W tym podrozdziale zapoznamy się z najważniejszą dla dalszych zastosowań, (w szczególności w teorii grup oraz w wykorzystaniu dalej m.in. w teorii ciał i teorii Galois) funkcją arytmetyczną 12. Funkcję tę można definiować na różne sposoby, ale postawimy tu standardową definicję teorioliczbową.
Własność 2.5.2 ( podstawowe własności funkcji Eulera).
(1) \(\varphi (1)=1\), (jeden jest względnie pierwsze z jedynką).
(2) Niech \(p\) - liczba pierwsza. Wtedy: \(\varphi (p)=p-1=p(1-\f {1}{p})\).
(3) Niech \(p\) - liczba pierwsza, \(k\in \N \). Wtedy \(\varphi (p^k)=p^{k}-p^{k-1}=p^{k}(1-\f {1}{p})\), gdyż mamy \(p^{k-1}\) liczb całkowitych takich, że \(1\leqslant l<p^k\), które są podzielne przez \(p\).
Przypomnijmy, że funkcja arytmetyczna \(f:\;N\rightarrow \C \) jest multiplikatywna wtedy i tylko wtedy gdy dla dowolnych względnie pierwszych \(m, n\in \N \) spełniona jest równość \(f(mn)=f(m)f(n)\). Udowodnimy teraz, że funkcja \(\phi \) Eulera jest multiplikatywna.
Dowód. Niech
\[ I:=\{k\in \{1,\ldots ,m\}:\; \nwd (k,m)=1\},\quad J:=\{l\in \{1,\ldots ,n\}: \; \nwd (l,n)=1\} \]
oraz
\[ A:=\{s\in \{1,\ldots , m\cdot n\}: \; \nwd (s,m\cdot n)=1\}. \]
Wtedy oczywiście \(\#(I\times J)=\varphi (m)\varphi (n)\), zaś \(\#(A)=\varphi (mn)\). Skonstruujemy bijekcję między zbiorami \(I\times J\) i \(A\).
Zgodnie z twierdzeniem chińskim o resztach dla dowolnej pary liczb \((k,l)\in I\times J\) istnieje dokładnie jedna liczba \(z_{k,l}\in \{1,\ldots ,mn\}\) spełniająca warunki
\[ \begin {cases} z_{k,l}\equiv k\pmod {m}\\ z_{k,l}\equiv l\pmod {n} \end {cases}\]
(jedyność wynika z żądania, aby \(z_{k,l}\in \{1,\ldots ,mn\}\). Liczba ta jest względnie pierwsza z \(m\) (bo \(k\) była) oraz z \(n\) (bo \(l\) była) stąd jest względnie pierwsza z \(mn\). Mamy więc dobrze określone odwzorowanie:
\[ \Phi : I\times J\ni (k,l)\str z_{k,l}\in A. \]
(1) Wykażemy, że \(\Phi \) jest injekcją. Niech bowiem \(z_{k,l}=z_{k’,l’}\) i na przykład \(1\leqslant k<k’\leq m\). Wtedy \(m|(z_{k,l}-k)\) i \(m|(z_{k,l}-k’)\), skąd \(m|(k’-k)\), co prowadzi do sprzeczności. (2) By dokończyć dowód wykażemy, że \(\Phi \) jest surjekcją. Jeśli \(z\in A\), to \(z=\Phi (k,l)\) gdzie \(k:=z\pmod {m}\) oraz \(l:=z\pmod {n}\). Łatwo sprawdzić, że \((k,l)\in I\times J\). Wobec tego \(\varphi (m)\varphi (n)=\#(I)\cdot \#(J)=\#(I\times J)=\# (A)=\varphi (mn)\) i dostajemy tezę. □
Dowód. Jeśli \(n=p_1^{k_1}\cdot \ldots \cdot p_r^{k_r}\), gdzie \(p_1,\ldots , p_r\) to parami różne liczby pierwsze oraz \(k_1,\ldots , k_r>0\), to
\[ \varphi (n)=\varphi (p_1^{k_1})\cdot \ldots \cdot \varphi (p_r^{k_r})=p_1^{k_1}\left (1-\frac {1}{p_1}\right )\cdot \ldots \cdot p_r^{k_r}\left (1-\frac {1}{p_r}\right )=n\prod \limits _{i=1}^r\left (1-\frac {1}{p_i}\right ).\]
□
Udowodnimy teraz własność funkcji Eulera, która zostanie wykorzystana w ostatniej części wykładu przy badaniu własności grupy multiplikatywnej ciała skończonego.
Dowód. Zauważmy, że jeśli \(k\in \{1,\ldots , n\}\), to \(\nwd (n,k)=n/d\) dla pewnego dzielnika \(d\) liczby \(n\). Jeżeli teraz:
\[ n_d:=\#\{k\in \N :\; k<n, \nwd (n,k)=n/d\}, \]
to \(n=\sum \limits _{d|n}n_d\). Niech teraz liczba \(k\in \{1,\ldots , n\}\) będzie taka, że \(\nwd (n,k)=n/d=l\). Wtedy \(k=lm\) dla pewnego \(m<d\) oraz z równości \(\nwd (n,k)=l\) otrzymujemy \(\nwd (m,d)=l\). Oznacza to, że czyli liczby \(k\in \{1,\ldots , n\}\) spełniające warunek \(\nwd (n,k)=l\) są postaci \(lm\), gdzie \(m\in \{1,\ldots , d\}\) oraz \(\nwd (m,d)=1\). Otrzymujemy stąd równość \(n_d=\varphi (d)\). Łącząc oba fakty otrzymujemy tezę. □