Eulerova věta je zobecněním malé Fermatovy věty a říká, že

 a^{\\varphi (m)} = 1 \\; v \\; Z_{m}

kde \\varphi (m) je Eulerova funkce a gcd(a,\\; m) = 1.

Eulerova funkce

Eulerova funkce \\varphi (n), kde n \\geq 2, je definována jako počet kladných celých čísel, která jsou nižší než n a jsou s n nesoudělná. Platí, že \\varphi (1) = 1.

Výpočet Eulerovy funkce

Číslo n rozložíme na prvočísla p_{1},\\; p_{2}, \\cdots ,\\; p_{r} a dosadíme do následujícího vzorce:


\\varphi (p_{1}^{n_{1}} \\cdot p_{2}^{n_{2}} \\cdots p_{r}^{n_{r}}) = p_{1}^{n_{1}} \\cdot (1 - {1 \\over p_{1}}) \\cdot p_{2}^{n_{2}} \\cdot (1 - {1 \\over p_{2}}) \\; \\cdots \\; p_{r}^{n_{r}} \\cdot (1 - {1 \\over p_{r}}) =

= n \\cdot (1 - {1 \\over p_{1}}) \\cdot (1 - {1 \\over p_{2}}) \\; \\cdots \\; (1 - {1 \\over p_{r}})

Důkaz Eulerovy věty

Každé číslo od 0 do m-1, které je nesoudělné s m a má inverzi v Z_{m}, má podle Eulerovy funkce přesně \\varphi (m) invertibilních prvků, označme si je b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{n}.

Pro každé dva prvky b_{i} a b_{j}, kde i a j jsou z množiny \\{0,\\; 1,\\; 2, \\cdots,\\; \\varphi (m)\\} platí

 b_{i} \\cdot a \\neq b_{j} \\cdot a \\; v \\; Z_{m}

protože b_{i}, b_{j} i číslo a jsou nesoudělné s m, tak rovnost nemůže platit.

Pokud nyní vezmene posloupnosti

b_{1} \\cdot a,\\; b_{2} \\cdot a,\\; b_{3} \\cdot a, \\cdots ,\\; b_{\\varphi (n)} \\cdot a
b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi (n)}

tak musí obsahovat (až na pořadí) totožná čísla. Vytkneme-li z první posloupnosti a, pak platí


 a^{\\varphi (n)} \\cdot (b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi (n)}) = b_{1},\\; b_{2},\\; b_{3}, \\cdots ,\\; b_{\\varphi(n)} \\; v \\; Z_{m}

A nakonec vykrátíme


a^{\\varphi (n)} = 1 \\; v \\; Z_{m}

A dostáváme tvrzení, které jsme chtěli dokázat.


Příklad

Kolik je 7^{3822} v Z_{15}?

gcd(7, 15) = 1
15 = 5 \\cdot 3
\\varphi (15) = 15 \\cdot (1- {1 \\over 5}) \\cdot(1- {1 \\over 3}) = 8
{{3822} \\over {8}} = 477 \\; (zbytek \\; 6)
 7^{3822} = (7^{8})^{477} \\cdot 7^{6} = 1^{477} \\cdot 7^{6} = 1 \\cdot 7^{2} \\cdot 7^{2} \\cdot 7^{2} =  49 \\cdot 49 \\cdot 49 =
 = 4 \\cdot 4 \\cdot 4 = 16 \\cdot 4 = 1 \\cdot 4 = 4 \\; v \\; Z_{15}

Literatura

  • VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 193 s.







Doporučujeme