1
$\begingroup$

Fom wiki Fermat's little theorem, the theorem is as follows: If there exists an integer $a$ such that $ a^{p-1}\equiv 1\pmod p $ and for all primes $q$ dividing $p − 1$ one has ${\displaystyle a^{(p-1)/q}\not \equiv 1{\pmod {p}},}$ then $p$ is prime.

How to prove this theorem?

$\endgroup$
11
  • 1
    $\begingroup$ Do you know about Euler's theorem? It says that $a^{\phi(n)} \equiv 1 \; (\textrm{mod} \; n)$ for all $a \in \mathbf{Z}$ where $\phi$ is Euler's totient function. Using this and the fact that $\phi(n) = n - 1$ if and only if $n$ is prime, you can prove your theorem! $\endgroup$
    – Joseph Harrison
    Feb 17 at 7:44
  • 1
    $\begingroup$ @JosephHarrison Yes I know Euler's theorem. $\endgroup$
    – miket
    Feb 17 at 8:37
  • 1
    $\begingroup$ @JosephHarrison Nothing made. $\endgroup$
    – miket
    Feb 17 at 12:42
  • 1
    $\begingroup$ @JosephHarrison Yes I looked at that answer, but it seems that answer doen't helps. $\endgroup$
    – miket
    Feb 19 at 2:57
  • 1
    $\begingroup$ @miket If $a^{p - 1} \equiv 1 \mod{p}$, then $\phi(p)$ divides $p - 1$. Writing $p - 1 = k\phi(p)$ for some integer $k$, if $k > 1$ then it is divisible by a prime $q$. Then $(p - 1)/q = k\phi(p)/q$, the latter of which is a multiple of $\phi(p)$ and so $a^{(p - 1)/q} \equiv 1 \mod{p}$, against assumption. Therefore we must have $k = 1$ so that $\phi(p) = p - 1$ and $p$ is prime. I hope this helps! Feel free to ask for clarifications. $\endgroup$
    – Joseph Harrison
    Feb 19 at 19:38

0

Reset to default

Browse other questions tagged .