Questions: Euler's Theorem

Question 1

You want to apply Euler's theorem to compute 6^20 (mod 9). You check that φ(9) = 6. Does the theorem guarantee 6^6 ≡ 1 (mod 9)?

• A. Yes — φ(9) = 6 and 6 < 9, so the theorem applies
• B. No — gcd(6, 9) = 3 ≠ 1, so 6 is not in (ℤ/9ℤ)* and the theorem does not apply
• C. Yes — Euler's theorem applies to any integer and any modulus
• D. No — the theorem only applies when n is prime

Answer: (B)

Euler's theorem requires gcd(a, n) = 1. Here gcd(6, 9) = 3, so 6 shares a factor with 9. The element 6 is not in the multiplicative group (ℤ/9ℤ)*, and the theorem gives no guarantee. Checking: 6^6 = 46656 = 5184 × 9, so 6^6 ≡ 0 (mod 9) — not 1. The coprimality condition is not a technicality; it defines exactly which elements the theorem covers.

Question 2

Euler's theorem states a^φ(n) ≡ 1 (mod n) when gcd(a,n) = 1. Which of the following best explains WHY the exponent φ(n) appears specifically?

• A. φ(n) is the smallest integer k such that a^k ≡ 1 (mod n) for every a coprime to n
• B. The elements coprime to n form a multiplicative group of order φ(n), and by Lagrange's theorem any element raised to the group order equals the identity
• C. φ(n) is defined so that a^φ(n) ≡ 1 always holds, making the theorem circular
• D. It follows directly from the prime factorization of n without needing group theory

Answer: (B)

The integers coprime to n form the multiplicative group (ℤ/nℤ)*, which has exactly φ(n) elements. Lagrange's theorem states that the order of any element divides the order of the group. So the sequence a, a², a³, ... must return to 1 within φ(n) steps. Note that φ(n) need not be the *smallest* such exponent — the order of a divides φ(n) but may be smaller. The group-theoretic structure explains why φ(n) works for every coprime a simultaneously.

Question 3

Euler's theorem states a^φ(n) ≡ 1 (mod n) for most integers a and most positive integers n.

• T. True
• F. False

Answer: False

The theorem requires the additional condition gcd(a, n) = 1. When a shares a common factor with n, the element a is not in the multiplicative group (ℤ/nℤ)* and the conclusion fails. For example, gcd(2, 10) = 2 ≠ 1, and 2^4 = 16 ≡ 6 (mod 10), not 1. The coprimality condition is essential — omitting it is the most common error when applying the theorem.

Question 4

Fermat's Little Theorem (a^(p−1) ≡ 1 (mod p) for prime p with gcd(a,p) = 1) is a special case of Euler's Theorem.

• T. True
• F. False

Answer: True

When n = p is prime, every integer from 1 to p−1 is coprime to p, so φ(p) = p − 1. Substituting into Euler's theorem gives a^(p−1) ≡ 1 (mod p), which is exactly Fermat's Little Theorem. Euler's theorem is the generalization that covers any modulus n, not just primes — it was specifically designed to extend the result beyond the prime case.

Question 5

Why is the condition gcd(a, n) = 1 necessary for Euler's theorem, and what goes wrong when it fails?

Model answer: The proof relies on the elements coprime to n forming a multiplicative group (ℤ/nℤ)*. A group requires every element to have a multiplicative inverse mod n — which is only possible when gcd(a, n) = 1. When gcd(a, n) > 1, a has no inverse mod n, it cannot be in the group, and repeated multiplication by a does not cycle back to 1. For instance, multiplying by 2 mod 6 cycles through 2, 4, 2, 4, ... — never reaching 1. The Lagrange's theorem argument that guarantees a^φ(n) ≡ 1 simply does not apply outside the group.

In RSA, this is exactly why the plaintext message m must satisfy gcd(m, pq) = 1. For large primes p and q, this holds for every m < pq that isn't a multiple of p or q — an astronomically rare failure case in practice. Understanding why the coprimality condition is necessary, not just a side constraint, is what separates mechanical use of the theorem from genuine understanding of how it works.