Skip to main content
MathidiaMathematics Academy
Number theory and cryptography
Lesson 49 of 75
Challenge

Fermat and Euler theorems

Objective. Compute powers modulo integers.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Fermat's little theorem states that for prime p and integer a not divisible by p, a^(p−1) ≡ 1 (mod p), while Euler's generalisation uses φ(n), the count of integers up to n coprime to n, so that a^φ(n) ≡ 1 (mod n) whenever gcd(a,n) = 1. These theorems let large modular powers be reduced by working with the exponent modulo p−1 or φ(n) rather than computing huge powers directly. For example, to compute 3^100 mod 7, since 7 is prime, 3^6 ≡ 1 (mod 7), so 3^100 = 3^(6×16+4) ≡ 3^4 ≡ 81 ≡ 4 (mod 7).

Worked example

Using Fermat's theorem, compute 2^10 mod 11.

compute 2^10 mod 11
Illustrated card showing compute 2^10 mod 11
  1. 1Fermat: since 11 is prime, 2^10 ≡ 1 (mod 11)
  2. 2This holds for any a coprime to 11
  3. 3Here a = 2 is coprime to 11
  4. 4So 2^10 mod 11 = 1

Answer: 1

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students apply Fermat's little theorem to a composite modulus directly, treating a^(n−1) ≡ 1 (mod n) as always true; it only holds for prime moduli, so composite cases require Euler's theorem with φ(n) instead.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard