Fermat's Little Theorem
Fermat's Little Theorem says:
- a is an integer
- p is a prime number
An example will help:
Example: a=2, p=5
ap − a = 25 − 2 = 32 − 2 = 30
And 30 is divisible by 5
Maybe that was just luck, let's try another:
Example: a=3, p=7
ap − a = 37 − 3 = 2187 − 3 = 2184
And 2184 is divisible by 7 (because 7 × 312 = 2184)
Colored Beads
It seems like a miracle that it works, but we can explain using colored beads!
We are aiming for this:
Imagine we have a=7 different types of beads 0123456 and make strings of p=5 beads like 23436 (duplicates allowed):
(7 choices for 1st bead) × (7 choices for 2nd bead) × ... × (7 choices for 5th bead) =
Using the Combinations and Permutations Calculator there are 16,807 strings:
00001
00002
00003
14350
14351
66665
66666
Then we remove the a=7 "solid color" strings:
11111 X
22222 X
33333 X
44444 X
55555 X
66666 X
And we are left with:
Now we make necklaces of them, and find we can group them like this:
00010
00100
01000
10000
Do you see they all make the
same necklace, just rotated?
Note that we always go clockwise. More examples:
01230
12300
23001
30012
03040
30400
04003
40030
Each necklace group has p=5 strings in it, no more, no less.
The only exceptions to this rule are solid color strings, which are gone already, and strings made of a repeating pattern, which can't occur when p is prime.
All the strings can be formed into groups of 5 and so must be divisible by 5.
And so:
Other Forms
The symbol ≡ means congruent to (has the same remainder as).
So, a ≡ b (mod p) simply means that when we divide both a and b by p, we get the same remainder.
Let's restate the formula using the symbol ≡:
So these 3 forms are the same:
ap ≡ a (mod p)
a(p-1) ≡ 1 (mod p)
Let's see them in action!
| a | p | ap | ap-a | ap-1 | (ap-a)/p | ap mod p | ap-1 mod p |
| = integer | = a mod p | = 1 | |||||
| 0 | 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 5 | 1 | 0 | 1 | 0 | 1 | 1 |
| 2 | 5 | 32 | 30 | 16 | 6 | 2 | 1 |
| 3 | 5 | 243 | 240 | 81 | 48 | 3 | 1 |
| 4 | 5 | 1024 | 1020 | 256 | 204 | 4 | 1 |
| 5 | 5 | 3125 | 3120 | 625 | 624 | 0 | 0 |
| 6 | 5 | 7776 | 7770 | 1296 | 1554 | 1 | 1 |
They work great, except the last form doesn't work when a is a multiple of p.
Uses
Fermat's Little Theorem is very useful in cryptography where we do crazy things like raise huge numbers to huge powers with a huge modulus.
Let's see an example using a moderately large exponent:
Example: Find the remainder when we divide 740,000 by 67
Just calculating 71,000 is hard for a spreadsheet, but all these calculations are fine:
Answer: 56
Despite the many steps this is a much quicker way to find that remainder.
One more example:
Example: Find the remainder when we divide 33,000 by 19
A power to get us close to 3000:3000/18 = 166 as a whole number Use that power:(318)166 ≡ 1166 (mod 19) That gets us close:32988 ≡ 1 (mod 19) Need 12 more:312(32988) ≡ 312 (mod 19) Simplify:33000 ≡ 312 (mod 19) A few more steps to simplify 312 312 = (34)3 = 813:33000 ≡ 813 (mod 19) 81 ≡ 5 (mod 19):33000 ≡ 53 (mod 19) 53 = 125 ≡ 11 (mod 19):33000 ≡ 11 (mod 19)
Answer: 11
Why Prime?
Why does p need to be prime?
Let's try p = 6 = 2 × 3 so a string can be made of repeating patterns of 2 or 3 long such as:
That example has only 3 different strings in a group:
231231
312312
So we no longer have our "every necklace has p strings" rule and we become sad.
But this won't happen when p is prime. Happy again.