2
$\begingroup$

Problem:
If $n > 1$, and there exists an integer $x$ such that $x^{n-1} \equiv 1 \pmod{n}$, but $x^{q} \not\equiv 1 \pmod{n}$ for all strict divisors $q$ of $n - 1$, then $n$ is prime.

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,

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The hypotheses imply the order $\,k\,$ of $\,x\pmod{\! n}\,$ is a divisor of $\,n\!-\!1,\,$ but not a proper divisor, so $\, k = n\!-\!1.\, $ These $\,n\!-\!\color{#c00}{\bf 1}$ incongruent powers of $\:\!x\:\!$ are all invertible $(x^kx^{n-1-k}\equiv 1)\,$ hence coprime to $\:\!n,\,$ so $\:\!n\:\!$ is prime (a composite $\:\!n\!=\!ab\,$ has at most $\,n\!-\!\color{#c00}{\bf 2}\,$ coprimes - it omits $\,\color{#c00}{0,\:\!a}$).

Optimization $ $ Lucas Primality Test. We need only test maximal proper divisors $\,q=n/p\,$ by

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.

$\endgroup$
7
  • $\begingroup$ When you say order $k$ of $x$, do you mean $ord_{k}x$? $\endgroup$ Commented Mar 10, 2011 at 6:44
  • $\begingroup$ @Chan: $\rm\ mod\ n\::\ k\ $ is the order of $\rm\ x\:,\ $ so $\rm\ x^j\equiv 1\ \iff\ k\ |\ j\:$ $\endgroup$ Commented Mar 10, 2011 at 6:47
  • $\begingroup$ 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. $\endgroup$ Commented Mar 10, 2011 at 6:51
  • $\begingroup$ @Chan: What book? $\endgroup$ Commented Mar 10, 2011 at 6:54
  • 1
    $\begingroup$ Great! The subgroup of $(\mathbb{Z}/n)^{\times}$ generated by $a$ has cardinality $n-1$, so the group itself has at least $n-1$ elements. Therefore $n$ is prime ( no need for Euler here I guess). $\endgroup$ Commented Sep 4, 2022 at 1:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.