youproof.orgDeep Math. Human Access.

Bizonyítás

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

[a1]n[a2]n[a3]n⋮[ak]n\begin{aligned}&[a_1]_n \\ &[a_2]_n \\ &[a_3]_n \\ &\vdots \\ &[a_k]_n \end{aligned}

A tétel szövege alapján tegyük fel, hogy nn-nek létezik legalább egy Fermat-tanúja. Legyen ez például az alábbi redukált maradékosztály:

[b]n[b]_n

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

[b]n⊙[a1]n[b]n⊙[a2]n[b]n⊙[a3]n⋮[b]n⊙[ak]n\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[b]_n egy redukált maradékosztály, továbbá az [a1]n[a_1]_n, [a2]n[a_2]_n, ..., [ak]n[a_k]_n 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 [a1]n[a_1]_n, [a2]n[a_2]_n, ..., [ak]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 nn-hez létezik legalább egy Fermat-tanú, akkor ennek a segítségével minden Fermat-nemtanúhoz elő tudunk állítani egy-egy újabb Fermat-tanút. Más szavakkal a redukált maradékosztályok között minimum annyi Fermat-tanú van, mint ahány Fermat-nemtanú. A redukált maradékosztályoknak tehát valóban legalább a fele Fermat-tanú.

∎