# 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?

I might be giving out too much information here (so don't read unless you want spoilers). Anyway, as rings the Chinese Remainder Theorem gives

$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z}$$

The isomorphism takes $(\mathbb{Z}/n\mathbb{Z})^\times$ to $(\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$. Now the order of $(\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$ is $(p-1)(q-1)$ and if $m = \textrm{lcm}(p-1,q-1) = \phi(pq)/\gcd(p-1,q-1)$, then

$$(x,y)^m = (x^m,y^m)=(1,1)$$

using Lagrange on the components. This shows that the exponent of your group divides $\phi(pq)/\gcd(p-1,q-1)$, which is precisely the claim.

Addenda: The point here is that you can look at elements in $\mathbb{Z}/n\mathbb{Z}$ that are coprime to $n$ as pairs of nonzero elements of $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$. This is the classical Chinese Remainder Theorem that you should know if you've been assigned this problem. Now $\phi(n)/g$ is the least common multiple of $p-1$ and $q-1$, so taken such a pair to this power you should see the rest from Lagrange or Fermat's little theorem.

• Thanks for help but I´m not YET educated enaugh to understand this:) – user17919 Oct 27 '14 at 22:34
• I added a simpler version of what I wrote, so you can try to understand it. – Edvard Fagerholm Oct 28 '14 at 0:22