1
$\begingroup$

Let $a$ and $n\ge3$ be integers. Suppose that $a^{n-1} \equiv 1 \pmod n$, while $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$, and I want to show that $n$ is prime.

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{\phi(n)}$ (this is the part I am having trouble proving, I know that the converse always holds, and I want to show that in this case the statement also holds), which means $n - 1 = k \cdot\phi(n)$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {\phi(n)}$ which means $\phi(n) \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $\phi(n) = n-1$.

Is it possible to prove the statement preceding the text in bold? Otherwise, what is the right approach to take for this problem?

$\endgroup$
  • 1
    $\begingroup$ Well there are some numbers called pseudo primes ( a special type of pseudo primes are called Carmichael numbers where(a,n)=1).These numbers are composite and yet follow fermat's little theorem.Hence, converse of Fermat's little theorem is not always true. $\endgroup$ – user369582 Sep 29 '16 at 19:37
  • $\begingroup$ @Avi Sorry, the title may be a bit misleading, but actually the problem has a stronger hypothesis than the title states (I didn't want to include too much in the title). Can you please have a look at the problem statement itself? Thanks! $\endgroup$ – b_pcakes Sep 29 '16 at 19:42
1
$\begingroup$

Ended up figuring out the answer. Here's the altered proof:

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{h}$, where $h$ is the order of $a\pmod n$, which means $n - 1 = k \cdot h$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {h}$ which means $h \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $h = n-1$. But $\phi(n) \leq n-1$ and $h \mid \phi(n)$ so $\phi(n) = n - 1$.

$\endgroup$
  • 1
    $\begingroup$ Kudos. I was just about to give up on this problem,! $\endgroup$ – user369582 Sep 29 '16 at 19:52
  • $\begingroup$ This is correct! $\endgroup$ – Jyrki Lahtonen Sep 29 '16 at 20:07

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.