Informatyka MIMUW

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