0
$\begingroup$

I have trouble in understanding the last part of the sufficiency proof of Pépin´s Test (https://en.wikipedia.org/wiki/Pépin%27s_test).

"In particular, there are at least least F_{n}-1 numbers below F_{n} coprime to F_{n}, and this can happen only if F_{n} is prime".

Can anybody explain me that? Is it true that if the order of a number (mod n) equals n-1 then n is prime?

$\endgroup$
6
  • $\begingroup$ not true for $n=561$ then $a^{n-1}\equiv 1(mod n)$ for a in $\mathbb{Z}_{n}$ $\endgroup$
    – Ramez Hindi
    May 13, 2019 at 17:30
  • $\begingroup$ The term "order" applied to an element of a group may be misleading here. The quote describes $\phi(n)=n-1$ where $\phi$ is the totient function. $\endgroup$
    – robjohn ♦
    May 13, 2019 at 17:32
  • $\begingroup$ The set of elements $\pmod n$ which are prime to $n$ form a group under modular multiplication. That group has size $n-1$ if and only if $n$ is prime, and in general the order of that group is $≤n-1$. If that group contains an element of order $n-1$ then the order of the group must have order at least $n-1$ so... $\endgroup$
    – lulu
    May 13, 2019 at 17:34
  • $\begingroup$ To stress: the order of an element $g \pmod n$ means the least positive exponent such that $g^k\equiv 1 \pmod n$. Is that the way you intended to use the term? $\endgroup$
    – lulu
    May 13, 2019 at 17:36
  • $\begingroup$ Yes, Lulu, I was about to write that definition. Would it be possible to explain the reasoning without using group theory? $\endgroup$
    – Luis Gimeno Sotelo
    May 13, 2019 at 17:40

1 Answer 1

Reset to default
1
$\begingroup$

It is essentially saying that $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic of order $n-1$ iff $n$ is prime. Which is true since if $n$ is not prime, then $|(\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n)<n-1$.

Edit: In other words, by Euler's theorem we have the order of any element divides $\varphi(n)$. So, if the order of an element is $n-1$, we would have $n-1|\varphi(n)$. But $\varphi(n)<n-1$ if $n$ is not prime. We conclude that $n$ has to be prime.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .