Euler's Theorem: Formula, Examples and Applications

Euler's Theorem connects coprime numbers with modular powers. It states that if a and n are positive integers with gcd(a, n) = 1, then a raised to the power φ(n) leaves remainder 1 when divided by n. This page explains the theorem, Euler's totient function, exponent reduction, conditions, examples and common calculation methods.

On this page

What Is Euler's Theorem?

For positive integers a and n with gcd(a, n) = 1, Euler's Theorem states that a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.

The value φ(n) counts the positive integers from 1 to n that are relatively prime to n. The theorem allows powers of a to be reduced in modular calculations. For example, since φ(10) = 4 and gcd(3, 10) = 1, 3^4 ≡ 1 (mod 10).

Euler's Theorem Formula & Tricks

Important Formulas

Euler's theorem formula
If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

The remainder of a raised to φ(n) is 1 when a and n are coprime.

Euler totient for a prime
φ(p) = p − 1

If p is prime, every integer from 1 to p − 1 is coprime to p.

Euler totient for a prime power
φ(p^k) = p^k − p^(k−1) = p^k(1 − 1/p)

This gives the count of integers up to p^k that are relatively prime to p^k.

Euler totient using prime factors
If n = p₁^a₁p₂^a₂...pᵣ^aᵣ, then φ(n) = n(1 − 1/p₁)(1 − 1/p₂)...(1 − 1/pᵣ)

Use each distinct prime factor of n once in the product.

Quick Tricks

Reduce the exponent modulo φ(n)

When gcd(a, n) = 1, divide the exponent by φ(n) and use the remainder. If the remainder is r, then a^m ≡ a^r (mod n), with the case r = 0 treated as a^φ(n).

Example: To find 3^100 mod 7, φ(7) = 6 and 100 leaves remainder 4 on division by 6. Therefore, 3^100 ≡ 3^4 = 81 ≡ 4 (mod 7).
Calculate φ(n) from distinct prime factors

Factor n first, then apply φ(n) = n multiplied by (1 − 1/p) for every distinct prime factor p.

Example: For n = 60 = 2² × 3 × 5, φ(60) = 60(1 − 1/2)(1 − 1/3)(1 − 1/5) = 16.
Check coprimality before applying the theorem

Euler's Theorem cannot be applied directly if gcd(a, n) is not 1. A common factor between the base and modulus invalidates the theorem's required condition.

Example: For a = 2 and n = 8, gcd(2, 8) = 2. Thus, the statement 2^φ(8) ≡ 1 (mod 8) cannot be used; in fact, 2^4 ≡ 0 (mod 8).

Euler's Theorem Concepts

Condition and statement of Euler's Theorem

Euler's Theorem applies only when the base and modulus are coprime: gcd(a, n) must equal 1.

For n > 1, if a and n have no common factor other than 1, then a^φ(n) ≡ 1 (mod n). The result concerns the remainder after division by n, not equality as ordinary integers.

Example: Since gcd(7, 15) = 1 and φ(15) = 8, 7^8 ≡ 1 (mod 15).

Finding Euler's totient function

Euler's totient function φ(n) is the number of integers from 1 through n that are coprime to n.

For n = p^k, use φ(p^k) = p^k − p^(k−1). For a general factorisation, use φ(n) = n∏(1 − 1/p), where the product is over the distinct prime divisors p of n.

Example: The divisors of 12 are not all counted; the numbers 1, 5, 7 and 11 are coprime to 12. Hence, φ(12) = 4.

Reducing large powers modulo n

If gcd(a, n) = 1, a large exponent can be reduced using the cycle length φ(n).

If m = qφ(n) + r, then a^m = (a^φ(n))^q a^r ≡ a^r (mod n). When r = 0, use a^m ≡ 1 (mod n), rather than replacing the power by a^0 during a modular-cycle calculation.

Example: For 7^123 mod 10, φ(10) = 4 and 123 = 4 × 30 + 3. Therefore, 7^123 ≡ 7^3 = 343 ≡ 3 (mod 10).

When Euler's Theorem does not apply

If gcd(a, n) ≠ 1, Euler's Theorem cannot be used directly.

The condition is essential because the proof and congruence depend on multiplication by a being invertible modulo n. In such cases, simplify powers by direct modular calculation or use another method appropriate to the factorisation of the modulus.

Example: For 6^5 mod 9, gcd(6, 9) = 3, so Euler's Theorem is not directly valid. Directly, 6² = 36 ≡ 0 (mod 9), so 6^5 ≡ 0 (mod 9).

Euler's Theorem Video Lessons

Watch short topic-wise lessons for quick revision.

14 Lessons
Lesson 1 of 14 Quick Revision

Remainder Tricks: Fermat and Euler

Learn how Fermat’s pattern and Euler’s approach simplify remainder calculations for powers, including the key conditions and steps needed to apply these methods accurately.

Continue with more lessons and practice in PrepShots.Watch More in App - Start ₹1 Trial →
More Euler's Theorem Lessons Scroll to explore →

Practice Euler's Theorem Questions

Practise published questions related to this topic.

1Find the least number which leaves remainder 3 when divided by 5, 7, and 8.→ 262P8 is divisible by 4. Which of the following cannot be the value of P?→ 3What is the largest 2 digit number which is exactly divisible by both 2 and 7?→ 4Find the maximum number of students among whom 198 chips and 330 toffees can be distributed such that each student gets the same number of each.→ 5Find the largest number that divides 555, 703, 999 and 1147 leaving the same remainder in each case.→ 6If the ratio of two numbers is 2 : 5, and their HCF is 29, then their LCM is:→ 7What is the square root of 10201?→ 8Which of the following numbers is divisible by 11?→ 9Which of the following number is NOT divisible by 6?→ 10Six bells commence ringing together and ring at intervals of 4, 8, 12, 16, 20 and 24 seconds respectively. In 18 minutes, how many times do they ring together? (including the first ringing together at commencement)→

Euler's Theorem Quick Quiz

Attempt 5 questions and check your score instantly.

Quick Revision Notes

Euler's Theorem Revision Points

Use these rules for quick revision of the theorem and its applications.

  • Euler's Theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n).
  • φ(p) = p − 1 for a prime p.
  • φ(p^k) = p^k − p^(k−1).
  • For n with distinct prime factors p₁, p₂, ..., φ(n) = n∏(1 − 1/pᵢ).
  • Check gcd(a, n) = 1 before reducing an exponent using φ(n).
  • If m = qφ(n) + r, then a^m ≡ a^r (mod n) for a coprime to n.
  • If the base and modulus are not coprime, Euler's Theorem cannot be applied directly.

Euler's Theorem FAQs

What is the formula for Euler's Theorem?

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function.

What is φ(20), and how is it calculated?

Since 20 = 2² × 5, φ(20) = 20(1 − 1/2)(1 − 1/5) = 8.

Find 2^100 mod 9 using Euler's Theorem.

gcd(2, 9) = 1 and φ(9) = 6. Since 100 leaves remainder 4 when divided by 6, 2^100 ≡ 2^4 = 16 ≡ 7 (mod 9).

Can Euler's Theorem be applied to 4^k mod 12?

No. gcd(4, 12) = 4, not 1, so Euler's Theorem does not apply directly.

What is the difference between Euler's Theorem and Fermat's Little Theorem?

Euler's Theorem uses any modulus n with gcd(a, n) = 1: a^φ(n) ≡ 1 (mod n). Fermat's Little Theorem is the prime-modulus case: if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p).

What happens when the exponent is a multiple of φ(n)?

If gcd(a, n) = 1 and m is a positive multiple of φ(n), then a^m ≡ 1 (mod n). For example, 3^8 ≡ 1 (mod 10) because φ(10) = 4.

Continue learning Euler's Theorem on PrepShots

Continue on PrepShots