Fermat's Theorem

Congruent Modulo

If p is prime and a is a positive integer not divisible by p then:

a^(p-1) ≡ 1 mod p is equivalent to a^p ≡ a mod p

Let's find out the mod of a divisor with a large exponent. However, first let's use an exponent that isn't extremely large and then afterwards use a large one.

(6¹⁷) mod(13)
[(6¹²) * (6⁵)] mod(13)
[(6¹²) mod(13)] * [(6⁵ mod(13)]
1 * (6⁵) mod(13) = 2

This example can be done on Calc.exe that comes with the MS Windows operating system. First, you can confirm this by doing 6¹⁷ mod(13) and the answer will be 2. However, using Fermat's theorem you can obtain the exponent of 12 from 13 - 1 resulting in 6¹² * 6⁵ = 6¹⁷. So, according the Fermat's theorem a^{(p - 1)} mod p = 1, we have (6¹²) mod(13) = 1, which leaves something easily calculable 6⁵ mod(13) = 2. Let's now look at a very large exponent:

(5²⁰⁰³) mod(7)
[(5¹⁹⁹⁸) * (5⁵)] mod(7)
[(5¹⁹⁹⁸) mod(7)] * [(5⁵) mod(7)]
1 * (5⁵) mod(7) = 3

The only difference between this problem and the one above is that 1998 is a multiple of p - 1, hence 6 * 333 = 1998. Now what happens when the dividend is very large (or larger than the exponent)? The answer lies within the Chinese Remainder Theorem.

Fermat's Last Theorem.

Since we're talking about Fermat, it is suffice to talk about his famous last theorem. Mathematicians have struggled with finding a solution to Fermat's last theorem, which came about in 1637. Fermat claimed that xⁿ + yⁿ = zⁿ does not have a solution in positive integers x, y, and z for n > 2. However, no one has been able to prove or disprove this. However, interestingly enough, by 1936 Alonzo Church along with Alan Turing was able to show that Fermat's last theorem was not effectively calculable thus was not decidable.

Links

http://www.avernus.org.uk/encrypt.php?article=fermat
http://www.math.okstate.edu/~wrightd/crypt/lecnotes/node19.html
http://www.mbay.net/~cgd/flt/flt08.htm
http://www.aryankindred.com/sniffy/fermat.htm
http://www.public.iastate.edu/~kchoi/time.htm
http://www.bath.ac.uk/~ma0drje/www.Fermat/Fermats%20Theorem.html
http://www.sasquatch.com/~kory/fermats_enigma.html
http://www.cs.utsa.edu/~wagner/laws/AFermat.html