Eulerova věta

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ž a jsou s nesoudělná. Platí, že $\\varphi (1) = 1$ .

Výpočet Eulerovy funkce

Číslo 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 do m-1 , které je nesoudělné s 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 a 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 jsou nesoudělné s , 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}$ ?

$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.

Eulerova funkce

Výpočet Eulerovy funkce

Důkaz Eulerovy věty

Příklad

Literatura

Doporučujeme