You need to compute 3^100 mod 7. Applying Euler's theorem with φ(7) = 6, which computation is correct?
A3^100 ≡ 3^(100 mod 7) ≡ 3^2 ≡ 2 (mod 7) — reduce the exponent by the modulus
B3^100 ≡ 3^(100 mod 6) ≡ 3^4 ≡ 81 ≡ 4 (mod 7) — reduce the exponent modulo φ(7)
C3^100 ≡ 1 (mod 7) — Euler's theorem says any power of any number is 1 mod the modulus
D3^100 ≡ 3^(100 mod 3) ≡ 3^1 ≡ 3 (mod 7) — reduce by the base
Euler's theorem says a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1. Since 7 is prime, gcd(3, 7) = 1 and φ(7) = 6. This means 3^6 ≡ 1 (mod 7), so 3^100 = (3^6)^16 · 3^4 ≡ 1^16 · 3^4 ≡ 81 ≡ 4 (mod 7). The reduction is: reduce the exponent modulo φ(n), not modulo n. The common mistake (option A) reduces by n itself — that is wrong; n is the modulus for the *result*, not for the exponent.
Question 2 Multiple Choice
A student wants to apply Euler's theorem to compute 6^10 mod 9. They note φ(9) = 6 and conclude 6^10 ≡ 6^(10 mod 6) ≡ 6^4 (mod 9). What is wrong?
Aφ(9) is not 6; it should be 3
BThe exponent reduction rule uses φ(n) − 1, not φ(n)
CEuler's theorem requires gcd(a, n) = 1, but gcd(6, 9) = 3 ≠ 1, so the theorem does not apply
DNothing — the computation is correct
Euler's theorem has a necessary hypothesis: gcd(a, n) = 1. Here gcd(6, 9) = 3, so 6 and 9 share a common factor and the theorem simply does not apply. φ(9) = 6 is actually correct (the units mod 9 are 1, 2, 4, 5, 7, 8). But since 6 is not a unit mod 9, you cannot use Euler's theorem to reduce 6^10 mod 9. In fact 6^10 mod 9 = 0, since 6^2 = 36 ≡ 0 (mod 9)... wait, that's 3^2|36, and 9|36, so yes 6^2 ≡ 0. The coprimality condition is not a technical nicety — without it the theorem is false.
Question 3 True / False
Fermat's Little Theorem — that a^(p−1) ≡ 1 (mod p) for any prime p not dividing a — is a special case of Euler's Theorem.
TTrue
FFalse
Answer: True
Yes. When n = p is prime, every integer from 1 to p−1 is coprime to p, so φ(p) = p − 1. Euler's theorem then says a^φ(p) = a^(p−1) ≡ 1 (mod p) for gcd(a, p) = 1 — exactly Fermat's Little Theorem. Euler's theorem is the generalization that extends this to composite moduli, which is what gives it broader applicability, including in RSA where the modulus n = pq is the product of two large primes.
Question 4 True / False
Euler's theorem states that a^φ(n) ≡ 1 (mod n) holds for most integer a, including those that share a common factor with n.
TTrue
FFalse
Answer: False
The condition gcd(a, n) = 1 is essential — without it the theorem is false. For example, a = 2, n = 4: φ(4) = 2, and 2^2 = 4 ≡ 0 (mod 4), not 1. The reason is that the proof relies on the set of units modulo n (integers coprime to n) forming a group under multiplication; multiplying by a unit permutes this group. If gcd(a, n) > 1, then a is not a unit and does not act on the units by permutation — the proof breaks down entirely.
Question 5 Short Answer
Explain in your own words why the proof of Euler's theorem works — why does multiplying all units modulo n by a fixed unit a give back the same set of units?
Think about your answer, then reveal below.
Model answer: The units modulo n form a group under multiplication. If a is a unit (gcd(a,n)=1), multiplying any unit u by a gives another unit (since gcd(au, n) = 1 when gcd(a,n)=1 and gcd(u,n)=1), and the map u ↦ au is injective (cancellation holds for units). So the map sends the finite set of units to itself injectively — meaning it is a bijection, a rearrangement. The product of all units equals the product of their images under this rearrangement. Setting these equal gives a^φ(n) · (product of units) ≡ (product of units) (mod n), and canceling the product of units (which is itself a unit, hence invertible) yields a^φ(n) ≡ 1 (mod n).
This 'rearrangement argument' is elegant because it requires no calculation — just the observation that a bijection from a finite set to itself preserves the product. The same argument proves Fermat's Little Theorem as a special case and generalizes to any finite group (as Lagrange's theorem): the order of any element divides the order of the group.