Let $p$ and $q$ be distinct odd primes and write $$n=\frac{(p-1)(q-1)}{2}$$ Show that $$x^n\equiv 1\mod pq$$ for all $x\in\mathbb{Z}$ with $\gcd(x,pq)=1$.
I tried solving it the following way. Since $$\varphi(pq)=(p-1)(q-1)=2n$$ (where $\varphi$ denotes Euler's totient function), we have, by Euler's congruence, that $$x^{\varphi(n)}=x^{2n}\equiv 1\mod pq$$ whenever $\gcd(x,pq)=1$. However, I don't see how I can reduce the power of $x$ from $2n$ to $n$.
Best Answer
Hint: You know $(x^n)^2-1\equiv (x^n+1)(x^n-1)\equiv 0$. This means that both $p$ and $q$ divide $(x^n+1)(x^n-1)$. Show that neither $p$ nor $q$ divides $x^n+1$.
Actually, the previous argument is unduly complicated. Since Fermat's little theorem implies $x^{p-1}\equiv 1\pmod p$, you have $$ x^n=(x^{p-1})^{(q-1)/2}\equiv 1^{(q-1)/2}=1\pmod p. $$ This means $p$ divides $x^n-1$. By the same logic, $q$ divides $x^n-1$, so $pq$ divides $x^n-1$.