Tegyük fel, hogy összesen k darab olyan modulo n redukált maradékosztály van, amely nem Fermat-tanú. Legyenek például ezek az alábbiak, amelyek tehát páronként különböző redukált maradékosztályok:

\begin{aligned}&[a_1]_n \\ &[a_2]_n \\ &[a_3]_n \\ &\vdots \\ &[a_k]_n \end{aligned}

Tegyük fel továbbá, hogy n-nek létezik legalább egy Fermat-tanúja a redukált maradékosztályok között. Legyen ez például az alábbi redukált maradékosztály:

[b]_n

Amennyiben ezzel a [b]_n Fermat-tanúval végigszorozzuk a fenti k darab nem Fermat-tanút, akkor az alábbi maradékosztályokat kapjuk, amelyek a 23.4. Lemma alapján szintén mindannyian Fermat-tanúk és redukált maradékosztályok:

\begin{aligned}[b]_n &\odot [a_1]_n \\ [b]_n &\odot [a_2]_n \\ [b]_n &\odot [a_3]_n \\ &\vdots \\ [b]_n &\odot [a_k]_n \end{aligned}

Mivel a szorzáshoz használt [b]_n egy redukált maradékosztály, továbbá az [a_1]_n, [a_2]_n, …, [a_k]_n redukált maradékosztályok páronként különbözőek voltak, emiatt a 23.5. Lemma alapján az eredményül kapott szorzatok is páronként különböző redukált maradékosztályok. Ráadásul ezek az [a_1]_n, [a_2]_n, …, [a_k]_n redukált maradékosztályoktól is biztosan különböznek, hiszen azok nem is voltak Fermat-tanúk.

Ha tehát teljesül a tétel feltétele, miszerint n-hez létezik legalább egy Fermat-tanú a redukált maradékosztályok között, akkor minden nem Fermat-tanúhoz elő tudunk állítani egy-egy újabb Fermat-tanút szintén a redukált maradékosztályok között. Más szavakkal a redukált maradékosztályok között minimum annyi Fermat-tanú van, mint ahány nem Fermat-tanú, ráadásul létezhetnek további Fermat-tanúk is. A modulo n redukált maradékosztályoknak tehát valóban legalább a fele Fermat-tanú.