Twierdzenie Eulera

Poznamy teraz uogólnienie Małego Twierdzenia Fermata pochodzące od Eulera. Uogólnienie to leży u podstaw znanego systemu kryptograficznego - RSA. Potrzebne nam będzie funkcja zliczające liczby względnie pierwsze z liczbą \( n \).

Funkcja \( \varphi \)-Eulera to \( \varphi:\mathbb{N}-{\{ {0} \} }\longrightarrow\mathbb{N} \) zdefiniowaną poprzez

\( \varphi(n)=\vert{\{ {1\leq a < n\quad:\quad {\sf NWD}\ (a,n)=1} \} }\vert. \)

Obserwacja 11.11

Dla dowolnej liczby pierwszej \( p \) zachodzi:

  • \( \varphi(p)=p-1 \),
  • \( \varphi(p^\alpha)=p^\alpha-p^{\alpha-1}=p^\alpha(1-\frac{1}{p}) \).

Dowód

Ponieważ \( p \) jest pierwsza, liczby \( 1,2,\ldots,p-1 \) są z nią względnie pierwsze, co dowodzi pierwszego punktu. Dla dowodu punktu drugiego zauważmy najpierw, że jedynie wielokrotności liczby \( p \) mają nietrywialny wspólny dzielnik z \( p^\alpha \). Wielokrotności tych w przedziale [\( 1,p^\alpha \)] jest dokładnie \( p^{\alpha-1} \), stąd \( \varphi(p^\alpha)=p^\alpha-p^{\alpha-1} \).

Obserwacja 11.12

Dla dowolnych \( m,n>0 \) takich, że \( m\perp n \) zachodzi

\( \varphi(m n)=\varphi(m)\varphi(n). \)

Dowód

Z Chińskiego Twierdzenia o Resztach wiemy, iż każda liczba z przedziału \( [0,\ldots,mn-1] \) jest jednoznacznie wyznaczona przez jej reszty modulo \( m \) i modulo \( n \). Wiemy także, że dla dowolnego \( a \):

\( {\sf NWD}\ (a,mn)=1 \) wtedy i tylko wtedy, gdy \( {\sf NWD}\ (a,m)=1={\sf NWD}\ (a,n) \).

To oznacza, iż liczb \( 0\leq a < mn \) takich, że \( a \perp mn \) jest dokładnie tyle co par \( (i_1,i_2) \) takich, że \( 0\leq i_1 < m \), \( 0\leq i_2 < n \) oraz \( i_1 \perp m \), \( i_2\perp n \).

Wniosek 11.13

Jeśli \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) jest rozkładem na liczby pierwsze \( p_i \), w którym \( \alpha_i\geq 1 \), to:

\( \begin{align*} \varphi(n) & =\varphi(p_1^{\alpha_1})\ldots\varphi(p_k^{\alpha_k}) \\ & =p_1^{\alpha_1}(1-\frac{1}{p_1})p_2^{\alpha_2}(1-\frac{1}{p_2})\ldots p_k^{\alpha_k}(1-\frac{1}{p_k}) \\ & =n\cdot\prod_{p|n}(1-\frac{1}{p}), \end{align*} \)

gdzie ostatnim iloczyn przebiega po wszystkich liczbach pierwszych \( p \) dzielących \( n \).

Przykład

Policzmy \( \varphi(2006) \):

  • \( 2006=2\cdot17\cdot59 \),
  • \( \varphi(2006)=2006\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{17})\cdot(1-\frac{1}{59})=928 \).

Oraz \( \varphi(1980) \):

  • \( 1980=2^2\cdot3^2\cdot5\cdot11 \),
  • \( \varphi(1980)=1980\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})\cdot(1-\frac{1}{5})\cdot(1-\frac{1}{11})=480 \).

Twierdzenie 11.14 [Euler 1736]

Dla dowolnych \( a,n \), gdzie \( {\sf NWD}\ (a,n)=1 \) zachodzi:

\( a^{\varphi(n)}\ \equiv_{n}1 . \)

Dowód

Zmodyfikujmy pierwszy z poznanych dowodów Małego Twierdzenia Fermata. Niech \( m_1 < m_2 < \ldots < m_{\varphi(n)} \) będą wszystkimi liczbami względnie pierwszymi z \( n \) i niewiększymi od \( n \). Rozważmy ciąg

\( a_1, a_2,\ldots, a_{\varphi(n)} \)

reszt \( a_i = m_i a \ {\sf mod}\ n \) liczb \( m_i a \) modulo \( n \). Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech \( 1\leq i < j\leq \varphi(n) \) i, dla dowodu niewprost, niech

\( m_ia\ \equiv_{n}m_ja . \)

Wtedy \( n|(m_j-m_i)a \), a ponieważ \( n\perp a \), to \( n|m_j-m_i \), co jest niemożliwe wobec \( 0 < m_j-m_i < n \).

Ponadto pokażmy, że każde \( a_i \) jest względnie pierwsze z \( n \). Załóżmy zatem, że \( d|a_i \) oraz \( d|n \). Ponieważ \( a_i=m_ia-qn \) dla pewnego \( q \), to \( d|m_i a \). Z drugiej strony \( d|n \), \( n \perp m_i \) i \( n \perp a \), co daje \( d\perp m \) i \( d\perp a \). A więc \( d=1 \), czyli w istocie \( a_i \perp n \).

Wiemy więc, że liczby \( a_1,\ldots,a_{\varphi(n)} \) przyjmują wszystkie wartości \( m_1,\ldots,m_{\varphi(n)} \) i każdą tylko raz. A zatem

\( m_1a\cdot m_2a\cdot\ldots\cdot m_{\varphi(n)}a \equiv_n a_1\cdot a_2\ldots a_{\varphi(n)} =m_1\cdot m_2\cdot\ldots\cdot m_{\varphi(n)}. \)

Ponieważ liczby \( m_1,\ldots,m_{\varphi(n)} \) są względnie pierwsze z \( n \) możemy zastosować regułę skracania, by dostać

\( a^{\varphi(m)}\ \equiv_{n}1 . \)

Zastosowanie Twierdzenia Eulera do szybkiego potęgowania.

Twierdzenie Eulera, tak jak uprzednio Twierdzenie Fermata, możemy wykorzystać do przyspieszenia potęgowania modularnego. Wymaga to jednak, by podstawa potęgi była względnie pierwsza z modułem \( n \). Jest to istotnie słabszy warunek, niż ten wymagany przez Małe Twierdzenie Fermata. Zwracamy jednak uwagę, że aby zastosować Twierdzenie Eulera musimy w szczególności znać wartość funkcji \( \varphi \) dla modułu \( n \). Jak się przekonamy podczas poznawania algorytmu RSA, wartość \( \varphi(n) \) jest jednak jest tak trudna do policzenia, jak rozkład \( n \) na czynniki pierwsze.

Przykład

Spróbujmy policzyć \( 13^{101} \ {\sf mod} \ 16 \).

  • \( 13\perp16 \), czyli możemy skorzystać z Twierdzenia Eulera,
  • \( \varphi(16)=8 \),
  • \( 101 \ {\sf mod} \ 8 =5 \),
  • \( 13^{101}\equiv_{16} 13^5 \),
  • \( 5=(101)_2 \),
  • liczymy wybrane potęgi \( 13 \) modulo \( 16 \):
    • \( 13^1\equiv_{16}13 \),
    • \( 13^2\equiv_{16}13\cdot13= 169 \equiv_{16} 9 \),
    • \( 13^4\equiv_{16}9\cdot9=81\equiv_{16}1 \).
  • \( 13^{101}\equiv_{16}13^5=13^4\cdot13^1\equiv_{16}1\cdot13=13 \).

Funkcja Mobiusa

Choć Wniosek 11.13 wyprowadziliśmy już bezpośrednio z Obserwacji 11.11 i 11.12, na zakończenie tego wykładu przedstawimy jego alternatywny dowód. Metoda użyta w tym alternatywnym dowodzie będzie przydatna w kilku innych sytuacjach.

Dowód

Niech \( n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \) będzie rozkładem na liczby pierwsze \( p_i \), w którym \( \alpha_i\geq 1 \). Zdefiniujmy \( A_i \) jako zbiór wielokrotności liczby \( p_i \) w \( {\{ {1,\ldots,n-1} \} } \). Wtedy \( \varphi(n)=n-\vert A_1\cup\ldots\cup A_k\vert \). Korzystając z Zasady Włączania i Wyłączania otrzymujemy

\( \varphi(n)=n-\vert A_1\cup\ldots\cup A_k\vert=n-\alpha_1+\alpha_2-\ldots+(-1)^k\alpha_k, \)

gdzie \( \displaystyle \alpha_i=\sum_{1\leq j_1 < \ldots < j_i\leq k}\vert A_{j_1}\cap\ldots\cap A_{j_i}\vert \). Zauważmy, że zbiór \( A_{j_1}\cap\ldots\cap A_{j_i} \) składa się z wielokrotności liczby \( P=p_{j_1}\cdot\ldots\cdot p_{j_k} \), czyli liczb \( P,2P,\ldots,(\frac{n}{P})P \). Zatem \( \vert A_{j_1}\cap\ldots\cap A_{j_i}\vert=\frac{n}{P}=\frac{n}{p_{i_1}\cdot\ldots\cdot p_{j_i}} \), skąd

\( \displaystyle \alpha_i=\sum_{1\leq j_1 < \ldots < j_i\leq k}\frac{n}{p_{j_1}\cdot\ldots\cdot p_{j_i}}=n\sum_{1\leq j_1 < \ldots < j_i\leq k}\frac{1}{p_{j_1}\cdot\ldots\cdot p_{j_i}}. \)

Teraz łatwo już policzyć

\( \begin{align*} \varphi(n) & =n-\alpha_1+\alpha_2-\alpha_3+\ldots+(-1)^k\alpha_k \\ & =n-n(\frac{1}{p_1}+\frac{1}{p_2}+\ldots+\frac{1}{p_k})+n(\frac{1}{p_1p_2}+\frac{1}{p_1p_3}+\ldots)-\ldots \\ & & \ldots+n(-1)^k\frac{1}{p_1\cdot\ldots\cdot p_k}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(*) \\ & =n(1-\frac{1}{p_1})\cdot\ldots\cdot(1-\frac{1}{p_k}). \end{align*} \)

Przyjrzyjmy się temu dowodowi trochę dokładniej. Analizując ostatnią sumę dla \( n=60=2^2\cdot3\cdot5 \) mamy

\( \varphi(60)=\frac{60}{1}-(\frac{60}{2}+\frac{60}{3}+\frac{60}{5})+(\frac{60}{6}+\frac{60}{10}+\frac{60}{15})-\frac{60}{30}. \)

Po prawej stronie mamy naprzemienną sumę składników \( \frac{n}{d} \), gdzie \( d \) przebiega kolejne dzielniki liczby \( n \), będące iloczynem różnych liczb pierwszych. Czynnik jest dodawany, jeśli \( d \) jest iloczynem parzystej liczby liczb pierwszych i odejmowany, jeśli \( d \) jest iloczynem nieparzystej liczby liczb pierwszych. Zależność tę możemy ogólniej zapisać w postaci

\( \displaystyle \varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}, \)

gdzie \( \mu(d) \) zadana jest przez:

\( \mu(d)= \left\{\begin{array} {cl} 1, & \textrm{jeśli d=1,} \\ (-1)^k, & \textrm{jeśli d jest iloczynem k różnych liczb pierwszych,} \\ 0, & \textrm{jeśli w rozkładzie d któryś z czynników się powtarza.} \end{array} \right. \)

Funkcja \( \mu(d) \) jest znana jako funkcja Mobiusa, na cześć niemieckiego matematyka Augusta Ferdynanda Mobiusa, który jako pierwszy użył jej w 1831 roku. Funkcja Mobiusa pojawia się nieoczekiwanie w wielu rozważaniach Matematyki Dyskretnej. Pojawi się też i u nas w wykładach poświęconych teorii grup i teorii ciał.

Obserwacja 11.15

Dla dowolnego \( n\geq2 \) mamy \( \displaystyle \sum_{d|n}\mu(d)=0. \)

Dowód

Niech \( n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha} \). Wtedy każdy dzielnik \( d \) liczby \( n \) ma rozkład \( d=p_1^{\beta_1}\cdot\ldots\cdot p_k^{\beta_k} \), gdzie \( 0\leq\beta_i\leq\alpha_i \). Jeśli choć jedno \( \beta_i>1 \), to \( \mu(d)=0 \). Rozważmy więc tylko te dzielniki dla których \( \beta_i\in{\{ {0,1} \} } \). Każdy taki dzielnik wyznacza jednoznacznie pewien podzbiór zbioru \( {\{ {1,\ldots,k} \} } \), przy czym wartościom \( d \), dla których \( \mu(d)=1 \) odpowiadają podzbiory o parzystej liczbie elementów, a wartościom \( d \), dla których \( \mu(d)=-1 \) odpowiadają podzbiory o nieparzystej liczbie elementów. A zatem:

\( \displaystyle \sum_{d|n}\mu(d)=1-{k\choose 1}+{k\choose2}- \ldots+(-1)^k{k\choose k}=0. \)

Obserwacja 11.16 [wzór inwersyjny Mobiusa]

Dla dowolnych funkcji \( f,g : \mathbb{N} \longrightarrow \mathbb{R} \), jeśli \( \displaystyle f(n)=\sum_{d|n}g(d) \), to \( \displaystyle g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) \).

Dowód

Ponieważ

\( \displaystyle f(n)= \sum_{d|n}g(d), \)

\( \begin{align*} \sum_{d|n} \mu(d) f(\frac{n}{d}) & =\sum_{d|n} \mu(d)\sum_{c|\frac{n}{d}}g(c) \\ & =\sum_{d|n,c|\frac{n}{d}} \mu(d)g(c). \end{align*} \)

Zauważmy, iż \( {\{ {(c,d):d|n,c|\frac{n}{d}} \} }={\{ {(c,d):c|n,d|\frac{n}{c}} \} } \). Zatem

\( \begin{align*} \sum_{d|n} \mu(d) f(\frac{n}{d}) & =\sum_{c|n,d|\frac{n}{c}}\mu(d)g(c) \\ & =\sum_{c|n}g(c)\sum_{d|\frac{n}{c}}\mu(d). \end{align*} \)

Z Obserwacji 11.15 wiemy, że wewnętrze sumy zerują się dla wszystkich \( \frac{n}{c}\geq2 \). Zatem jedyny interesujący składnik zewnętrznej sumy dostajemy przy \( c=n \):

\( \begin{align*} \sum_{d|n} \mu(d) f(\frac{n}{d}) & =\sum_{c|n}g(c)\sum_{d|\frac{n}{c}}\mu(d) \\ & =g(n)\sum_{d|1}\mu(d)=g(n)\mu(1)=g(n). \end{align*} \)

Jako ćwiczenie pozostawiamy użycie wzoru inwersyjnego Mobiusa do wyprowadzenia następującego wniosku:

Wniosek 11.17

\( \sum_{d|n} \varphi(d) = n \).