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 čísel nesoudělných s . 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 má inverzi v $Z_{m}$ a má podle Eulerovy funkce přesně $\phi (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}$ ?

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

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (3): 5

Přečtěte si také

Diskuse

Článek zatím nemá žádné komentáře.