Małe twierdzenie Fermata

Małe Twierdzenie Fermata

Małe twierdzenie Fermata (MTF) jest fundamentalnym twierdzeniem w teorii liczb, sformułowanym przez Pierre’a de Fermata. Twierdzenie to stanowi podstawę dla testu pierwszości Fermata i można je wyrazić w następujący sposób:

Jeśli $p$ jest liczbą pierwszą, to dla każdej liczby całkowitej $a$ , liczba $a^p – a$ jest podzielna przez $p$ :

$a^p – a \equiv 0 \pmod p.$

Jeśli $p$ jest liczbą pierwszą, a $a$ jest taką liczbą całkowitą, że $a$ i $p$ są względnie pierwsze, to $a^{p-1} – 1$ dzieli się przez $p$ :

$a^{p-1} \equiv 1 \pmod p.$

Dowody Małego Twierdzenia Fermata

1. Dowód z twierdzeniem Eulera

Jeżeli $p$ jest liczbą pierwszą, która nie dzieli $a$ , to $p$ jest względnie pierwsze z $a$ . Z twierdzenia Eulera wynika, że twierdzenie jest prawdziwe.

2. Dowód kombinatoryczny

Rozpatrując kolorowanie koła podzielonego na $p$ części przy użyciu $a$ kolorów, mamy $a^p$ kolorowań. Kolorowania z co najmniej dwoma kolorami można obracać, co prowadzi do zestawów po $p$ kolorowań. W przypadku, gdy wykorzystujemy tylko jeden kolor, nie ma możliwości uzyskania takich samych kolorowań w obrocie. Dlatego:

$a^p = pn + a.$

Co dowodzi, że $p$ dzieli $a^p – a$ .

3. Dowód z teorii grup

Multiplikatywna grupa $\mathbb Z_p^*$ ma rząd $p-1$ . Dla elementu $a$ tej grupy, jego rząd $k$ dzieli $p-1$ . Oznacza to:

$a^{p-1} \equiv 1 \pmod p.$

4. Dowód indukcyjny

Zakładamy, że twierdzenie jest prawdziwe dla $a = 1$ i przyjmujemy indukcyjnie, że jest prawdziwe dla $a \geq 1$ . Rozważając rozwinięcie dwumianowe $(a+1)^p$ , dowodzimy, że:

$(a+1)^p \equiv a + 1 \pmod p.$

W rezultacie, na mocy indukcji, mamy:

$a^p \equiv a \pmod p.$

Podsumowując, Małe Twierdzenie Fermata jest kluczowym rezultatem w teorii liczb, z różnorodnymi dowodami, które potwierdzają jego prawdziwość i zastosowanie w testach pierwszości.

Najnowsze aktualności:

Małe twierdzenie Fermata