By Fermat's Little Theorem, 3^6 ≡ 1 (mod 7) since 7 is prime and gcd(3,7) = 1. Write 100 = 16·6 + 4. Then 3^100 = (3^6)^16 · 3^4 ≡ 1 · 81 ≡ 81 (mod 7). Since 81 = 11·7 + 4, we get 3^100 ≡ 4 (mod 7). The key step is reducing the exponent 100 modulo p−1 = 6, not modulo p = 7 — a common error that would give the wrong answer.
Question 2 Multiple Choice
To compute 2^1000 mod 17 using Fermat's Little Theorem, you should first reduce the exponent 1000 modulo which number?
A17, because all arithmetic is done mod 17
B16, because FLT gives 2^16 ≡ 1 (mod 17), so the exponent repeats with period 16
C1000, because the theorem applies to the base, not the exponent
D8, because you use half of p−1 for even bases
Fermat's Little Theorem says a^(p−1) ≡ 1 (mod p), so the exponent repeats with period p−1 = 16. Write 1000 = 62·16 + 8, so 2^1000 ≡ (2^16)^62 · 2^8 ≡ 1 · 256 ≡ 256 (mod 17). Since 256 = 15·17 + 1, the answer is 1. Reducing the exponent mod p instead of mod p−1 is the most common error — it gives 1000 mod 17 = 14, which produces the wrong result.
Question 3 True / False
For any prime p and any integer a — including multiples of p — the congruence a^p ≡ a (mod p) holds.
TTrue
FFalse
Answer: True
The corollary a^p ≡ a (mod p) is valid for all integers a. When gcd(a,p) = 1, it follows from a^(p−1) ≡ 1 by multiplying both sides by a. When p | a, both sides equal 0 mod p. The corollary is more convenient than the main theorem precisely because it requires no divisibility check — useful in proofs and applications where you cannot assume gcd(a,p) = 1.
Question 4 True / False
Fermat's Little Theorem states that a^(p−1) ≡ 1 (mod p) for most integer a when p is prime.
TTrue
FFalse
Answer: False
The theorem requires gcd(a, p) = 1 — that is, p does not divide a. If p | a, then a ≡ 0 (mod p), so a^(p−1) ≡ 0 (mod p), not 1. For example, 7^6 ≡ 0 (mod 7), not 1. The condition gcd(a,p) = 1 ensures a belongs to the multiplicative group (Z/pZ)*, which has order p−1; the theorem follows from the fact that every group element's order divides the group order.
Question 5 Short Answer
Explain why the set {a, 2a, 3a, ..., (p−1)a} reduced modulo a prime p must be a permutation of {1, 2, ..., p−1} when gcd(a,p) = 1, and how this implies Fermat's Little Theorem.
Think about your answer, then reveal below.
Model answer: If two elements ka and la were congruent mod p — that is, p | (k−l)a — then since p is prime and gcd(a,p) = 1, p must divide k−l. But k and l are both in {1,...,p−1}, so |k−l| < p, forcing k = l. Thus all p−1 elements are distinct and nonzero mod p, so they must be exactly {1,...,p−1} in some order. Multiplying both sides of a·2a·...·(p−1)a ≡ 1·2·...·(p−1) (mod p) gives a^(p−1)·(p−1)! ≡ (p−1)! (mod p). Since (p−1)! is nonzero mod p, canceling it yields a^(p−1) ≡ 1 (mod p).
This 'scrambling' proof uses only the pigeonhole principle and basic properties of primes — no group theory required. It also reveals why primality is essential: if p were composite, gcd(a,p) = 1 would not prevent two multiples ka and la from colliding mod p, and the permutation argument would fail.