Eulerova funkce

Definice. Eulerova funkce

φ : ℕ^{+} \to ℕ^{+}

φ (n) = | {k \in \hat{n} | k ⟂ n} |

Věta. Nechť

\prod_{i} p_{i}^{k_{i}}

je prvočíselný rozklad čísla

n

. Pak

φ (n) = \prod_{i} p_{i}^{k_{i} - 1} (p_{i} - 1) = \prod_{i} p_{i}^{k_{i}} (1 - \frac{1}{p_{i}}) = n \prod_{i} (1 - \frac{1}{p_{i}})

Věta.

(\forall n \in ℕ^{+}) (n = \sum_{d | n} φ (d))

Důkaz. Uvažujme základní tvary všech zlomků

\frac{i}{n}, i \in \hat{n}

. Pro každé

d | n

bude platit, že počet zlomků, které mají ve jmenovateli

d

, bude právě

φ (d)

Věta (Eulerova-Fermatova).

(\forall a, n \in ℕ, a ⟂ n) (a^{φ (n)} \equiv 1 (m o d n))

Důkaz. Nechť

b_{i}, i \in \hat{φ (n)}

jsou všechna čísla do

n

nesoudělná s

n

. Nechť

r_{i} = a b_{i} mod n

, pak i všechna

r_{i}

budou nesoudělná s

n

a navzájem různá (důkaz triviální). To znamená, že

r_{i}

tvoří permutaci

b_{i}

, tedy

\prod_{i} b_{i} = \prod_{i} r_{i} \equiv \prod_{i} a b_{i} = a^{φ_{n}} \prod_{i} b_{i} (m o d n)

. Jelikož součin

b_{i}

je nesoudělný s

n

, můžeme podělit obě strany kongruence, čímž je důkaz hotov.

Cvičení. Najděte mocninu

3

, jejíž dekadický zápis končí na

0001

Řešení

3^{m} \equiv 1 (m o d 10^{4})

, podle Eulerovy-Fermatovy věty

m = φ (10^{4}) = φ (2^{4} \cdot 5^{4}) = 2^{3} (2 - 1) \cdot 5^{3} (5 - 1) = 4000

Cvičení. Existuje

a \in ℕ

takové, že

a^{13} = 21982145917308330487013369

. Jaké?