Malá Fermatova věta

Malá Fermatova věta je věta z teorie čísel, která říká, že pro každé prvočíslo p nesoudělné s číslem a platí:

a^{p-1} = 1 \; v \; Z_{p}

Důkaz

Věta je speciálním případem Eulerovy věty, která byla dokázána, proto i tato věta platí.

Příklad:

Kolik je 7^{35} \; v \; Z_{17}?

gcd(7, 17) = 1
7^{35} = 7^{16} \cdot 7^{16} \cdot 7^{3} = 1 \cdot 1 \cdot 7^{2} \cdot 7 = 49 \cdot 7 = -2 \cdot 7 = -14 = 3 \; v \; Z_{17}
PDF
– Pavel Mička
Zakladatel a administrátor stránek Algoritmy.net
Hodnocení (4): 5

Přečtěte si také

Diskuse





Pavel Mička15.5.2010
Díky, překlep opraven :-)
Martin15.5.2010
V příkladu je chybka. Místo 716 tam má být 7 na 16.
a23.3.2010
Urcite ten dukaz mel a byl tak na dva okraje v Diofantove knize ;)