# How to prove Lucas's Converse of Fermat's Little Theorem without using primitive root?

Problem:
If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n > 1)$

I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?

And another related question about power residue:
If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$? Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it.
Any idea?

Thanks,

## 2 Answers

Hint $$\$$ The conditions imply that the order $$\rm\:k\:$$ of $$\rm\:x\:$$ is a divisor of $$\rm\:n-1\:$$ but not a proper divisor, hence $$\rm\: k = n-1\:.\$$ By Euler, $$\rm\ k\ |\ \phi(n)\$$ so $$\rm\ n-1\: \le\: \phi(n)\:.\$$ This implies that $$\rm\:n\:$$ is prime, since $$\rm\ \phi(n) \:\le\: n-\color{red}{2}\$$ for composite $$\rm\:n,\:$$ since they have at least $$\:\color{red}2\$$ smaller naturals non-coprime to $$\rm\:n.$$

Remark  In fact we can we can restrict to maximal proper divisors $$\,q\,$$ using the following.

Order Test $$\ \,a\,$$ has order $$\,n\iff a^n \equiv 1\,$$ but $$\,a^{n/p} \not\equiv 1\,$$ for every prime $$\,p\mid n.\,$$

Proof $$\ (\Leftarrow)\$$ If $$\,a\,$$ has $$\,\color{#c00}{{\rm order}\ k}\,$$ then $$\,k\mid n\,$$ (proof). If $$\:k < n\,$$ then $$\,k\,$$ is proper divisor of $$\,n\,$$ therefore $$\,k\,$$ arises by deleting at least one prime $$\,p\,$$ from the prime factorization of $$\,n,\,$$ hence $$\,k\mid n/p,\,$$ say $$\, kj = n/p,\$$ so $$\ a^{n/p} \equiv (\color{#c00}{a^k})^j\equiv \color{#c00}1^j\equiv 1,\,$$ contra hypothesis. $$\ (\Rightarrow)\$$ Clear.

• When you say order $k$ of $x$, do you mean $ord_{k}x$? – Chan Mar 10 '11 at 6:44
• @Chan: $\rm\ mod\ n\::\ k\$ is the order of $\rm\ x\:,\$ so $\rm\ x^j\equiv 1\ \iff\ k\ |\ j\:$ – Bill Dubuque Mar 10 '11 at 6:47
• Thanks, sorry my mathematics vocabulary are very limited. I tried to understand your hint, but I was confused because the argument that you used is very similar to the way the book proved using primitive root. – Chan Mar 10 '11 at 6:51
• @Chan: What book? – Bill Dubuque Mar 10 '11 at 6:54
• I'm currently reading "Elementary Number Theory and Its application" by Kenneth H. Rosen 6th edition. Thanks. – Chan Mar 10 '11 at 7:07

Do you understand the definition of $\phi(n)$? It's the number of natural numbers less than $n$ which are relatively prime to $n$. If $n$ is prime, then $\phi(n)$ is necessarily $n-1$ (since only 1 is relatively prime with $n$). Likewise, if $\phi(n) = n-1$ then only one number less than $n$ is relatively prime to it, which must be the number 1, so $n$ is prime. So that would be the relationship between them.

• The above definition of $\rm\:\phi(n)\:$ is incorrect. $\rm\:\phi(n)\:$ is the number of units (invertibles) modulo $\rm\:n\:$ or, equivalently, the number of naturals smaller than $\rm\:n\:$ that are coprime to $\rm\:n\:.\:$ Also it is not true that $\rm\ a^{\phi(n)}\equiv 1\ (mod\ n)\$ for all $\rm\ a\neq 0$. – Bill Dubuque Mar 10 '11 at 18:43
• Yeah, I meant to say "less than n which are relatively prime to n", I just had a little brain-fart and typed "divides" instead. And you're also correct about the second mistake. Clearly I wasn't at my best. I'll edit the answer substantially. – Keith Irwin Mar 11 '11 at 6:17