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í

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

Věta je nazvána podle francouzského matematika Pierra de Fermat (16011665); 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 \frac{a}{p} ∉ Z platí:

\frac{a^{p-1} -1}{p} ∈ Z (z0)

Podmínka \frac{a}{p} ∉ 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í:

a \equiv a \pmod n (e1)
je-li a \equiv b \pmod n, pak b \equiv a \pmod n (e2)
je-li a \equiv b \pmod n a b \equiv c \pmod n, pak a \equiv c \pmod n (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 \equiv b \pmod n a c \equiv d \pmod n

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 a \equiv b \pmod n je přitom rovnocenný s \frac{a -b}{n} ∈ 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 \equiv b \pmod n a c \equiv d \pmod n
pak platí (a + c) \equiv (b + d) \pmod n (1) Dk: použijte zápis (z1) a rozklady (p1-4)
a také (ac) \equiv (bd) \pmod n (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

a \equiv b \pmod n
pak platí ra \equiv rb \pmod n (3) Dk: použijte zápis (z1)
a také (r + a) \equiv (r + b) \pmod n (4) Dk: použijte zápis (z1), platí jak pro soudělná i nesoudělná r s n viz také Lemma6
a také a^k \equiv b^k \pmod n (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 \equiv b \pmod n

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í:

a + i \equiv b \pmod n (6) Dk: použijte zápis (z1)

Pozn.: Obdobné Lemma pro násobení jedné strany kongruence ale neplatí, tj. není pravda, že

ai \equiv b \pmod n (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

\frac{1}{p} \cdot {p \choose m} ∈ Z (7)

to jest, že pro libovolný binomický koeficient, a pro libovolné prvočíslo nahoře {p \choose m} platí, že je celočíselný i po dělení prvočíslem p.

Důkaz provedeme úvahou a indukcí: Nejprve rozvineme formální zápis.

\frac{1}{p} \cdot {p \choose m} = \frac{1}{p} \cdot \frac{p!}{m!(p-m)}
1. Pro m = 1 věta platí a důkaz je triviální, protože
\frac{p!}{1!(p-1)!} = \frac{p!p}{1!p!} 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
\frac{p!}{2!(p-2)!} = \frac{p!p(p-1)}{2!p!} 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
\frac{p!}{3!(p-3)!} = \frac{p!p(p-1)(p-2)}{3!p!} 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í:
\frac{p!}{k!(p-k)!} = \frac{p!p(p-1)...(p-(k-1))}{k!p!}

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é xB takové že, platí:

\frac{(p-(j-1))}{x} ∈ 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)

a^p \equiv a \pmod p.

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:

k^{p-1}\equiv 1 \pmod p (f1)

Indukce:

(k+1)^{p-1}\equiv 1 \pmod p (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í: :(k+1)^p \equiv k^p+{p \choose 1}k^{p-1}+{p \choose 2}k^{p-2}+\cdots+1 \pmod p (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:
(k+1)^p \equiv k^p+1 \pmod p ekvivalence k^p \equiv k \pmod p 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 (k+1)^p \equiv k+1 \pmod p, 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

(-a)^{1}\equiv 1 \pmod p 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