Řešené příklady na „poslední dvě cifry"
2324    Hledáme poslední dvě cifry.
y(100) = (4 — 2) (25 — 5) = 40, takže pro libovolné a nesoudělné se 100 platí podle Eulerovy věty a40 = í(mod 100). Takže kdyby se nám podařilo zjistit zbytek 2425 modulo 40, věděli bychom, že 23 (nesoudělné se 100) umocněno na ten zbytek má stejné poslední dvě cifry jako 2324 . Jenže jednoduše pomocí Eulerovy věty to nezjistíme, protože 24 a 40 nejsou nesoudělná (takže předpoklady Eulerovy věty nejsou splněny).
První plán nám nevyšel - nevadí, jdeme sbírat dílčí informace.
Můžeme si pomoci tím, že najdeme poslední cifru - zbytek po dělení 10. cp(ÍO) = (2 - 1)(5 - 1) = 4. Největší společný dělitel 23 a 10 je 1. Tedy můžeme použít Eulerovu větu. Podle ní je 234 = í(mod 10). Je 2425 = 4 • 6 • 2424. Tedy 234 6 24'4 = í624"'(mod 10), neboli 2324'5 = í(mod 10). Poslední cifra je tedy 1.
Další informaci získáme pomocí zbytků po dělení čísla 2324    čísly
25 a 4. Víme, že 100 je dělitelné 4 a 25, takže každé přirozené číslo n dává po dělení 4 a 25 stejné zbytky jako číslo, které získáme, když od n odečteme všechny stovky (např. 19987 jako 87).
Hledáme zbytek 232426 po dělení 25. ^>(25) = (25 - 5) = 20. Největší společný dělitel 23 a 25 je 1. Tedy podle Eulerovy věty je 2320 = 1 (mod 25).
Hledáme zbytek 2425 po dělení 20. Je
2425 = 4 • 6 • 2424 = 4 • (5 + 1) • (25 - l)24
4 • (5 + 1) • (25 - l)24 = (20 + 4) • (25 - l)24 = 4 • (25 - l)24(mod 20) Zajímá nás zbytek 4 • (25 — l)24 po dělení 5.
(25-l)24 = (-l)24 = l(mod5)
(V poslední úpravě si uvědomíme, že jde o 24 závorek ve kterých je v každé vždy jeden člen nedělitelný 5, takže celý součin musí dávat stejný zbytek po dělení 5 jako ( — l)24 = 1.)
Tedy 2425 = 4 • (5k + í)(mod 20) pro nějaké celé k, neboli 2425 = 4 • (5k + 1) = (20Ä; + 4) = A(mod 20)
232425 = 234 = (25 - 2)4 = (-2)4 = í6(mod 25)
Získali jsme informaci, že 2324    dává zbytek 16 po dělení 25.
Teď hledáme zbytek 232426 po dělení 4. y>(4) = (4 - 2) = 2. Největší společný dělitel 23 a 4 je 1. Tedy podle Eulerovy věty je 232 = í(mod 10). Je 2425 = 2 • 12 • 2424. Tedy je to sudé číslo, a proto
232425 = l(moeU)
Dejme nyní tyto informace dohromady. Poslední cifra omezuje řešení na prvky množiny {01,11, 21, 31, 41, 51, 61, 71, 81, 91}. Zbytek po dělení 25
1
říká, že řešení je v množině {16,41,76,91}. Zbytek po dělení 4 říká, že řešení je v množině
{01, 05,09,13,17, 21, 25, 29, 33, 37,41,45,49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97}
Takže jsme dospěli k výsledku 41. (Na určení výsledku by nám stačila dělitelnost 4 a 25 a určitě nemusíme vypisovat tu poslední množinu celou, stačí ověřit zbytek po dělení 4 z dosud nabízených možností.)
2. 79   - máme najít poslední dvě cifry (příklad ze skript).
95(100) = (4-2)(25-5) =40
7 je nesoudělné se 100. Podle Eulerovy věty 740 = í(mod 100).
Takže kdyby se nám podařilo zjistit zbytek 99 modulo 40, věděli bychom, že 7 (nesoudělné se 100) umocněno na ten zbytek má stejné poslední dvě cifry jako 79 .
Hledáme zbytek 99 = 318 modulo 40. 95(40) = (8 - 4)(5 - 1) = 16, 3 je nesoudělné se 40. Podle Eulerovy věty 316 = í(mod 40). Takže 318 = 32 = 9(mod 40) Zbytek 99 po dělení 40 je tedy 9.
Takže podle Eulerovy věty platí
799 =79(mod 100) 79 = (73)3 = 3433 = 433 = 79507 = 7(mod 100) Poslední dvě cifry jsou 07.
Definice svazu (převzatá z teorie množin a teorie svazů)
Řekneme, že uspořádaná množina S je svazem s operacemi infimum a supremum, pokud je neprázdná a pro každou její dvouprvkovou podmnožinu {x, y} existuje supremum a infimum této množiny v S.
Poznámka: supremum a infimum počítáme vzhledem k danému uspořádání (reflexivní, antisymetrická, tranzitivní relace - nemusí být úplné) na množině S s argumentem - množinou - ne uspořádanou dvojicí (x, y), takže je automaticky komutativní, a argumentem může být i víceprvková množina, takže je i asociativní. Nemusí být distributivní.
2