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$.
On
As you (the OP) pointed out, $x^{\varphi(n)}=x^{2n}\equiv 1\mod pq$, whenever $\gcd(x,pq)=1$. So the question is, does this imply $x^{n}\equiv 1\mod pq$ whenever $\gcd(x,pq)=1$?
If this were false, there would be $y\neq 1$ so that $y^2\equiv1$ mod $pq$, what this would mean that $\mathbb{Z}_{pq}$ would have an element of order 2 (namely $y$). But all of it's elements are of order $p,q$ or $pq$(By Lagrange theorem)
On
Hint $\ 2\mid a,b\,\Rightarrow a,b\mid ab/2\,\Rightarrow\, \color{#c00}{{\rm lcm}(a,b)}\mid \color{#0a0}{ab/2}$
Recall: $\ \ \ \begin{align} x^{\large a}\equiv 1\!\!\!\pmod{\!p}\\ x^{\large b}\equiv 1\!\!\!\pmod{\!q}\end{align}\,\Rightarrow\, x^{\large \color{#c00}{{\rm lcm}(a,b)}}\equiv 1\pmod{\!pq},\, $ so $\ x^{\large\color{#0a0}{ab/2}}\equiv 1\pmod{\!pq}\ $ by above
Remark $ $ It stays true if we replace $\,2\,$ by any conmon divisor $\,c\mid a,b.\,$ Thus we can cancel $c$ from the "obvious" common multiple $\,ab\,$ to obtain a smaller one $\,m = ab/c.\ $ $\,c\,$ is greatest $\iff m\,$ is least, which leads to a duality based proof of $\:{\rm lcm}(a,b) = ab/\gcd(a,b)$
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$.