Course contentsShow
← Mathematics
Lesson 2749 of 3,12154. Number TheoryFree lesson

Proof of Euler's Theorem

Prove Euler's Theorem using the multiplicative group of units modulo n and Lagrange's theorem.

Proof of Euler's Theorem

What you'll learn: You'll see why Euler's Theorem holds by connecting it to the structure of the multiplicative group of units modulo n and applying Lagrange's theorem from group theory.

The Core Idea

Euler's Theorem states that if a and n are relatively prime (gcd(a, n) = 1), then:

a^φ(n) ≡ 1 (mod n)

where φ(n) is Euler's totient function counting integers from 1 to n that are relatively prime to n.

Why This Works

The proof relies on viewing the problem through the lens of group theory:

  1. The Multiplicative Group: Consider all integers from 1 to n that are relatively prime to n. These form what's called the multiplicative group of units modulo n, often denoted U(n). This set has exactly φ(n) elements.

  2. Group Properties: When you multiply any two numbers in this set and reduce modulo n, you get another number in the set. The number 1 acts as the identity element, and every element has a multiplicative inverse.

  3. Lagrange's Theorem: From group theory, Lagrange's theorem tells us that for any element g in a finite group of order k, we have g^k = e (where e is the identity).

  4. Applying Lagrange: Since a is relatively prime to n, it belongs to U(n), which has order φ(n). By Lagrange's theorem, raising a to the power φ(n) gives us the identity element 1 (modulo n).

The Beautiful Connection

This proof elegantly shows that Euler's Theorem isn't just a number theory curiosity—it's a natural consequence of the underlying group structure governing modular multiplication.

Key Takeaway: Euler's Theorem follows directly from Lagrange's theorem applied to the multiplicative group of units modulo n, which has exactly φ(n) elements.