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 |
---|---|
12^{1} = 12 | |
12^{2} = 144 | |
12^{3} = 1728 | |
12^{4} = 20736 | |
12^{5} = 248832 |