Funkcja Eulera

Własnoś¶ci

1. Je¶śli NWD(n, m)=1, to $\varphi(n\cdot m)=\varphi(n)\cdot \varphi(m)$
2. Je¶lsi p jest liczb± pierwsz±, to $\varphi(p^{k})=p^{k-1}(p-1)$
   W szczególno¶ci $\varphi(p)=p-1$

Uzasadnienie własno¶ci 2)
Aby obliczyć $\varphi(p^{n})$, należy z ci±gu $1, 2, 3, ... , p^{n}$ usun±ć wszystkie te liczby, które nie s± względnie pierwsze z $p^{n}$, czyli te, które nie s± względnie pierwsze z $p$. Liczby, które nie s± względnie pierwsze z $p$ s± wielokrotno¶ciami liczby $p$. S± to więc liczby postaci $kp$, a więc $p, 2p, 3p, ... p^{n-1}p$. Jest ich $p^{n-1}$. Po usunięciu ich z ci±gu $1, 2, 3, ... ,pp^{n-1}$ pozostaje w tym ci±gu $p^{n} - p^{n-1}$ liczb. Zatem $$ \varphi(n)=p^{n}-p^{n-1}=p^{n-1}(p-1)$$ Uzasadnienie własno¶ci 1), znajdziesz np. w publikacji.
Przykład
$$\varphi(200)=\varphi(2^{3}5^{2})=\varphi(2^{3})\varphi(5^{2})=2^{2}(2-1)5^{1}(5-1)=4\cdot 20=80$$

Tw. Eulera

Wniosek - Małe Tw. Fermata

ZnajdĽ trzy ostatnie cyfry liczby $3^{14404}$.

Rozwi±zanie
Należy znaleĽć resztę z dzielenia liczby $3^{14404}$ przez 1000.
$\varphi(1000)=\varphi(2^{3}5^{3})=\varphi(2^{3})\varphi(5^{3})=400$. Zatem na mocy tw. Eulera
$$3^{400} \equiv 1 (\bmod 1000)$$ $3^{14404}=3^{400\cdot 36+4}=(3^{400})^{36}\cdot 3^{4} \equiv 3^{4}(\bmod 1000)$
Ponieważ $3^{4}=81$, więc trzy ostatnie cyfry liczby $3^{14404}$ to 081.

ZnajdĽ dwie ostatnie cyfry liczby $7^{6042}$

Rozwi±zanie
Należy znaleĽć resztę z dzielenia liczby $7^{6042}$ przez 100. $$\varphi(100)=\varphi(2^{2}\cdot 5^{2})=\varphi(2^{2})\cdot \varphi(5^{2})= 2\cdot 5 \cdot 4 = 40.$$ Zatem na mocy tw. Eulera $7^{40} \equiv 1 (\bmod 100)$. $$7^{6042}=7^{151\cdot 40+2}=(7^{40})^{151}\cdot 7^{2}\equiv 49 (\bmod 100)$$ Odp.
Dwie ostatnie cyfry liczby $7^{6042}$, to 49.

ZnajdĽ dwie ostatnie cyfry liczby $7^{9^{9}}$

Należy znaleĽć resztę z dzielenia liczby przez 100.
Obliczymy najpierw resztę z dzielenia liczby $9^{9}$ przez $40$ $$9^{2} \equiv 1 (\bmod 40)$$ $$9^{9}=9^{2\cdot 4+1}=(9^{2})^{4}\cdot 9 \equiv 9 (\bmod 40)$$ czyli $9^{9}=40\cdot k+9$ $$7^{9^{9}}=7^{40\cdot k+9}=(7^{40})^{k}\cdot7^{9}$$ $$\varphi(100)=\varphi(2^{2}\cdot 5^{2})=\varphi(2^{2})\cdot \varphi(5^{2})= 2\cdot 5 \cdot 4 = 40.$$ Na mocy tw. Eulera $$7^{40}\equiv 1 (\bmod 100)$$ Zatem $$(7^{40})^{k}\cdot7^{9} \equiv 7^{9} (\bmod 100)\equiv 7 (\bmod 100)$$, bo $$7^{3} \equiv 43 (\bmod 100)$$ $$7^{9}=7^{3\cdot 3}=(7^{3})^{3}\equiv (43)^{3} (\bmod 100)\equiv 7 (\bmod 100) $$ Odp.
Dwie ostatnie cyfry liczby $7^{9^{9}}$, to 07.
powrót do spisu

©2010