Euler's Phi Function: The Art of Counting Coprimes

 One of my favorite moments in teaching number theory is when students first encounter Euler's phi function. "Wait," they say, "we're counting numbers based on whether they share factors?" Yes! And this simple idea unlocks some of the most beautiful results in mathematics.

What is Euler's Phi Function?

Euler's phi function (also called Euler's totient function), denoted φ(n), counts how many positive integers less than or equal to n are relatively prime to n (i.e., share no common factors except 1 with n).

φ(n) = |{k : 1 ≤ k ≤ n and gcd(k, n) = 1}|

Examples 

Example 1: φ(10)

Numbers from 1 to 10: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Which are coprime to 10?


1: gcd(1, 10) = 1 ✓

2: gcd(2, 10) = 2 ✗

3: gcd(3, 10) = 1 ✓

4: gcd(4, 10) = 2 ✗

5: gcd(5, 10) = 5 ✗

6: gcd(6, 10) = 2 ✗

7: gcd(7, 10) = 1 ✓

8: gcd(8, 10) = 2 ✗

9: gcd(9, 10) = 1 ✓

10: gcd(10, 10) = 10 ✗


So φ(10) = 4 (the numbers 1, 3, 7, 9)

Example 2: φ(7)

Since 7 is prime, every number from 1 to 6 is coprime to 7.

Therefore, φ(7) = 6

Example 3: φ(12)

Numbers coprime to 12: {1, 5, 7, 11}

So φ(12) = 4

The Formula for Prime Powers

For a prime p and positive integer k:

φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1)

Why? Out of p^k numbers, exactly p^(k-1) are divisible by p. Remove those, and you get the count of coprimes.

Example: φ(8) = φ(2³) = 2³ - 2² = 8 - 4 = 4

The coprime numbers are {1, 3, 5, 7}.

The Multiplicative Property

Here's the game-changer: If gcd(m, n) = 1, then φ(mn) = φ(m) · φ(n)

This makes calculations so much easier!

Example: φ(30) = φ(2 × 3 × 5)

Since 2, 3, and 5 are pairwise coprime:

φ(30) = φ(2) · φ(3) · φ(5) = 1 · 2 · 4 = 8

The General Formula

For any n with prime factorization n = p₁^(a₁) · p₂^(a₂) · ... · pₖ^(aₖ):

φ(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/pₖ)

Or equivalently:

φ(n) = n · ∏(1 - 1/p) where the product is over all prime divisors of n.

Example: φ(36)

36 = 2² × 3²

Using the formula:

φ(36) = 36(1 - 1/2)(1 - 1/3) = 36 · (1/2) · (2/3) = 36 · 2/6 = 12

Or using the multiplicative property:

φ(36) = φ(2²) · φ(3²) = (2² - 2¹)(3² - 3¹) = 2 · 6 = 12 ✓

Euler's Theorem: The Crown Jewel

Theorem: If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

This is one of the most powerful results in number theory!

Example: Let's verify for a = 3, n = 10


φ(10) = 4

3⁴ = 81 ≡ 1 (mod 10) ✓


This theorem is the foundation of RSA encryption!

Fermat's Little Theorem: A Special Case

When n = p (prime), φ(p) = p - 1, so Euler's theorem gives us:

a^(p-1) ≡ 1 (mod p) for gcd(a, p) = 1

This is Fermat's Little Theorem – a special case of Euler's result!

Beautiful Properties

Property 1: For n > 2, φ(n) is always even (makes sense – coprimes come in pairs)

Property 2: The sum of φ(d) over all divisors d of n equals n:

Σ φ(d) = n (where d|n)

Example: For n = 6, divisors are {1, 2, 3, 6}

φ(1) + φ(2) + φ(3) + φ(6) = 1 + 1 + 2 + 2 = 6 ✓

Property 3: φ(n) = n - 1 if and only if n is prime

Practice Problem

Question: What is φ(100)?

A) 20 B) 40 C) 50 D) 80

Answer: B) 40

Solution:

100 = 2² × 5²

Method 1: φ(100) = φ(2²) · φ(5²) = (2² - 2¹)(5² - 5¹) = 2 · 20 = 40

Method 2: φ(100) = 100(1 - 1/2)(1 - 1/5) = 100 · (1/2) · (4/5) = 40

Real-World Applications

Cryptography: RSA encryption relies entirely on Euler's phi function and theorem

Clock Arithmetic: Understanding modular arithmetic patterns

Number Theory: Counting primitive roots, analyzing cyclic groups

Computer Science: Hash functions and pseudorandom number generation

Connection to Group Theory

Here's something beautiful: φ(n) gives the order of the multiplicative group (ℤ/nℤ)*.

For students studying abstract algebra, this connects number theory directly to group theory – two seemingly different areas unified by the phi function!

Computing φ(n) Efficiently

For large numbers:

Find prime factorization of n

Apply the formula φ(n) = n · ∏(1 - 1/p)

Use multiplicativity when possible to break into smaller pieces


This is much faster than checking each number individually!

A Challenge Problem

Try finding φ(1001) without calculating each coprime individually!

Solution: 1001 = 7 × 11 × 13

φ(1001) = φ(7) · φ(11) · φ(13) = 6 · 10 · 12 = 720

Why I Love Teaching This

Euler's phi function is where number theory becomes concrete and applicable. Students see how abstract counting problems connect to modern cryptography and computer security. It's pure mathematics with immediate real-world impact!

On my YouTube channel "Maths mastery with Dr. Upasana P Taneja," I regularly explore these connections and work through competition-level problems involving the phi function. Understanding φ(n) opens doors to advanced number theory and its applications in the digital age.

The phi function reminds us that sometimes the most powerful mathematical tools come from asking simple counting questions. How many numbers share no factors with n? This innocent question leads to theorems that secure our online communications!


Count wisely, and the mathematics will reveal its secrets!

Dr. Upasana Pahuja Taneja

Comments

Post a Comment

Popular posts from this blog

The One-Step Subgroup Test: Why Check Three When One Will Do?

  During my years of teaching group theory, I've noticed that students often get overwhelmed when verifying subgroups. They diligently check closure, identity, and inverses separately – which is correct but sometimes unnecessarily tedious. That's when I introduce them to one of my favorite shortcuts: the One-Step Subgroup Test! The Traditional Way vs. The Smart Way Traditional approach: Check three separate conditions Closure under the operation Contains the identity element Contains inverse of every element One-Step Test: Check just ONE condition! The One-Step Subgroup Test Theorem For a non-empty subset H of group G: H is a subgroup of G if and only if for all a, b ∈ H, we have ab⁻¹ ∈ H. That's it! Just one condition to check instead of three. Why Does This Work? The beauty lies in how this single condition automatically ensures all three requirements: Step 1 - Identity: Take any element a ∈ H. Since aa⁻¹ = e must be in H, we get the identity! Step 2 - Inverses: For any a...
Read more

Understanding Groups: A Journey Through Algebraic Structures

  Group theory is one of the most elegant and fundamental branches of abstract algebra, providing a framework for understanding symmetry, structure, and operations across mathematics. At its heart lies the concept of a group, but to truly appreciate groups, we need to understand the algebraic structures that lead up to them. Let's embark on this journey, starting with the simplest structures and building our way up to the rich world of groups. https://youtu.be/YKkfgZWqbfA?si=0Zx-hZegRW7LhuDe Watch this video for Explanation with examples and MCQs.  The Foundation: Semigroup A semigroup is perhaps the most basic algebraic structure we encounter. It consists of a set equipped with a single binary operation that satisfies just one crucial property. Definition A semigroup is a set S together with a binary operation * such that: Associativity: For all a, b, c ∈ S, we have (a * b) * c = a * (b * c) That's it! This single requirement might seem modest, but it captures something funda...
Read more

Cyclic vs Non-Cyclic Groups: The Key Results

 After years of teaching group theory, I've found that students truly understand groups when they grasp the fundamental differences between cyclic and non-cyclic groups. Let me share the most important theorems you need to know! Essential Results on Cyclic Groups Result 1: Every Cyclic Group is Abelian Theorem : If G is cyclic, then G is abelian. Proof : Let G = ⟨g⟩. Any two elements are g^m and g^n. Then g^m · g^n = g^(m+n) = g^(n+m) = g^n · g^m ✓ Important : The converse is FALSE! Not every abelian group is cyclic. Counterexample : V₄ = Z₂ × Z₂ is abelian but NOT cyclic. Result 2: Every Subgroup of a Cyclic Group is Cyclic Theorem : If G is cyclic and H ≤ G, then H is cyclic. Proof Sketch : Let G = ⟨g⟩. If H = {e}, then H is cyclic. Otherwise, take the smallest positive integer m such that g^m ∈ H. Then H = ⟨g^m⟩. Example : In Z₁₂ = ⟨1⟩: H = {0, 4, 8} = ⟨4⟩ is cyclic H = {0, 3, 6, 9} = ⟨3⟩ is cyclic Result 3: Classification of Cyclic Groups Theorem : Every cyclic g...
Read more