# Proving that $n|x^ {φ(n)/2} − 1$ for every $x$ coprime to $n$.

Let $n \in \Bbb{N}$ for which there exist two coprime numbers bigger than 2 dividing n. Show that for every x coprime to n we have $n|x^ {\phi(n)/2} − 1$. Conclude that there is no primitive root modulo n.

How does the fact the two coprime numbers bigger than 2 divide $n$ help? I tried using factorization and other theorems but I don't get anywhere. Besides, I have to prove that $x^{\phi(n)/2}\equiv1 \mod n$, but I could as well prove that $x^{\phi(n)}\equiv 1^2=1 \mod n$ so why is dividing $\phi(n)$ by 2 necessary? I could really use your help, any direction or hint is to what I might be overlooking.

• If you know that $y^2\equiv 1$, then it doesn't follow that $y\equiv 1$. – Wojowu May 16 '15 at 9:48
• You are correct. – Meitar May 16 '15 at 9:49

## 1 Answer

Let $n=ab$ with $a,b>2$ relatively prime. Recall that in this case both $\phi(a)$ and $\phi(b)$ are even. Write $\phi(a)=2p,\phi(b)=2q$. Then $\frac{\phi(n)}{2}=\frac{2p2q}{2}=2pq$.

Now we have $x^\frac{\phi(n)}{2}=x^{2pq}=(x^{2p})^q=(x^{\phi(a)})^q\equiv 1^q=1\pmod a$, so $a\mid x^\frac{\phi(n)}{2}-1$. Similarly $b\mid x^\frac{\phi(n)}{2}-1$. But $a,b$ are relatively prime, so $n=ab\mid x^\frac{\phi(n)}{2}-1$.

• Why are they even? – Meitar May 16 '15 at 10:35
• @Meitar $\phi(n)$ is even if $n>2$. Recall the formula $\phi(n) = n\prod_{p\mid n} \left(1-\frac{1}{p}\right)$. – Hanul Jeon May 16 '15 at 10:42
• Thank you. That is a very good solution. – Meitar May 16 '15 at 10:55
• I should make sure I remember all the properties of $\phi(n)$. It is actually trivial which is why I have to keep that in mind. – Meitar May 16 '15 at 10:56
• How can I conclude there is no primitive root modulo n? – Meitar May 16 '15 at 13:17