---
title: "Fermat's Little Theorem and Euler's Theorem"
description: "Prove that raising a unit to the size of the unit group returns one, and use it to shortcut enormous modular powers."
canonical: https://lightmysky.com/learn/mathematics/fermats-little-theorem-and-eulers-theorem-mt_7wW4z4Eidx
source: https://lightmysky.com/learn/mathematics/fermats-little-theorem-and-eulers-theorem-mt_7wW4z4Eidx.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Fermat's Little Theorem and Euler's Theorem

Prove that raising a unit to the size of the unit group returns one, and use it to shortcut enormous modular powers.

Subject: Mathematics · Area: Number Theory · Ages 20 to 21
Page: https://lightmysky.com/learn/mathematics/fermats-little-theorem-and-eulers-theorem-mt_7wW4z4Eidx

## Ready when they can

- Prove Fermat's little theorem by permuting the nonzero residues
- Compute Euler's totient function and state the general theorem
- Reduce a huge exponent modulo the totient before computing the power

## Lesson: Shortcuts for giant modular powers

Fermat's little theorem says a to the power (p minus 1) leaves remainder 1 modulo p, for prime p not dividing a. So 2 to the power 10 is 1 modulo 11. The proof permutes the nonzero residues: multiplying them all by a just reshuffles the list.

**Example.** Euler widened the idea with the totient. Phi of n counts numbers from 1 to n that share no factor with n: phi of 9 is 6, namely 1, 2, 4, 5, 7, 8, and phi of 12 is 4. His theorem says a to the phi of n is 1 modulo n whenever a and n are coprime.

That turns huge powers into small ones. For 3 to the 100th modulo 7, phi of 7 is 6, and 100 equals 96 plus 4. So the power reduces to 3 to the 4th, which is 81, and 81 modulo 7 is 4.

**Tip.** Reduce the exponent modulo the totient, never modulo n itself. Then finish with fast squaring: square down the binary form of the exponent, multiplying by the base only at set bits. A million multiplications shrink to about twenty steps.

**Recap.** Spot the prime or the totient, shrink the exponent, and compute the small power that remains.

## Practice

14 questions on this page, each with its working shown.

## Needs first

- [Linear Congruences and the Chinese Remainder Theorem](https://lightmysky.com/learn/mathematics/linear-congruences-and-the-chinese-remainder-theorem-mt_J9_RMpwcRX)
- [Homomorphisms, Cosets and Lagrange's Theorem](https://lightmysky.com/learn/mathematics/homomorphisms-cosets-and-lagranges-theorem-mt_yKiZ8sg7yN)

## Opens up

- [Public-Key Cryptography and Key Exchange](https://lightmysky.com/learn/computing/public-key-cryptography-and-key-exchange-mt_AHCtrer4eh)
- [Primitive Roots and the Units Modulo n](https://lightmysky.com/learn/mathematics/primitive-roots-and-the-units-modulo-n-mt_KwTDckkMze)