Malá Fermatova věta
Z Wikipedie, otevřené encyklopedie
Malá Fermatova věta je matematická věta, která tvrdí, že pro každé prvočíslo p a každé celé číslo a takové, že p nedělí a, platí
.
Věta je nazvána podle francouzského matematika Pierra de Fermat (1601–1665); přívlastek malá ji odlišuje od Velké Fermatovy věty.
[editovat] Důkaz
Nechť P je množina přirozených čísel, Pp je množina prvočísel a Z množina celých čísel a m, n ∈ P, p ∈ Pp, a, k ∈ Z. Pak pro každé a, p takové, že
∉ Z platí:
∈ Z (z0)
Podmínka
∉ Z zároveň vymezuje definiční obor všech celých čísel a, pro která věta platí.
Toto je pouze jiný způsob zápisu Malé Fermatovy věty a vlastně říká, že ap − 1 − 1 je dělitelné beze zbytku p, tj. že výsledek padne do oboru celých čísel, nebo také, že libovolné celé číslo a umocněné na p-1 pro libovolné prvočíslo má zbytek po dělení p roven 1 pro každé a, p nesoudělné. Pro vlastní důkaz potřebujeme znát některé vlastnosti kongruence a několik Lemma. Kongruence je také ekvivalence, tj. je reflexivní (e1), symetrická (e2) a tranzitivní (e3). Tj. pro každé n ∈ P, a,b,c ∈ Z platí:
(e1)- je-li
, pak
(e2) - je-li
a
, pak
(e3)
Ekvivalence a Lemma uvedená níže jsou ponechána bez důkazu, nebo je důkaz jenom naznačený. Laskavý čtenář nahlédne, že většina důkazů je triviální.
Lemma0: Nechť pro každé a, b, c, d ∈ Z existuje n ∈ P takové že
a 
pak jednotlivé členy kongruencí lze vždy rozepsat jako součet čísla děliteného n a celočíselného zbytku po dělení
- a = o + k (p1)
- b = q + k (p2)
- c = p + l (p3)
- d = r + l (p4)
kde k, l jsou celočíselné zbytky po dělení n a o, q, p, r jsou čísla soudělná s n.
Zápis
je přitom rovnocenný s
∈ Z, což plyne přímo z definice kongruence (z1)
Lemma1,2: Nechť pro každé a, b, c, d ∈ Z existuje n ∈ P takové že
a 
- pak platí
(1) Dk: použijte zápis (z1) a rozklady (p1-4) - a také
(2) Dk: použijte zápis (z1) a rozklady (p1-4)
Lemma3,4,5: Nechť pro každé a, b, r ∈ Z a k ∈ P existuje n ∈ P takové že
- pak platí
(3) Dk: použijte zápis (z1) - a také
(4) Dk: použijte zápis (z1), platí jak pro soudělná i nesoudělná r s n viz také Lemma6 - a také
(5) Dk: Použijte Lemma2
Lemma6 o neutrálním prvku: Nechť pro každé a ∈ Z a n ∈ P existuje b ∈ Z takové že
a nechť existuje i ∈ Z takové, že je celočíselným násobkem n, tj. existuje x ∈ Z takové, že : i = xn. Přičtením takového čísla k libovolné straně se kongruence nezmění, a takových i existuje dokonce neomezené množství:
(6) Dk: použijte zápis (z1)
Pozn.: Obdobné Lemma pro násobení jedné strany kongruence ale neplatí, tj. není pravda, že
(6) Dk sporem: předpokládejte, že výraz platí a použijte zápis (z1)
Lemma7 o binomických koeficientech: Nechť p ∈ Pp a m ∈ P jsou kombinační čísla binomického koeficientu Pascalova trojúhelníku taková že p > m > 0, pak platí, že
∈ Z (7)
to jest, že pro libovolný binomický koeficient, a pro libovolné prvočíslo nahoře
platí, že je celočíselný i po dělení prvočíslem p.
Důkaz provedeme úvahou a indukcí: Nejprve rozvineme formální zápis.

- 1. Pro m = 1 věta platí a důkaz je triviální, protože
zlomek vynásobím p a vykrátím p!
Výsledek je dělitelný p, 1! a je proto celočíselný (7.1)
- 2. Pro m = 2 věta platí, protože
zlomek vynásobím p(p-1) a vykrátím p!
Výsledek je zřejmě dělitelný p, 2! a je proto celočíselný, protože, je-li p prvočíslo, je liché a nejbližší mižší číslo tj. (p-1) v rozvoji p(p-1) nutně musí být sudé a tedy dělitelné dvěma (7.2)
- 3. Pro m = 3 věta platí, protože
zlomek vynásobím p(p-1)(p-2) a vykrátím p!
Výsledek je zřejmě dělitelný p, 3! a je proto celočíselný, protože, v rozvoji p(p-1)(p-2) je (p-1) dělitelné 2 (7.2) a (p-1) nebo (p-2) nutně musí být dělitelné 3, protože p je prvočíslo, z předpokladu je p>3, tj. není dělitelné 3 a na číselné ose je každé třetí číslo dělitelné 3, a může tedy stát od prvočísla p nejdále o dvě pozice (7.3). Toto je i návod, jak pokračovat dále, v každém dalším kroku bude součin činitelů p(p-1)(p-2)…(p-m-1) delší o jeden člen a faktoriál bude také o jeden člen delší.
- 4. Předpokládejme, že věta platí pro m = 1, 2, …, j, …, k, pak platí:
Dá se ukázat, že na úseku A číselné osy celých čísel A = {(p-(k-1)), …, (p-(j-1)), …, (p-1), p} existuje zobrazení (není vzájemně jednoznačné) množiny B = {1, 2, …, x, …, k}, tj. členů faktoriálu k! do množiny A, a že tedy vždy existuje nějaké x ∈ B takové že, platí:
∈ Z pro nějaké j ∈ Z takové, že k > j > 1
- 5. Je zřejmé, že pokud věta platí pro k, bude platit i pro každého následníka k+1.
Vlastní Dk Malé Fermatovy věty: Nejprve kongruenci převedeme na ekvivalentní tvar (Lemma3)
.
Důkaz poté použije matematickou indukci:
- 1. Pro a = 1 věta platí a důkaz je triviální, protože 1p − 1 / p = 0 a 0 ∈ Z, protože 0 je soudělná s kažým p ∈ Pp
- 2. Předpokládejme, že věta platí pro a = 1, 2, …, k, a dokažme, že platí i pro a = k+1, tedy
Předpoklad:
(f1)
Indukce:
(f2)
- 3. Indukční předpoklad (f2) nejprve převedeme dle (e1), tj. napravo napíšeme to, co je i nalevo. Podle binomické věty platí: :
(f3). Všechna kombinační čísla v této kongruenci jsou celočíselná a dělitelná p (Lemma7), podle Lemma6 je proto možné všechny členy s kombinačními čísly vyrušit, tedy:
ekvivalence
je kongruentní z indukčního předpokladu a Lemma3, a lze proto dle Lemma4 přičíst k oběma stranám konstantu +1 a dle (e3) dosadit napravo pravou stranu výrazu. Proto platí, že
, což je ekvivalentní zápis k (f2) dle Lemma3. Tímto je kongruence dokázána pro všechna přirozená čísla.- 4. Pro každé záporné číslo -a ∈ Z a každé prvočíslo p ∈ Pp platí, že
- ( − a)p − 1 = (a)p − 1 (8)
Dk: ( − a)p − 1 = ( − 1)p − 1(a)p − 1 a ( − 1)p − 1 = 1 pro všechny sudé mocnitele, a protože každé prvočíslo p ≠ 2 je liché, je nutně p-1 sudé, a všechny sudé mocniny jsou kladné. Pro případ p = 2 je kongruence zjednodušená na případ
kde p = 2 (9)
z předpokladu, že -a a p jsou nesoudělná a p je sudé, musí být -a liché. Hodnota ( − a)1 − 1 je sudá, a proto dělitelná 2.
Tímto je je věta dokázána pro všechna celá čísla z oboru definičních hodnot.
[editovat] Literatura
- Prof. RNDr. Marie Demlová, CSc.: Diskrétní matematika a logika Přednáška z 5.12.2005
- Jaroslav Blažek, Emil Calda, Blanka Kussová: Algebra a teoretická aritmetika I., SPN Praha 1979


