1
$\begingroup$

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ where $\mathbb{P}$ denotes the set of prime numbers $\Rightarrow$ $n\in\mathbb{P}$.

What does all that mean? Fermat's little theorem states, that if $p\in\mathbb{P}$, then it holds for all $a\in\mathbb{Z}$ with $p\nmid a$:$$a^{p-1}\equiv 1\text{ mod }p$$ It seem's like this has something in common with the statement above. However, we only know that the congruence is fulfilled for one specific $a$ and Fermat's little theorem doesn't help in this direction.

So, how would one argue?

$\endgroup$
2
  • $\begingroup$ You may wish to consider an Euler pseudoprime ( en.wikipedia.org/wiki/Euler_pseudoprime ) where the set $\mathbb{P} = \{2\}$ is insufficient to show $n$ is prime. $\endgroup$
    – Eric Towers
    Jun 13, 2014 at 17:15
  • $\begingroup$ Your formulation is needlessly confusing. In you title there is, right away, "if" and "there exists", but in the first sentence after the title both are absent, and coming to "$\Rightarrow$" near the end, one suddenly realises there was some condition being formulated. Where did that condition start? Instead of "$\Rightarrow$" I would prefer just ending the first sentence (which is complete); then continue "How can one deduce from this that $n$ is prime?" $\endgroup$
    – Marc van Leeuwen
    Jun 15, 2014 at 9:47

3 Answers 3

Reset to default
2
$\begingroup$

The assumption implies that $a$ is an element of order $n-1$ in the multiplicative monoid $\mathbb{Z} / n \mathbb{Z}$. (If the order of $a$ were a proper divisor $m$ of $n-1$, consider a prime $p$ dividing $(n-1)/m$, and compute $a^{(n-1)/p} = (a^{m})^{(n-1)/(mp)} \equiv 1 \pmod{n}$, against the assumption.)

Since $a$ is invertible in $\mathbb{Z} / n \mathbb{Z}$, as $a \cdot a^{n-2} \equiv 1 \pmod{n}$, it follows that $\mathbb{Z} / n \mathbb{Z}$ is a field, and thus $n$ is prime.

$\endgroup$
6
  • $\begingroup$ What's the "order" of an elemenet $a$ of a multiplicative monoid? I assume you will answer, that it's the smallest natural number $n$ such that $a^n=1$ - but I thought that would one call the "characteristic" of $a$. But, what's the order of $M$ itself? Why is $n-1$ the order of $\mathbb{Z}/n\mathbb{Z}$ and why must the order of an element be a divisor of the order of the monoid? This seems like Lagrange's theorem, which states something similar for groups. $\endgroup$
    – 0xbadf00d
    Jun 13, 2014 at 18:22
  • 1
    $\begingroup$ I would call it order in this context, keeping characteristic for the (additive!) order of unity in a ring, but maybe there are other usages. It is not difficult to show that $a^{k} = 1$ of and only if the order of $a$ divides $k$. $\endgroup$
    – Andreas Caranti
    Jun 13, 2014 at 18:37
  • $\begingroup$ So, we want to show $$a^k=1\Leftrightarrow\text{ord }a\mid k$$ While the direction $(\Leftarrow)$ is easy, how would you prove the other direction? $\endgroup$
    – 0xbadf00d
    Jun 13, 2014 at 20:02
  • 1
    $\begingroup$ if $a^{k} = 1$, divide $k$ with remainder by the order of $a$. The remainder $r$ is smaller than the order of $a$, and still satisfies $a^{r} = 1$, so $r$ has to be zero. $\endgroup$
    – Andreas Caranti
    Jun 13, 2014 at 20:12
  • $\begingroup$ Why does it follow, that $\mathbb{Z}/n\mathbb{Z}$ is a field? It would be a field if and only if each element is invertible, but the only thing we've shown is, that this specific $a$ is invertible, right? $\endgroup$
    – 0xbadf00d
    Jun 13, 2014 at 22:21
2
$\begingroup$

Hint: The condition says that there is an element $a$ of order $n-1$. But the order of an element is always $\le \varphi(n)$. So $\varphi(n)=n-1$, which for $n\gt 1$ implies that $n$ is prime.

$\endgroup$
3
  • $\begingroup$ Talking about the "order" of $a$, you mean the order of $a$ as an element of $(\mathbb{Z}/n\mathbb{Z})^\times$, right? $\endgroup$
    – 0xbadf00d
    Jun 13, 2014 at 18:37
  • $\begingroup$ Yes, the smallest positive integer $e$ such that $a^e\equiv 1\pmod{n}$. $\endgroup$
    – André Nicolas
    Jun 13, 2014 at 19:16
  • $\begingroup$ @AndréNicolas I read the proof from an article about this theorem. The author shows that $a^{\phi(n)} \equiv 1 \mod{n}$. Any idea why that is the case? We don't assume $a$ and $n$ are relatively prime, otherwise, we can just use the Euler's theorem. $\endgroup$
    – Jk_0fjnewuif
    Sep 8, 2020 at 5:42
0
$\begingroup$

Hint $\ $ Let $\,k =\,$ order of $\,a\,$ modulo $\,n\,$ Then $\,a^j\equiv 1\iff k\mid j,\,$ so our hypotheses become

$$\begin{eqnarray} a^{n-1}\equiv 1 &&\iff k\mid n-1\\ \\ a^{(n-1)/p}\not\equiv 1&&\iff k\nmid (n-1)/p\end{eqnarray}\quad $$

The first says that $\,k\,$ is a factor of $\,n-1\,$ and the second, being true for all primes $\,p\mid n-1,\,$ implies that $\,k\,$ is not a proper factor of $\,n-1\,$ [indeed, by unique factorization any proper factor $\,k\,$ of $\,n-1\,$ arises by deleting at least one prime factor $\,p,\,$ thus $\,k\mid (n-1)/p\ $]

Therefore $\, k = n\!-\!1.\ $ By Euler, $\ k=n\!-\!1\ |\ \phi(n)\ $ so $\ \phi(n) \ge n\!-\!1.\ $ Therefore $\:n\:$ is prime, since $\ \phi(n) \:\le\: n-\color{red}{2}\ $ for composite $\:n = ab,\ a,b > 1,\,$ since it has at least $\:\color{red}2\ $ smaller naturals that are not coprime to $\:n,\,$ namely $\,0\,$ and $\,a.$

Remark $\ $ The idea generalizes, e.g. see the Pocklington-Lehmer primality test.

$\endgroup$
3
  • $\begingroup$ How do you get $n- 1| \phi(n)$? We don't assume $a$ and $n$ are relatively prime. I am just wondering how people get $a^{\phi(n)} \equiv 1 \mod{n}$. $\endgroup$
    – Jk_0fjnewuif
    Sep 8, 2020 at 5:46
  • 1
    $\begingroup$ @Smith $\,a^{n-1}\equiv 1\pmod{n}\Rightarrow\, a(a^{n-2})+b\,n = 1\,\Rightarrow\,\gcd(a,n)=1.\,$ Or, equivalently, $a$ is invertible hence coprime to the modulus. See here for a clearer presentation. $\endgroup$
    – Bill Dubuque
    Sep 8, 2020 at 6:00
  • $\begingroup$ That makes sense! Thanks! $\endgroup$
    – Jk_0fjnewuif
    Sep 8, 2020 at 15:31

You must log in to answer this question.

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