Daffodil International University
Faculties and Departments => Faculty Sections => Faculty Forum => Topic started by: jas_fluidm on May 23, 2013, 02:45:23 PM
-
Fermat's Little Theorem
It comes from observation of multiplication tables modulo prime number p that all rows are nothing but a permutation of the first row {1, 2,... , p-1}. The same is true for the columns. Here I wish to verify that this is indeed so. The proof depends on the Euclid's Proposition VII.30
If two numbers, multiplied by one another make some number, and any prime number measures the product, then it also measures one of the original numbers.
Let a be one of the positive remainders of division by p: 0 < a < p. I wish to prove that [a]p, [2a]p, [3a]p, ..., [(p-1)a]p are all different. Which, in terms of remainders, claims that in the sequence {a, 2a, 3a, ..., (p-1)a} no two numbers are congruent modulo p. Assume the opposite: let there be two numbers 1 ≤ m < n < p such that na = ma (mod p). This would imply that p|a(n-m). By the Proposition VII.30 either p|a or p|(n-m). But both a and (n-m) are positive integers less than p. So it can't divide either of them. Contradiction.
It indeed follows that the set {[a]p, [2a]p, [3a]p, ..., [(p-1)a]p} is just a permutation of the set
{[1]p, [2]p, [3]p, ..., [p-1]p},
or that rows in the multiplication tables are just permutations of the first row.
If two sets are permutations of each other, then products of their elements are clearly equal:
[(p-1)!]p = [1]p·[2]p·[3]p·...·[p-1]p
= [a]p·[2a]p·[3a]p·...·[a(p-1)]p
= [ap-1(p-1)!]p
= [ap-1]p·[(p-1)!]p
Now, dividing by [(p - 1)!]p (which is not 0 by Euclid's Proposition VII.30) gives 1 = [ap-1]p. Or, in terms of remainders,
ap-1 = 1 (mod p)
Going over the proof we may notice that it's an overkill to require a to be less than p. The proof remains valid for any a not divisible by p.
The statement first appeared without proof in a letter dated October 18, 1640 that Fermat wrote to Frenicle de Bessy . The first proof was given by Leibniz (1646-1716) and the one above was found by Ivory in 1806. Euler proved the theorem in 1736 and its generalization in 1760. The theorem is now known as the Fermat's Little Theorem to distinguish it from the Fermat's Last or Great Theorem. The latter has been finally established by the Princeton mathematician Andrew Wiles (with assistance from Richard Taylor) in 1994.
Remark
The set {{[0]N, [1]N, [2]N, ..., [p-1]N} is an additive group. The set {[1]p, [2]p, [3]p, ..., [p-1]p} is a multiplicative group. For the latter we saw that to every element [a]p in the group, there corresponds a permutation
{[a]p, [2a]p, [3a]p, ..., [(p-1)a]p}
of its elements. This relation is a group isomorphism: it preserves the group operation and is 1-1. A general statement, known as the Cayley's Theorem, asserts that this is a rule:
Every group is isomorphic to a group of permutations.
-
Use Fermat's little theorem to evaluate 11^123 mod 7?
Since gcd(7,11) = 1, Fermat's Little Theorem says that
11^(7-1) = 11^6 = 1 (mod 7).
Since 123 = 6 * 20 + 3, we have
11^123 = (11^6)^20 * 11^3 (mod 7)
= 1^20 * 11^3 (mod 7)
= 1 * 4^3 (mod 7)
= 64 (mod 7)
= 1 (mod 7).