Fermat's Little Theorem
Fermat's Little Theorem states that if
p is a prime number
and
n any integer that does not have
p as a factor, then
n p-1
= 1 mod p. This theorem proved 350 years ago is the basis of the following
shuffling scheme. Choose the prime number 5 and another number that does
not have a factor of 5, say 12. The second column in the table below represents
a type of shuffling of a four-card deck where "shuffling" is accomplished
by multiplying by 12. We also notice that, after we shuffle 4 times
mod
5, we always get one as the answer. Try this shuffling yourself. Set the
prime number to 7 and pick another number not divisible by 7. Shuffle it
by raising your number to powers mod 7. What do you observe? By the way,
the spirit of the above shuffling procedure is used millions of times each
day encoding electronic communications. See the
RSA Coding Scheme for further
information.
| Powers of 12 | Powers of 12 mod 5 |
|---|
| 121 = 12 |
2 |
| 122 = 144 |
4 |
| 123 = 1728 |
3 |
| 124 = 20736 |
1 |
| 125 = 248832 |
2 |
updated: Jul 31st 2008
