Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
