Fermat's Little Theorem is a central result in number theory that describes a surprising pattern in remainders. If p is prime, raising a whole number to the pth power gives a result with the same remainder as the original number when divided by p. This theorem matters because it turns large powers into manageable modular arithmetic problems.
It is a key tool for understanding primes, remainders, and modern encryption.
Understanding Math: Fermat's Little Theorem
The reason behind the theorem comes from arranging the nonzero remainders after division by a prime. For a prime p, these remainders are one through p minus one. Multiply every member of this list by a number a that is not divisible by p.
After reducing the results by p, no two results can match. If two matched, p would divide their difference, which would force p to divide a times the difference of the original remainders. Since p does not divide a, it would have to divide that difference.
This is impossible for two different remainders in the list. The multiplied list is therefore just a rearrangement of the original list. Comparing the two products produces the useful power rule.
This result can reject many composite numbers, but it cannot prove that every number passing the test is prime. A composite number can sometimes imitate a prime for one chosen base. For example, a number might give remainder one after a certain large power even though it has factors.
These are called pseudoprimes for that base. A rarer group, called Carmichael numbers, can pass the basic test for every base that shares no factor with them. This limitation matters.
A failed test gives certain evidence that a number is composite. A passed test gives only partial evidence. Reliable primality testing uses several stronger checks and carefully selected bases.
In practice, nobody calculates a huge power by multiplying the base thousands of times. Repeated squaring keeps each calculation small. To find the remainder of three to the power one hundred after division by seven, first find remainders for powers that double.
Three squared has remainder two. Squaring again gives a remainder of four for the fourth power. Squaring four gives a remainder of two for the eighth power.
The pattern can then be combined using the binary form of one hundred. At every stage, replace a large number with its remainder after division by seven. This works because replacing a number by an equal remainder does not change the final remainder after later multiplication.
Pay close attention to the conditions before applying any version of the theorem. The shorter power rule needs the base to share no factor with the prime divisor. If the base is a multiple of that prime, cancellation in the product argument is not valid.
Students often confuse equality with having the same remainder. Two numbers can be far apart in size yet behave identically in modular work. It helps to write the divisor beside every calculation and reduce early.
Check small cases by hand, look for repeating powers, then use repeated squaring when the exponent becomes large. These habits are useful in clock arithmetic, check digits, computer algorithms, and cryptography.
Key Facts
- If p is prime, then a^p ≡ a mod p for every integer a.
- If p is prime and gcd(a, p) = 1, then a^(p - 1) ≡ 1 mod p.
- The condition gcd(a, p) = 1 means a is not divisible by p.
- Example: 2^6 = 64, and 64 ≡ 1 mod 7, so 2^6 ≡ 1 mod 7.
- Fermat primality test: if a^(n - 1) is not congruent to 1 mod n for some gcd(a, n) = 1, then n is composite.
- Large powers can be reduced using exponent cycles, such as a^k mod p repeating with a period that divides p - 1.
Vocabulary
- Prime number
- A prime number is an integer greater than 1 with exactly two positive factors, 1 and itself.
- Congruent modulo p
- Two integers are congruent modulo p if they have the same remainder when divided by p.
- Greatest common divisor
- The greatest common divisor of two integers is the largest positive integer that divides both of them.
- Residue
- A residue modulo p is a possible remainder after division by p, usually one of 0, 1, 2, ..., p - 1.
- Primality test
- A primality test is a method for checking whether a number is prime or composite.
Common Mistakes to Avoid
- Using a^(p - 1) ≡ 1 mod p when a is divisible by p. This is wrong because the reduced version requires gcd(a, p) = 1.
- Applying the theorem to composite moduli without checking. Fermat's Little Theorem is guaranteed for prime p, not for every modulus.
- Thinking a^p = a instead of a^p ≡ a mod p. The theorem is about equal remainders, not equal integer values.
- Concluding that n is prime just because a^(n - 1) ≡ 1 mod n for one base a. Some composite numbers can pass this test for certain bases.
Practice Questions
- 1 Find the remainder when 3^100 is divided by 7.
- 2 Use Fermat's Little Theorem to find the remainder when 5^42 is divided by 11.
- 3 Explain why Fermat's Little Theorem can prove that a number is composite when the congruence fails, but cannot always prove that a number is prime when the congruence holds.