3
$\begingroup$

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.

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

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why are they even? $\endgroup$ – Meitar May 16 '15 at 10:35
  • 1
    $\begingroup$ @Meitar $\phi(n)$ is even if $n>2$. Recall the formula $\phi(n) = n\prod_{p\mid n} \left(1-\frac{1}{p}\right)$. $\endgroup$ – Hanul Jeon May 16 '15 at 10:42
  • $\begingroup$ Thank you. That is a very good solution. $\endgroup$ – Meitar May 16 '15 at 10:55
  • $\begingroup$ 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. $\endgroup$ – Meitar May 16 '15 at 10:56
  • $\begingroup$ How can I conclude there is no primitive root modulo n? $\endgroup$ – Meitar May 16 '15 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.