Recepty z programátorské kuchařky
Teorie čísel

Zobraz historii verzí Skryj historii verzí

Aktuální verze kuchařky: prosinec 2012

Leták 25-3prosinec 2012(Michal Pokorný, Martin Mareš)
* První verze

Dnes si budeme povídat o různých užitečných vlastnostech celých čísel, především o dělitelnosti a kongruencích. Mohlo by se zdát, že to nemá s informatikou nic společného, ale překvapivě v informatice zakopáváme o teorii čísel takřka na každém kroku. Někdy se jedná o hledání velkých prvočísel, jindy o rychlé násobení čísel s miliony cifer nebo o všudypřítomnou asymetrickou šifru RSA.

Začneme vyjasněním základních pojmů, postupně se prokoušeme kongruencemi k hledání největšího společného dělitele a Bézoutových koeficientů, chvilku se zamyslíme nad prvočísly a nakonec si také ukážeme, jak to všechno souvisí s čínskou armádou.

Definice na úvod

Množinu celých čísel si označíme Z a každé její podmnožině {0, 1, … , n-1} budeme říkat Zn.

Často nás bude zajímat dělitelnost: a\b (nebo a|b) budeme značit, že číslo a je dělitelem čísla b (nebude-li hrozit mýlka, čteme prostě „a dělí b“).

Pro největšího společného dělitele dvou čísel zavedeme symbol nsd(a,b). Pokud nsd(a,b) = 1, říkáme, že čísla a a b jsou nesoudělná, zkráceně a b. Když budou naopak a a b soudělná, napíšeme a b. Podobně nejmenší společný násobek dvou čísel označíme nsn(a,b) a všimneme si, že je roven a · b / nsd(a,b).

Není-li jedno číslo dělitelné druhým, znamená to, že při celočíselném dělení vznikne zbytek: například pokud vydělíme 23 / 8, dostaneme zbytek 7, protože 23 = 8  · 2 + 7. Obecně zbytkem po dělení a/b nazveme hodnotu z v rovnici a = b  · x + z, kde x je celé číslo a z je nezáporné celé číslo menší než b. Obvyklé programovací jazyky mívají takovouto operaci zabudovanou a říkají jí modulo. Programátoři počítají zbytky po dělení často nějakou konstrukcí podobnou z = a % b, zatímco matematici spíše píší z = a mod b.

Dodejme, že pro záporná čísla už není definice zbytku po dělení tak jednoznačná: v některých programovacích jazycích je (-7)%3 = -1, jiné se shodnou s naší definicí na tom, že vyjde 2. Přitom oba výsledky vycházejí z jedné rovnice a = b  · x + z. Aby měla jednoznačné řešení, požadovali jsme 0≤ z<b. Lze na to ovšem jít i jinak: řekneme, že x má být celočíselný podíl a/b. Ten jde ale definovat dvěma způsoby: buď se zaokrouhlením dolů (což se shodne s naší definicí), nebo se zaokrouhlením k nule (to dělá většina procesorů), což dá pro záporné a záporný zbytek. Zkuste zjistit (a vysvětlit), jak je to ve vašem oblíbeném jazyce a co se stane, když je záporné i číslo, kterým modulíme.

Kongruence

Když čísla pq dávají stejný zbytek po dělení číslem m, píšeme

p ≡ q (mod m)

a čteme „p je kongruentníq modulo m“. To platí právě tehdy, je-li rozdíl p-q dělitelný m.

Zápis kongruence tak trochu připomíná rovnici. To není náhoda – kongruence totiž můžeme upravovat podobně jako rovnice.

Součet dvou kongruencí: Pokud a ≡ A a b ≡ B, pak také platí a+b ≡ A+B (to vše modulo totéž m). Že je to pravda, nahlédneme snadno. Napišme si a jako na  · m + za a čísla A, b, B obdobně. Pak dostaneme:

a + b = (na  · m + za) + (nb  · m + zb) =
= (na + nb)  · m + (za + zb),
A + B = (nA  · m + zA) + (nB  · m + zB) =
= (nA + nB)  · m + (zA + zB).

Protože a ≡ A a b ≡ B, musí být za = zA a zb = zB. Můžeme si tedy všimnout, že rozdíl mezi a + b a A + B je ((na + nb) - (nA + nB))  · m. To je násobek m, takže a + b ≡ A + B.

Rozdíl dvou kongruencí: Nahlédneme obdobně.

Přičtení téhož čísla k oběma stranám: Pokud a ≡ A, pak platí a+k ≡ A+k pro libovolné k. Stačí totiž přičíst evidentně platnou kongruenci k ≡ k.

Přičtení násobku m k jedné straně:a ≡ A plyne a+k ≡ A pro libovolné k, které je násobkem modulu m. Přičítáme totiž kongruenci k ≡ 0.

Vynásobení dvou kongruencí:a ≡ A a b ≡ B plyne ab ≡ AB. Stejně jako u součtů a rozdílů, i zde stačí čísla rozepsat na součty násobků m a zbytků po dělení m:

a  · b = (na  · m + za)  · (nb  · m + zb) =
= (na  · nb  · m + na  · zb + nb  · za)  · m + (za  · zb) ≡
≡ za  · zb,
A  · B = (nA  · m + zA)  · (nB  · m + zB) =
= (nA  · nB  · m + nA  · zB + nB  · zA)  · m + (zA  · zB) ≡
≡ zA  · zB.

Přitom opět víme, že za = zA a zb = zB.

Vynásobení obou stran kongruence tímtéž číslem: Pokud a ≡ A, platí také ax ≡ Ax pro libovolné x. To plyne z násobení kongruencí x ≡ x.

Ekvivalentnost úprav: Běžné úpravy rovnic jsou takzvaně ekvivalentní – to znamená, že fungují oběma směry, takže řešení rovnic ani neubírají, ani nepřidávají. Jak je to s kongruencemi? Sčítání kongruencí ekvivalentní musí být, protože opačný směr odpovídá odečtení kongruencí, což víme, že je také korektní úprava.

U násobení kongruencí to už tak jasné není. Zkusme zjistit, jestli je pravda, že z kongruence ax ≡ Ax plyne a ≡ A. Pro x=0 to jistě neplatí, ale co když zvolíme jiné x?

Vyzkoušíme to třeba na následujícím příkladě:

a ≡ 5 (mod 14)

Takováto kongruence má jednoduché řešení: a je každé celé číslo, které dostaneme sečtením 5 a nějakého násobku 14. To se dá zapsat třeba takhle:

a ∈{5 + k  · 14 | k ∈Z},

tudíž a může být například 5, 19 nebo 33.

Vyzkoušíme nyní obě strany vynásobit… třeba trojkou:

3  · a ≡ 15 ≡ 1 (mod 14) .

Tato kongruence platí pro všechna a, která po vynásobení 3 dávají modulo 14 zbytek 1. Když máme nějaké a z první kongruence, je ve tvaru 5 + k  · 14. Vynásobíme-li ho 3, dostaneme 15 + 3  · k  · 14. To je určitě kongruentní s 1 modulo 14, takže žádné řešení jsme neztratili a po chvíli uvažování zjistíme, že jsme ani žádné nepřidali.

Další pokus: původní kongruenci vynásobíme místo trojky dvojkou. Dostaneme:

2  · a ≡ 10 (mod 14) .

Řešení původní kongruence pořád sedí, ale nová kongruence platí například i pro a=12. Posuďte sami:

2  · 12 = 24 = 10 + 14 ≡ 10 (mod 14) .

Ouha, najednou vynásobení obou stran konstantou není ekvivalentní úprava!

Proč nám násobení trojkou fungovalo, ale násobení dvojkou si vymýšlí kořeny navíc? Postupně se ukáže, že násobení k je ekvivalentní úprava právě tehdy, když k 14 (či obecněji k m, počítáme-li modulo m).

Než k tomu dojdeme, nejdřív na chvíli odbočíme k největším společným dělitelům.

Euklidův algoritmus

Největšího společného dělitele dvou čísel můžeme vypočítat pomocí prvočíselného rozkladu, ale to je pro velká čísla velmi pomalé. Daleko lepší je použít prastarý Euklidův algoritmus. (Jmenuje se podle starověkého matematika Euklida, v jehož díle Základy se nachází první dochovaná verze. Jedná se zřejmě o nejstarší netriviální algoritmus, jaký se s drobnými úpravami používá dodnes. Dokonce je pravděpodobné, že Euklidés pouze sepsal dávno známý trik.)

Pojďme si odvodit, jak Euklidův algoritmus funguje. Nahlédneme, že pro libovolná čísla a,b (a>b) platí:

nsd(a,b) = nsd(a-b,b).

Proč je to pravda? Dokážeme, že dvojice (a,b) a (a-b,b) sdílejí dokonce všechny společné dělitele, takže i toho největšího:

  • Nechť d je společným dělitelem ab. Platí tedy a=a' · d, b=b' · d pro nějaká celá čísla a'b'. Pak ovšem můžeme zapsat a-b jako (a'-b') · d, což je zase dělitelné číslem d.
  • Nechť naopak d je společným dělitelem a-bb. Opět zapíšeme a-b = c' · d, b = b' · d a získáme a = (a-b) + b = (c'+b') · d.

Euklidův algoritmus dostane na vstupu nějaká dvě čísla ab a opakovaně odčítá menší z nich od většího. Jak už víme, tato operace zachovává největšího společného dělitele. Pokaždé se přitom součet a+b zmenší, takže po konečně mnoha krocích musíme jedno z čísel vynulovat. Pak víme, že největším společným dělitelem je druhé z nich (platí přeci nsd(0,x)=x).

Pojďme si takhle nějakého největšího společného dělitele spočítat. A abychom netroškařili, zkusme rovnou čísla 1518 a 945.

ab
1518 945
573 945
573 372
201 372
201 171
30 171

Zastavme se na chvíli. Teď bychom mohli pracně odečítat 30 od b, dokud bychom nenašli v b něco menšího než 30. Buďme trochu líní: když to budeme dělat dost dlouho, zbude nám v b zkrátka zbytek po dělení b číslem 30. Můžeme tedy místo odečítání modulit. Pokračujeme:

ab
30 171
30 21 = 171 mod 30
30 mod 21 = 9 21
9 3 = 21 mod 9
9 mod 3 = 0 3

a nám zbyla 0, takže nsd(1518, 945) = 3.

Pojďme si tento postup převést do návodu pro počítač. Při implementaci Euklidova algoritmu se hodí držet si v jedné proměnné pořád to větší z čísel a a b. Navíc můžeme využít toho, že každým krokem algoritmu se z většího čísla stane menší, takže je stačí prohodit a není potřeba znovu porovnávat. (Dokonce i porovnání před cyklem bychom si mohli ušetřit, kdyby nám nevadilo, že první průchod cyklem může projít „naprázdno“.)

def Euclid(a, b):
    # Prohodíme, je-li třeba
    if b > a:
        a, b = b, a

    # Zde je vždy a >= b
    while b > 0:
        # nsd(a % b, b) = nsd(a, b).
        a = a % b
        a, b = b, a

    # nsd(0, a) = a.
    return a

Jak rychle náš algoritmus běží? Podívejme se, co se stane, když pustíme dva kroky algoritmu na čísla a1 a b1 (a1 ≥ b1):

a2 = a1 mod b1
b2 = b1     (nyní a2 < b2)
a3 = a2 = a1 mod b1
b3 = b2 mod a2 = b1 mod (a1 mod b1)     (nyní a3 > b3)

Dokážeme, že a3 < a1 / 2. Rozebereme přitom dva případy podle toho, jestli bylo b1 menší, nebo větší než a1 / 2:

  • Pokud b1 ≤ a1 / 2, pak určitě platí a3 < b1, a tedy i a3 < a1 / 2. (Zde využíváme toho, že zbytek po dělení čehokoliv číslem b1 musí být menší než b1.)
  • V opačném případě leží b1 mezi a1/2a1, takže a3 = a1 mod b1 = a1 - b1 < a1 / 2. (Poslední rovnost platí, protože a1 / b1 = 1.)

Dokázali jsme tedy, že po dvou krocích algoritmu se větší z obou proměnných zmenší přinejmenším na polovinu a opět bude větší. Po O(log n) krocích tedy musí větší proměnná klesnout pod 1, čímž se algoritmus zastaví. Euklidův algoritmus proto provede O(log n) elementárních operací.

Jak dlouho ale trvá jedna elementární operace? Pokud počítáme s malými čísly, která se našemu počítači vejdou do celočíselné proměnné, zvládneme ji v konstantním čase. Jsou-li ovšem čísla větší, musíme ještě zohlednit složitost aritmetických operací: porovnání čísel a operace modulo. Když použijeme modulení pomocí školního dělení, které je kvadratické v počtu cifer, strávíme v každém z O(log n) kroků Euklidova algoritmu čas O(log 2 n). Celková složitost algoritmu tedy vzroste na O(log 3 n).

Rozšířený Euklidův algoritmus

Právě jsme našli největšího společného dělitele d nějakých dvou obrovských čísel ab. Jak ale přesvědčíme svého pochybovačného kolegu, že je náš výsledek správně? Snadno ověříme, že d dělí obě čísla. Ale jak ukážeme, že žádné větší číslo už a ani b nedělí? Překvapivě to jde jednoduše dosvědčit: pokud pro nějaká uv platí

a  · u + b  · v = d,

musí d být dělitelné každým společným dělitelem ab, takže i číslem nsd(a,b). Nemůže tedy být menší než nsd(a,b).

Dobrá – kde taková uv vzít? Kupodivu snadno: trochu upravíme Euklidův algoritmus. Nejprve ale prozradíme, že rovnici

a  · u + b  · v = nsd(a,b)

se říká Bézoutova identita a číslům uv Bézoutovy koeficienty.

Dokážeme, že spustíme-li Euklidův algoritmus na čísla ab, v každém okamžiku se v proměnných ab budou nacházet čísla tvaru α · a + β · b (kde αβ jsou nějaká celá čísla). Na začátku to triviálně platí, neboť a = a a b = b, a pokaždé, když se proměnné mění, buď se prohazují, nebo se jedna odčítá od druhé. Obě tyto operace z výrazů uvedeného tvaru dělají opět výrazy uvedeného tvaru. Takže i konečný výsledek algoritmu, tedy nsd(a,b), musí jít zapsat v takovém tvaru.

Algoritmus proto upravíme tak, aby si stále udržoval proměnné αa, αb, βa a βb a vždy platilo

a = αa  · a + βa  · b,
b = αb  · a + βb  · b.

Ke konci algoritmu je, jak víme, b = nsd(a,b), takže αbβb jsou hledané Bézoutovy koeficienty. Opět si to vyzkoušejme na výpočtu nsd(1518,945):

a αa βa b αb βb
1518 1 0 945 0 1
573 1 -1 945 0 1
573 1 -1 372 -1 2
201 2 -3 372 -1 2
201 2 -3 171 -3 5
30 5 -8 171 -3 5
30 5 -8 21 -28 45
9 33 -53 21 -28 45
9 33 -53 3 -94 151
0 315 -506 3 -94 151

Algoritmus tedy tvrdí, že hledaný nsd splňuje rovnost

1518  · (-94) + 945  · 151 = nsd(1518, 945) = 3.

Snadným výpočtem ověříme, že je to pravda. (Poznamenejme, že Bézoutova identita má nekonečně mnoho řešení. Jak byste našli ta další?)

Převeďme své myšlenky do zdrojového kódu. Do Aa, Ba, Ab, Bb budeme ukládat koeficienty αa, βa, αbβb.

def ExtEuclid(a, b):
    Aa, Ba = 1, 0  # a = 1 * a + 0 * b
    Ab, Bb = 0, 1  # b = 0 * a + 1 * b
    # Prohodíme, je-li třeba
    if b > a:
        a, b = b, a
        Aa, Ab = Ab, Aa
        Ba, Bb = Bb, Ba
    # Zde je vždy a >= b
    while b > 0:
        # Odečteme od proměnné a proměnnou b
        # tolikrát, kolikrát se tam vejde.
        # ("/" značí celočíselné dělení)
        Aa = Aa - (a / b) * Ab
        Ba = Ba - (a / b) * Bb
        # nsd(a % b, b) = nsd(a, b).
        a = a % b
        # Prohodíme
        a, b = b, a
        Aa, Ab = Ab, Aa
        Ba, Bb = Bb, Ba
    # nsd(0, a) = a.
    # Vrátíme také Bézoutovy koeficienty.
    return (a, Aa, Ba)

Žádná operace, kterou děláme s koeficienty pro proměnné ab, netrvá asymptoticky déle než operace modulo. Přidáním počítání Bézoutových koeficientů si tedy časovou složitost Euklidova algoritmu nezhoršíme.

Řešení lineárních kongruencí

Bézoutovy koeficienty jsou užitečné také k řešení kongruencí. Pojďme si to na jedné kongruenci vyzkoušet.

Máme nakoupena 4 vajíčka. V obchodě se vajíčka prodávají pouze v balíčcích po 6 kusech, zatímco my je skladujeme v platech po 20 kusech. Kolik si musíme koupit balíčků, abychom neměli v žádném platu volno?

Přepišme si tento příklad do formy kongruence:

4 + 6  · x ≡ 0 (mod 20) ,

čili

6  · x ≡ 16 (mod 20) .

To je totéž, jako že pro x a nějaké další celé číslo y platí

6  · x + 20  · y = 16.

Ejhle, to je rovnice podobná Bézoutově identitě. Kdyby na její pravé straně byl nsd(6,20)=2, byla by to přesně Bézoutova identita a rozšířený Euklidův algoritmus by nám prozradil, že platí

6  · (-3) + 20  · 1 = 2.

Tím bychom měli vyřešeno.

Jenže v našem případě je na pravé straně 8krát víc, než bychom potřebovali. Tak obě strany Bézoutovy identity vynásobíme 8:

6  · (-3)  · 8 + 20  · 1  · 8 = 2  · 8.

Řešením naší rovnice tedy je x=-24, y=8.

Tak hurá do obchodu nakoupit -24 balíčků vajec. Cože? Že záporné nemají? Nevadí – stačí si vzpomenout, že jsme původně počítali modulo 20, takže k x můžeme přičíst libovolný násobek 20 a dostaneme další řešení. Můžeme tedy jít třeba pro 16 balíčků. (Mimochodem, není to nejmenší počet balíčků, který vyhovuje úloze: 6 balíčků by také fungovalo. Rozmyslete si, jak najít nejmenší řešení kongruence.)

Teď už můžeme zformulovat obecný návod na řešení kongruence

ax ≡ b (mod n)

s neznámou x. Kongruenci přepíšeme do tvaru

ax - ny = b

a označíme d = nsd(a,n). Rozlišíme 3 případy:

  • d=b … tehdy jsou hledaná xy rovná Bézoutovým koeficientům a najdeme je rozšířeným Euklidovým algoritmem.
  • d \b … pak najdeme řešení x'y' rovnice s d na pravé straně a položíme x = x'  · b/d a y = y'  · b/d.
  • b není násobkem d … v tomto případě kongruence nemůže mít žádné řešení, neboť levá strana rovnice je pro každé xy dělitelná d, zatímco pravá strana dělitelná d nikdy není.

Inverzní prvky modulo m

Vraťme se teď zpátky z dlouhé odbočky a zkusme se znovu zamyslet nad tím, kdy je vynásobení obou stran kongruence ve tvaru

x ≡ z (mod m)

konstantou k ekvivalentní úprava. Tak říkáme úpravě, která neubírá ani nepřidává řešení. Už máme dokázáno, že když x ≡ z, tak pro každé k platí i k  · x ≡ k  · z. Takže zbývá zajistit, aby každé řešení kongruence k  · x ≡ k  · z bylo i řešením x ≡ z.

Nejprve ukážeme, že pokud k je soudělné s m, je naše snaha předem ztracená. Označme d = nsd(k,m) > 1. Vezměme libovolnou dvojici xz splňující kongruenci x ≡ z, což je totéž jako x-z ≡ 0. Nyní vytvořme novou dvojici x'=x a z' = z + m/d. Pro tu dostaneme

x' - z' ≡ x - (z + m/d) ≡ x-z - m/d ≡ - m/d not≡ 0.

Ovšem kongruenci vynásobenou k tato nová dvojice stále splňuje:

kx' - kz' ≡ kx - k(z+m/d) ≡ kx - kz - km/d ≡
≡ -km/d ≡ m · (-k/d) ≡ 0.

Dokázali jsme tedy, že pokud číslo k, kterým násobíme obě strany kongruence, je soudělné s modulem m, nejedná se o ekvivalentní úpravu. Teď naopak ukážeme, že jsou-li km nesoudělná, ekvivalentní to je.

Nahlédneme, že kdykoliv k m, existuje nějaké číslo k-1Zm takové, že k · k-1 ≡ 1. Tomuto číslu se říká inverzní prvek ke k (nebo také multiplikativní invers čísla k), a pokud jím kongruenci kx ≡ kz vynásobíme, získáme

k · k-1  · x ≡ k · k-1  · z (mod m) ,

což je kýžená kongruence x ≡ z.

Kongruenci k · k-1 ≡ 1 přitom už umíme vyřešit – předchozí kapitola nám říká, že takové k-1 existuje právě tehdy, je-li k m, a že se dá najít Euklidovým algoritmem. Dodejme ještě, že prvkům, které mají multiplikativní invers, se říká invertibilní prvky modulo m.

Konečná tělesa

Když speciálně zvolíme za m nějaké prvočíslo, budou všechny prvky Zm kromě nuly invertibilní. Tím pádem se Zm bude chovat dost podobně racionálním nebo reálným číslům. Má s nimi například tyto společné vlastnosti (sčítáním a násobením v případě Zm myslíme operace modulo m):

  • Sčítání je asociativní a komutativní.
  • Pro každé a platí a+0 = a.
  • Pro každé a existuje (-a) takové, že a + (-a) = 0.
  • Násobení je asociativní a komutativní.
  • Pro každé a je a · 1 = a.
  • Pro každé nenulové a existuje a-1 takové, že a · a-1 = 1.
  • Násobení a sčítání jsou distributivní: a  · (b - c) = a  · b - a  · c.

Obecněji, máme-li libovolnou množinu, můžeme v ní označit „jedničku“ a „nulu“ a „přibalit“ operace sčítání, násobení, „dej mi (-a)“ a „dej mi a-1“. Operací přitom myslíme libovolnou funkci, která prvkům množiny nebo jejich dvojicím přiřazuje prvky. Pokud navíc pro naši množinu s operacemi platí všechny vyjmenované vlastnosti, říká se jí komutativní těleso.

Racionální, reálná i komplexní čísla jsou příklady takových těles a my jsme k nim přidali konečná tělesa velikosti prvočísla. (Na okraj poznamenejme, že je známo, že všechna konečná tělesa mají velikost mocniny prvočísla, což ovšem neznamená, že se vždy chovají jako celá čísla modulo nějakým m.)

Malá Fermatova věta

S prvočísly úzce souvisí takzvaná Malá Fermatova věta. Říká, že pokud je p prvočíslo a a libovolné číslo od 1 do p-1, tak

ap - 1 ≡ 1 (mod p) .

Tato věta má mnoho různých použití (třeba ve známém šifrovacím algoritmu RSA nebo níže v algoritmu na testování prvočíselnosti), nám se bude především hodit jako další způsob invertování čísel modulo prvočíslo:

ap - 2  · a ≡ ap - 1 ≡ 1 (mod p) ,

takže ap-2 je inverzní prvek k a.

Danger!Pojďme nyní Malou Fermatovu větu dokázat. Indukcí podle a budeme dokazovat ekvivalentní tvrzení

ap ≡ a (mod p) .

(Jelikož a je určitě nesoudělné s modulem p, tak už víme, že násobení obou stran kongruence je ekvivalentní úprava.)

Pro a = 1 je snadné vidět, že věta platí:

ap = 1p = 1 ≡ 1 (mod p) .

Teď uděláme indukční krok. Řekněme, že máme dokázáno, že naše věta platí pro nějaké a, a chceme ji dokázat i pro a+1. K tomu se bude hodit známá Binomická věta, která říká, že pro každé reálné xy a přirozené n platí:

(x + y)n = ∑
n
i = 0
(n )
i
xi yn-i,
přičemž
(n)
i
je takzvané kombinační číslo tvaru
(n)
i
=
n · (n-1)  · (n-2)  ·  …    · (n-i+1)
i  · (i-1)  ·  …    · 1
,

mající v čitateli i jmenovali zlomku právě i členů.

Indukce po nás chce, abychom dokázali, že (a+1)p ≡ a. Rozepíšeme tedy levou stranu kongruence pomocí Binomické věty:

(a+1)p =
(p )
0
a0 +
(p )
1
a1 + … +
(p )
p
ap.
Jelikož
(p)
0
i
(p)
p
jsou rovny 1, tvoří první a poslední člen součtu dohromady ap + 1. To je podle indukčního předpokladu kongruentní s a.
Zbývá tedy dokázat, že všechny ostatní členy jsou dělitelné p, takže se v kongruenci modulo p neprojeví. Vskutku: pro 0 < i < p se ve zlomku definujícím
(p)
i
objeví p v prvočíselném rozkladu čitatele, ale ne v rozkladu jmenovatele, takže se nemá s čím zkrátit.

Tím je indukce hotova.

Fermatův test prvočíselnosti

Jako malou odměnu za dlouhý důkaz předvedeme, jak Malou Fermatovu větu využívat ke zjištění, zda je nějaké obrovské číslo n prvočíslem. Jistě bychom mohli zkoušet všechny kandidáty na dělitele od 2 do n-1 (nebo chytřeji do n), ale to by trvalo příliš dlouho.

Raději zkusíme vybrat nějaké náhodné a∈{1,… ,n-1} a spočítat, kolik je an-1 mod n. Pro prvočíselné n musí vyjít jednička, takže pokud vyjde něco jiného, usvědčili jsme n z toho, že není prvočíslem (aniž jsme našli jediného dělitele – zvláštní, že?).

Pokud pro toto konkrétní a jednička vyjde, samozřejmě to neznamená, že n je určitě prvočíslo. Vyzkoušíme proto několik různých a, a pokud test pro žádné z nich neselže, drze prohlásíme, že n je pravděpodobně prvočíslo.

Jak moc velká drzost to je? Překvapivě ne moc velká. Pro skoro každé složené číslo n platí, že alespoň polovina a-ček dosvědčí, že se nejedná o prvočíslo. Takže jeden pokus selže s pravděpodobností nejvýše 1/2 a pokud uděláme t pokusů, pravděpodobnost chybného výsledku je nanejvýš 1/2t.

Jedinou výjimku z našeho pravidla tvoří takzvaná Carmichaelova čísla (nejmenší z nich je číslo 561). To jsou čísla, jejichž složenost prokážeme jen tehdy, když se strefíme do a soudělného s n, a takových a je velmi málo. Naštěstí není Carmichaelových čísel moc (relativně k prvočíslům), takže Fermatův test funguje docela spolehlivě.

Existují i důmyslnější testy, které se Carmichaelovými čísly obalamutit nenechají. Jejich popis, jakož i důkaz našeho tvrzení o spolehlivosti Fermatova testu, najdete v literatuře zmíněné na konci kuchařky.

Rychlé mocnění

Ve Fermatově testu nebo při počítání inverzí pomocí Malé Fermatovy věty potřebujeme spočítat ak mod m pro velké k. Pokud budeme mocninu ak počítat přímo podle definice, tedy jako a  · a  · …  · a, budeme potřebovat O(k) násobení, což je příliš.

Jednoduchou fintou lze počet operací snížit na O(log k). Například a16 můžeme spočítat jako:

a16 = (a8)2 = ((a4)2)2 = (((a2)2)2)2.

Pro obecný exponent bude rychlejší umocňování vypadat takto:

def FastExp(a, k):
    # Nejdříve ošetříme triviální případy.
    if k == 0: return 1
    if k == 1: return a

    # Když je x sudé, vrátíme a^(k/2) * a^(k/2).
    # Když je x liché, vrátíme a * a^(k - 1).

    if k % 2 == 0:
        i = FastExp(a, k / 2)
        return i * i
    else:
        return a * FastExp(a, k - 1)

Každé volání FastExp pro sudé k jednou zavolá FastExp s polovičním k a jednou vynásobí dvě čísla. Když je k liché, převede se na sudé a provede se jedno vynásobení. FastExp tedy provede O(log k) násobení.

Je ale důležité uvědomit si, že kdybychom si neuložili výsledek ak/2 do pomocné proměnné i, ale rovnou vraceli FastExp(a, k / 2) * FastExp(a, k / 2), byl by náš kód stejně pomalý, jako kdybychom počítali mocninu podle definice!

Pro použití ve Fermatově testu (nebo obecně na spočítání mocniny ak mod m) stačí po každém násobení výsledek vymodulit m.

Síto na prvočísla

Už jsme zjistili, že se nám hodí umět najít prvočísla. Kde je ale vezmeme? Můžeme určitě zkoušet jedno číslo po druhém a pokaždé otestovat, jestli držíme prvočíslo (třeba Fermatovým testem nebo zkoušením všech dělitelů). Už staří Řekové ale znali algoritmus, který najde všechna prvočísla menší než n efektivněji. Říká se mu Eratosthenovo síto.

Síto funguje na docela jednoduchém principu. Budeme si uchovávat v paměti pro každé číslo od 2 do n příznak, jestli je prvočíslo, nebo složené. Začneme u dvojky a označíme všechny násobky 2 ležící mezi 4 a n jako složená čísla. Další prvočíslo je 3. Označíme všechny násobky 3 ležící od 6 do n jako složená čísla. Další číslo na řadě je 4. Když jsme ale vyškrtávali násobky 2, vyškrtli jsme i 4. Nebudeme tedy provádět nic a rovnou přejdeme na 5. Takto najdeme všechna prvočísla od 2 do n a stihneme to rychle.

Ukažme si ještě zdrojový kód v Pythonu:

def Eratosthenes(n):
    prvocislo = [ True ] * n

    for i in range(2, n):
        if prvocislo[i]:
            print("%d je prvocislo." % i)

            # Násobky prvočísla jsou složené
            j = i * 2
            while j < n:
                prvocislo[j] = False
            j += i

Jak dlouho síto poběží? Dá se dokázat, že jeho časová složitost činí O(n log log n), ale není to snadné. My si zde předvedeme jenom slabší odhad O(n log n). Zájemce o těžší důkaz menší složitosti odkazujeme na vzorové řešení úlohy 24-3-5.

Síto tráví čas O(n) hledáním prvočísel a mezitím škrtá jejich násobky. Když škrtáme násobky dvojky, vyškrtneme nejvýše n/2 čísel, když škrtáme násobky trojky, vyškrtneme jich nejvýše n/3, atd. Složitost Eratosthenova síta tedy bude shora omezena součtem

n +
n
2
+
n
3
+ … +
n
n
= n  · ∑
n
i = 1
1
i
.

Sumě

Hn = ∑
n
i=1
1
i

se říká n-té harmonické číslo a dokážeme o něm, že leží v O(log n).

Uvažujme, o co se zvětší H2n oproti Hn:

H2n - Hn =
1
n+1
+
1
n+2
+ … +
1
2n
.

To je součet n členů, z nichž každý je menší než 1/n. Celý součet je tedy menší než 1.

Zjistili jsme tedy, že H2n < Hn + 1. Funkce, které rostou takhle pomalu, jdou shora omezit nějakým logaritmem n, takže Hn = O(log n).

Proto složitost celého Eratosthenova síta činí O(n log n).

Čínská zbytková věta

Následující věta dostala své jméno po staročínském způsobu počítání vojáků. Čínská armáda je velká, a kdybychom chtěli počítat vojáky jednoho po druhém, trvalo by to dlouho. Pomáhalo prý armádu rozřadit do řad o velikostech m1, m2, …, mn (součin všech mi si označíme jako M bez indexu). Někdy zbyli nezařazení dva, někdy třicet, někdy se seřadili všichni. Tyto zbytky si označíme z1, z2, …, zn.

A co Čínská zbytková věta říká? Tvrdí, že když jsou všechna mi navzájem nesoudělná a počet vojáků je menší než M, lze ho ze zbytků zi jednoznačně určit. Když například rozdělujeme vojáky do řad velikostí 2, 3, 5, 7, 11 a 13, můžeme zbytky z řad jednoznačně vyjádřit každý počet vojáků menší než 2  · 3  · 5  · 7  · 11  · 13 = 30 030.

Formálněji řečeno: Jsou-li dána navzájem nesoudělná přirozená čísla m1, …, mn (jejichž součin označíme M) a zbytky z1, …, zn, pak existuje právě jedno číslo x∈ZM takové, že pro všechna i je

x ≡ zi (mod mi) .

A jak dokážeme, že něco takového platí? Mějme 2 čísla a, b ∈ZM taková, že mají stejné zbytky po dělení všemi mi. Ukážeme, že musí nutně být stejná.

Víme, že pro všechna i platí

a ≡ b (mod mi) .

To podle definice kongruence znamená, že rozdíl a-b je dělitelný všemi mi. Proto je dělitelný i nejmenším společným násobkem všech mi, což ovšem díky nesoudělnosti musí být jejich součin M.

Máme tedy dvě čísla ze ZM, jejichž rozdíl je dělitelný M. To nutně znamená, že jsou stejná.

Dokázali jsme tedy, že jedna sada zbytků z1, …, zn odpovídá jednoznačně určenému číslu x ∈ZM, ale ještě nevíme, jak bez zkoušení všech možností toto x najít. Půjdeme na to od lesa.

Nejprve se hodí všimnout si toho, že když sečteme dvě čísla, sečtou se i jejich zbytky modulo všemi mi.

Co kdybychom nyní dokázali sehnat čísla Q1, …, Qn taková, že Qj je dělitelné všemi mi kromě mj a že Qj ≡ 1 (mod mj) ?

To by potom stačilo položit

x = (z1 · Q1 + z2 · Q2 + … + zn · Qn) mod M.

Vskutku: počítáme-li x mod mi, všechny členy zj  · Qj pro j≠ i vyjdou nulové a člen zi  · Qi bude roven zi. To, že celý výsledek nakonec vymodulíme M, na věci nic nemění, protože přičtení či odečtení libovolného násobku M zbytek po dělení žádným mi neovlivní.

Jak se ale k číslům Qi dostaneme? Číslo Qi má být dělitelné všemi mj kromě mi. Uvažujme tedy součin

Si = m1  ·  …    · mi-1  · mi+1  ·  …    · mn.

Ten modulo každé mj (j≠ i) dá nulu, zatímco modulo mi nějaké číslo ri nesoudělné s mi (nesoudělné musí být, protože jinak by mi bylo soudělné s některým mj). Speciálně to znamená, že ri není 0.

Potřebujeme tedy z tohoto nenulového zbytku udělat jedničku. To zařídíme snadno: pořídíme si r
-1
i
, což bude inverzní prvek k ri modulo mi, a tímto prvkem celé Si vynásobíme:
Qi = Si  · r
-1
i
.

Toto Qi už má požadované vlastnosti: Qi mod mj pro j≠ i vyjde nulové, protože Qi je násobkem Si, které bylo dělitelné mj. A modulo mi získáme

Qi ≡ Si  · r
-1
i
≡ ri  · r
-1
i
≡ 1.

„Kouzelná“ čísla Qi tedy dokážeme sestrojit a jejich zkombinováním i hledané x.

Pojďme si to teď zkusit v praxi. Chceme najít nejmenší x takové, že platí následující kongruence:

x ≡ 3  (mod 5)
x ≡ 1  (mod 9)
x ≡ 14 (mod 16)

Spočítáme si nejdříve M a všechna Si:

M = 5  · 9  · 16 = 720,
S1 = 9  · 16 = 144,
S2 = 5  · 16 = 80,
S3 = 5  · 9 = 45.

Teď zjistíme, kolik vychází každé Si modulo mi a určíme příslušné multiplikativní inverze (například pomocí rozšířeného Euklidova algoritmu):

r1 = 144 mod 5 = 4,
r2 = 80 mod 9 = 8,
r3 = 45 mod 16 = 13,
r
-1
1
= 4     (4 · 4 mod 5 = 1),
r
-1
2
= 8     (8 · 8 mod 9 = 1),
r
-1
3
= 5     (13 · 5 mod 16 = 1).
Z toho vypočteme Qi jako Si  · r
-1
i
:
Q1 = S1  · r
-1
1
= 144  · 4 = 576,
Q2 = S2  · r
-1
2
= 80  · 8 = 640,
Q3 = S3  · r
-1
3
= 45  · 5 = 225.

Nakonec sečteme příslušné násobky Qi a zjistíme x:

x ≡ 3  · 576 + 1  · 640 + 14  · 225 = 5518 ≡ 478 (mod 720) .

Výsledek opravdu vypadá správně:

x = 478 = 3 + (5  · 95) = 1 + (9  · 53) = 14 + (16  · 29).

Pár slov na závěr

Doufáme, že se vám naše povídání o teorii čísel líbilo a že jste poznali, že i tak základní objekty, jako jsou celá čísla, mají spousty zajímavých vlastností.

Přejete-li si dozvědět se více o prvočíselných testech nebo o RSA, můžeme navrhnout ke studiu textík Algoritmy okolo teorie čísel od jednoho z autorů kuchařky. Důkladný rozbor Eratosthenova síta a jiné zajímavosti o prvočíslech najdete v článku Tři věty o prvočíslech od téhož autora.

S teorií čísel také souvisí algebra, která zobecňuje různé poznatky na libovolné množiny opatřené nějakými operacemi (například tělesa). Máte-li o ni zájem, mohla by vám pomoci například skripta Základy algebry od Davida Stanovského.

Kuchařku pro vás namíchali

Michal Pokorný a Martin Mareš