2 minute read Introductory

From the archive (2024). Corrected in October 2026; see the note at the end.

This post is a gentle introduction to some well-known theorems in elementary number theory.

Motivation

In my first university course on proofs, Accelerated Proofs and Problem Solving, we were asked to find \(a\) such that

\[3^{124} \equiv a \pmod{100}.\]

The answer is \(81\). I found it by computing successive powers of \(3\) until I “discovered” that

\[3^{20} \equiv 1 \pmod{100},\]

so \(3^{124} = (3^{20})^6 \cdot 3^4 \equiv 3^4 = 81\). Is there a general principle behind this?

Euler’s theorem

Euler’s theorem states that

\[a^{\varphi(n)} \equiv 1 \pmod{n}\]

for every integer \(a\) coprime to \(n\). Here \(\varphi(n)\) is Euler’s totient function, which counts the integers in \(\{1, \ldots, n\}\) that are coprime to \(n\). It can be computed from the prime factorisation of \(n\):

\[\varphi(n)=n \prod_{p\,\mid\,n}\left(1-\frac{1}{p}\right).\]

For example, \(\varphi(100)=100 \cdot \tfrac{1}{2} \cdot \tfrac{4}{5}=40\).

When \(n = p\) is prime, \(\varphi(p) = p - 1\), and Euler’s theorem becomes Fermat’s little theorem:

\[a^{p-1} \equiv 1 \pmod{p}.\]

The Carmichael function

Euler’s theorem guarantees \(3^{40} \equiv 1 \pmod{100}\), but we found the smaller exponent \(20\). The Carmichael function \(\lambda(n)\) is the smallest positive integer \(m\) such that

\[a^{m} \equiv 1 \pmod{n}\]

for every integer \(a\) coprime to \(n\). Indeed \(\lambda(100)=20\).

Because \(\lambda(n)\) is the best possible exponent in Euler’s theorem, it is also called the reduced totient function. It always divides \(\varphi(n)\) (see the exercises).

Carmichael numbers

Fermat’s little theorem suggests a primality test: declare \(n\) prime if

\[b^{n-1} \equiv 1 \pmod{n}\]

for every \(b\) coprime to \(n\).

The test fails for the first time at \(n = 561\): it satisfies \(b^{560} \equiv 1 \pmod{561}\) for every \(b\) coprime to \(561\), yet \(561 = 3 \cdot 11 \cdot 17\) is not prime. Composite numbers with this property are called Carmichael numbers, and \(561\) is the smallest.

Korselt’s criterion characterises them: a composite number \(n\) is a Carmichael number if and only if \(n\) is square-free and \(p-1 \mid n-1\) for every prime divisor \(p\) of \(n\).

For \(561\): it is square-free, and \(2 \mid 560\), \(10 \mid 560\) and \(16 \mid 560\). Hence \(561\) is a Carmichael number.

Exercises

  • Show that \(\varphi(p)=p-1\) for a prime \(p\), and deduce Fermat’s little theorem from Euler’s theorem. (Undergraduate, years 1–2)
  • Define the exponent and the order of a finite group. Show that \(\lambda(n)\) divides \(\varphi(n)\). (Hint: \(\lambda(n)\) is the exponent of the group \((\mathbb{Z}/n\mathbb{Z})^\times\).)
  • Write a Python program that prints the first \(10\) Carmichael numbers.

Changes on 25 October 2026

What was wrong. Nothing of substance.

What changed. The motivating example now shows the calculation, \(3^{124} = (3^{20})^6 \cdot 3^4 \equiv 81\), one exercise has a hint, and the WolframAlpha link is simpler. Previously titled “Euler’s Totient function, Reduced Totient function and Carmichael Number”.

You may also enjoy