Welcome to NRICH.

 
Fermat's Little Theorem and Wilson's Theorem
By Olof Sisask (P3033) on Thursday, February 15, 2001 - 07:55 pm:

Hi,

Does anyone know of a proof for Fermat's Little Theorem (that doesn't involve Group Theory, or, if it does, could give me a brief introduction to it, as I have almost forgotten what little I knew).

Thanks,
Olof.

By Michael Doré (Md285) on Thursday, February 15, 2001 - 08:15 pm:

Are you happy with the theorem of unique prime factorisation? That is, if ab is a multiple of a prime p then either a or b is a multiple of p? If so you can do the following.

Consider the numbers:

1n
2n
3n
...
(p - 1)n

where p is prime and n is not a multiple of p.

Suppose two of them are the same (mod p). Then we'd have rn = sn (mod p), i.e. n(r - s) = 0 (mod p) which, by unique factorisation, implies r = s (mod p) and as 0 < r,s < p this means r = s. Therefore no two of the listed numbers are the same mod p. Also none of the numbers are a multiple of p. And there are p-1 of them, so it follows that the p-1 numbers are 1,2,...,p-1 in some order (mod p). So if we multiply them all together we get:

(1n)(2n)...((p-1)n) = (1)(2)...(p-1) (mod p)

np-1 (p-1)! = (p-1)! (mod p)
(p-1)!(np-1 - 1) = 0 (mod p)

By unique factorisation, either (p - 1)! or np-1 - 1 is a multiple of p. The former clearly isn't so np-1 - 1 = 0 (mod p) or np-1 = 1 (mod p) which is equivalent to Fermat's Little Theorem.

Yours,

Michael

PS Another method is to prove, using the binomial theorem, that (n + 1)p - np = 1 (mod p). From there you can prove by induction that np = n (mod p) which is also equivalent to Fermat.

By Anonymous on Thursday, February 15, 2001 - 08:26 pm:

Alternatively you could consider the sequence

n, n2, n3, ... np-1

and then proceed in a similar way.

By Olof Sisask (P3033) on Friday, February 16, 2001 - 08:49 pm:

I see, great! These things are never as tough as you imagine, are they? Well, at least not with NRICHers explaining them.

Regards,
Olof.

By Michael Doré (Md285) on Saturday, February 17, 2001 - 12:52 am:

No problem, Olof. Interestingly enough, in the
above proof, the (p - 1)! factor we cancelled is
in fact equal to -1 (mod p). This is called
Wilson's Theorem (though we didn't need to
know it above as the (p - 1)!s cancelled
because
they clearly aren't multiples of p). To prove
Wilson's theorem, i.e. for primes p:

(p - 1)! = -1 (mod p)

we simply use the fact that if x is not
a multiple of p, then there exists unique y with
0 < y < p and xy = 1 (mod p).