RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$ I should prove that $a^{\varphi(n)/g} \equiv 1 \pmod{n}$, so I thought I would prove it with primitive roots but I got stuck. Here is the assignment:


  Let $p, q$ be primes such that $p \ne q$. Denote $n = pq$, $\varphi(n) = (p − 1)(q − 1)$, and $g = gcd(p − 1, q − 1)$. Prove that
  
  $$a^{\varphi(n)/g} \equiv 1 \pmod{n} ~ ~ \text{for all} ~ a ~ \text{satisfying} ~ \gcd(a, n) = 1$$


Any help/hint would be great. Thanks.
Hint: try to prove that $a^{phi(n)/g} \equiv 1 \pmod p$ for all $a$ satisfying $gcd(a, n) = 1$.

Metahint: $phi(n)/g = (p-1) \times (q-1)/g$; is $(q-1)/g$ an integer?