Matematyka dyskretna 1/Wykład 11: Teoria liczb II

Arytmetyka modularna

Liczby przystające modulo $n>0$ to takie dwie liczby $a,b\in \mathbb{\mathbb{Z}}$, dla których różnica $a-b$ jest wielokrotnością $n$. Fakt ten zapisujemy jako $a{\equiv }_{n}b$. Innymi słowy, $a{\equiv }_{n}b$ jeśli $a$ i $b$ mają te same reszty w dzieleniu przez $n$.

Obserwacja 11.

Dla dowolnych $a,b,c$ oraz $n>0$ zachodzi:

• $a{\equiv }_{n}a$,

• $a{\equiv }_{n}b$ wtedy i tylko wtedy, gdy $b{\equiv }_{n}a$,

• jeśli $a{\equiv }_{n}b$ i $b{\equiv }_{n}c$ to $a{\equiv }_{n}c$.

Powyższe własności świadczą o tym, że przystawanie ${\equiv }_n$ modulo $n$ jest relacją równoważności na zbiorze $\mathbb{\mathbb{Z}}$. Dlatego czasem relacja ta nazywana jest równością modulo $n$. Okazuje się też, że relacja ${\equiv }_n$ jest zgodna z działaniami arytmetycznymi: dodawania, odejmowania i mnożenia, a więc jest kongruencją ze względu na te działania.

Obserwacja 11.2

Dla dowolnych $a,b,c,d$ oraz $n>0$ mamy:

• jeśli $a{\equiv }_{n}b$ i $c{\equiv }_{n}d$, to $a+c{\equiv }_{n}b+d$,

• jeśli $a{\equiv }_{n}b$ i $c{\equiv }_{n}d$, to $a-c{\equiv }_{n}b-d$,

• jeśli $a{\equiv }_{n}b$ i $c{\equiv }_{n}d$, to $ac{\equiv }_{n}bd$.

Podane w dwu poprzednich obserwacjach własności relacji równości modulo $n$ pozwalają na wprowadzenie działań w zbiorze ilorazowym $\mathbb{\mathbb{Z}}/{\equiv }_n$, tzn. w zbiorze klas równoważności. $\left\{[a{]}_n:a\in \mathbb{\mathbb{Z}}\right\}$, poprzez:

• $[a{]}_n+[b{]}_n=[a+b{]}_n$,

• $[a{]}_n-[b{]}_n=[a-b{]}_n$,

• $[a{]}_n\cdot [b{]}_n=[a\cdot b{]}_n$,

Ponieważ w każdej klasie $[a{]}_n$ jest jakaś liczba spośród $0,1,2,\dots ,n-1$, a mianowicie reszta z dzielenia liczby $a$ przez $n$, to wygodniej jest po prostu mówić o arytmetyce (modularnej) na zbiorze tych reszt $\left\{0,1,2,\dots ,n-1\right\}$ i pisać np.:

• $3+5{\equiv }_{6}2$,

• $3-5{\equiv }_{6}4$,

• $3\cdot 5{\equiv }_{6}3$.

Tak więc, dla $n>0$ możemy zidentyfikować zbiór ilorazowy $\mathbb{\mathbb{Z}}/{\equiv }_n$ ze zbiorem ${\mathbb{\mathbb{Z}}}_n=\left\{0,\dots n-1\right\}$ reszt modulo $n$. Po wprowadzeniu do tego zbioru działań arytmetycznych dostajemy pierścień, przemienny z jedynką ${\mathbb{\mathbb{Z}}}_n=(\left\{0,\dots n-1\right\},+,\cdot )$. Pierścień ten nie zawsze jest jednak ciałem. Istotnie, nie zawsze możemy skracać w mnożeniu czynnik zachowując kongruencję. Dla przykładu: $2\cdot 2=4{\equiv }_{6}10=2\cdot 5$, ale $2{\equiv }_{6}5$. Okazuje się, że w równości modulo $n$ możemy skracać czynniki względnie pierwsze z $n$.

Obserwacja 11.3 [Reguła skracania]

Dla $n>0$, jeśli $ad{\equiv }_{n}bd$ i $d\perp n$, to $a{\equiv }_{n}b$.

Dowód

Ponieważ $\mathsf{N}\mathsf{W}\mathsf{D}(d,n)=1$, rozszerzony algorytm Euklidesa gwarantuje istnienie $x,y\in \mathbb{\mathbb{Z}}$ takich, że $xd+yn=1$, czyli $dx{\equiv }_{n}1$. Mnożąc teraz obie strony $ad{\equiv }_{n}bd$ przez $x$, otrzymujemy $adx{\equiv }_{n}bdx$, czyli $a=a1{\equiv }_{n}adx{\equiv }_{n}bdx{\equiv }_{n}b1=b$.

Przykład

• $15=3\cdot 5{\equiv }_{7}10\cdot 5=50$ oraz $5\perp 7$ implikuje $3{\equiv }_{7}10$,

• $8=2^3{\equiv }_{3}2$ oraz $2\perp 3$ implikuje $4=2^2{\equiv }_{3}1$.

Chcąc móc skracać w pierscieniu ${\mathbb{\mathbb{Z}}}_n$ dowolne niezerowe czynniki wymagamy, by wszystkie liczby $1,2,\dots ,n-1$ były względnie pierwsze z $n$. To nic innego, jak wymaganie, by $n$ było liczbą pierwszą.

Obserwacja 11.4

Pierścień ${\mathbb{\mathbb{Z}}}_n=(\left\{0,\dots n-1\right\},+,\cdot )$ jest ciałem, wtedy i tylko wtedy, gdy $n$ jest liczba pierwszą.

Rozwiązywanie równań modularnych

Oczywiście w ciele, każde równanie postaci $ax=b$ ma dokładnie jedno rozwiązanie $x$, o ile $a\ne 0$. Zobaczmy czy są, jak wyglądają i jak otrzymać rozwiązania $x$ równania modularnego postaci $ax{\equiv }_{n}b$ w liczbach całkowitych $x$, gdzie $a,b\in \mathbb{\mathbb{Z}}$ oraz $a\ne 0$.

Obserwacja 11.5

Dla $a,b\in \mathbb{\mathbb{Z}},a\ne 0$ rozwiązania równania modularnego z jedną niewiadomą $x$:

$ax{\equiv }_{n}b$

zależą od wielkości $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=1$ w następujący sposób:

• jeśli $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=1$,

to istnieje nieskończenie wiele rozwiązań; wszystkie one są postaci $x=x_0+kn$, gdzie $0\le x_0<n$ jest jakimś rozwiązaniem, a $k\in \mathbb{\mathbb{Z}}$,

• jeśli $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=d>1$,

to równanie ma rozwiązanie wtedy i tylko wtedy, gdy również $d|b$. W tym przypadku rozwiązania równania $ax{\equiv }_{n}b$ pokrywają się z rozwiązaniami równania $\frac{a}{d}x{\equiv }_{\frac{n}{d}}\frac{b}{d}$.

Ponadto,

• ponadto, jeśli $0\le a,b<n$, to rozwiązanie $0\le x_0<n$

równania $ax{\equiv }_{n}b$, lub jego brak, można wskazać wykonując $O(l{g}^{3}n)$ operacji bitowych.

Dowód

Zauważmy najpierw, że jeśli $a^{\prime },b^{\prime }$ są resztami z dzielenia odpowiednio $a$ i $b$ przez $n$, to rozwiązania równań $ax{\equiv }_{n}b$ i $a^{\prime }x{\equiv }_n{b}^{\prime }$ są takie same. Istotnie, wynika to natychmiast z tego, że $a^{\prime }x{\equiv }_{n}ax$ oraz $b^{\prime }{\equiv }_{n}b$. Możemy więc przyjąć, że $0\le a,b<n$. Ponadto odnotujmy, że z tych samych powodów, jeśli $x_0$ spełnia równanie, to spełnia je również każda liczba postaci $x_0+kn$, gdzie $k\in \mathbb{\mathbb{Z}}$.

Załóżmy najpierw, że $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=1$. Rozszerzony algorytm Euklidesa gwarantuje istnienie $y,z$ takich, że $1{\equiv }_{n}ya+zn{\equiv }_{n}ya$. Łatwo teraz sprawdzić, że reszta $x_0$ z dzielenia $yb$ przez $n$ jest rozwiązaniem. A więc i wszystkie liczby postaci $x_0+kn$, są również rozwiązaniami. Pozostaje pokazać, że wszystkie rozwiązania są takiej właśnie postaci. Niech więc $ax{\equiv }_{n}b{\equiv }_{n}a{x}_0$. Ponieważ $a\perp n$, to $a$ możemy skrócić otrzymując $x{\equiv }_n{x}_0$, co implikuje że $x=x_0+kn$, dla pewnej liczby całkowitej $k$.

Niech teraz $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=d>1$. Najpierw pokażemy, że jeśli równanie $ax{\equiv }_{n}b$ ma rozwiązanie, to $d|b$. Rzeczywiście, jeśli $a{x}_0{\equiv }_{n}b$ dla pewnego $x_0$, to $n|ax-b$, a więc i $d|ax-b$. Ale $d|a$, więc $d|b$. Na odwrót, gdy $d|b$, to liczby $a,b,n$ są podzielne przez $n$. Niech więc $a^{\prime }=a/d$, $b^{\prime }=b/d$ i $n^{\prime }=n/d$. Wtedy $\mathsf{N}\mathsf{W}\mathsf{D}(a^{\prime },n^{\prime })=1$ i, na mocy pierwszego punktu, równanie $a^{\prime }x{\equiv }_{n^{\prime }}{b}^{\prime }$ ma nieskończenie wiele rozwiązań. Pozostaje pokazać, że są to te same rozwiązania, co dla równania $ax{\equiv }_{n}b$. Niech więc $n^{\prime }|a^{\prime }x-b^{\prime }$. Wtedy $n=d{n}^{\prime }|d(a^{\prime }x-b^{\prime })=ax-b$. Gdy zaś $ax{\equiv }_{n}b$, to $ax=b+kn$ dla pewnego $k\in \mathbb{\mathbb{Z}}$. A zatem $d{a}^{\prime }x=d{b}^{\prime }+kd{n}^{\prime }$ i, po wydzieleniu przez $d>1$, dostajemy $a^{\prime }x=b^{\prime }+k{n}^{\prime }$, czyli $a^{\prime }x{\equiv }_{n^{\prime }}{b}^{\prime }$.

Na podstawie dowodu poprzednich dwu punktów wiemy więc, że by rozwiązać równanie $ax{\equiv }_{n}b$ wystarczy:

• policzyć $d:=\mathsf{N}\mathsf{W}\mathsf{D}(a,n)$ oraz współczynniki $y,z$ takie, że $ya+zn=d$,

• jeśli $d=1$, to $x_0=yb\mathsf{m}\mathsf{o}\mathsf{d}n$ jest poszukiwanym rozwiązaniem,

• jeśli $d>1$ i $d|b$, to równanie nie posiada rozwiązań,

• jeśli $d>1$ i $d|b$, to $y\frac{b}{d}$ jest szukanym rozwiązaniem.

W pierwszym punkcie rozszerzony algorytm Euklidesa pracuje w czasie $O({\lg }^{3}n)$, bo $a,b<n$. W kolejnych punktach wykonywane są jedynie podstawowe operacje arytmetyczne, a więc wykonywanych jest $O({\lg }^{2}n)$ operacji bitowych. Podsumowując, aby znaleźć rozwiązanie rozważanego równania (bądź stwierdzić ich brak) wystarczy $O({\lg }^{3}n)$ operacji bitowych.

Wniosek 11.6

Jeśli $p$ jest liczbą pierwszą, to równania postaci $ax{\equiv }_{p}b$ dla dowolnych $0<a<p$ i $0\le b<p$ zawsze mają rozwiązanie i można je znaleźć wykonując $O(l{g}^{3}p)$ operacji bitowych.

Przykład

Rozwiążemy równanie $3x{\equiv }_{7}4$.

• $\mathsf{N}\mathsf{W}\mathsf{D}(3,7)=1$, czyli równanie ma nieskończenie wiele rozwiązań,

• $1=1\cdot 7-2\cdot 3$,

czyli zbiór rozwiązań to $\left\{-2\cdot 4+7k:k\in \mathbb{\mathbb{Z}}\right\}=\left\{7k-1:k\in \mathbb{\mathbb{Z}}\right\}$.

A następnie równanie $3x{\equiv }_{12}4$.

• $\mathsf{N}\mathsf{W}\mathsf{D}(3,12)=3$, ale $3|4$, czyli równanie nie ma rozwiązania.

Wreszcie rozważmy równanie $9x{\equiv }_{21}12$.

• $\mathsf{N}\mathsf{W}\mathsf{D}(9,21)=3$ oraz $3|12$, czyli równanie ma nieskończenie wiele rozwiązań,

• $3=1\cdot 21-2\cdot 9$,

czyli zbiór rozwiązań to $\left\{-2\cdot \frac{12}{3}+\frac{21}{3}k:k\in \mathbb{\mathbb{Z}}\right\}=\left\{13+7k:k\in \mathbb{\mathbb{Z}}\right\}$.

Czasem jedną kongruencję wygodnie jest zamienić na układ kongruencji wykorzystując następującą własność.

Obserwacja 11.7

Niech $a,b,m,n\in \mathbb{\mathbb{Z}}$, gdzie $m,n>0$ i $m\perp n$. Wtedy $a{\equiv }_{mn}b$ jest równoważne temu, że równocześnie $a{\equiv }_{m}b$ i $a{\equiv }_{n}b$.

Dowód

Jeśli $a{\equiv }_{mn}b$, to $mn|a-b$. A więc oczywiście $m|a-b$ i $n|a-b$, co jest równoważne z $a{\equiv }_{m}b$ i $a{\equiv }_{n}b$. Dla dowodu implikacji odwrotnej, że jest ona trywialna dla $a=b$ i wobec tego przyjmijmy (bez straty ogólności), że $a>b$. Załóżmy też, że $m|a-b$ i $n|a-b$. Ponieważ $m\perp n$, to rozkłady liczb $m$ i $n$ nie mają wspólnych czynników pierwszych. Natomiast rozkład $a-b$ musi zawierać wszystkie liczby pierwsze z rozkładów $m$ i $n$ w odpowiednio wysokich potęgach. To dowodzi, iż $mn|a-b$, czyli $a{\equiv }_{mn}b$.

Poprzednia obserwacja prowadzi do twierdzenia powszechnie znanego jako Chińskie Twierdzenie o Resztach. Udowodnił je chiński matematyk Sun Tzu w III wieku n.e. ( nie mylić z Sun Tzu, myślicielem, filozofem, autorem Sztuki wojny).

Twierdzenie 11.7 [Chińskie twierdzenie o resztach]

Niech $n_1,\dots ,n_k\in \mathbb{\mathbb{N}}-\left\{0\right\}$ będą parami względnie pierwsze, tzn. $n_i\perp n_j$ dla $i\ne j$. Wtedy dla dowolnych $a_1,\dots ,a_k$ istnieje dokładnie jedna liczba $0\le x<n_1\cdot \dots \cdot n_k$ taka, że:

$\begin{array}{rlr}x& {\equiv }_{n_1}& a_1,\\ x& {\equiv }_{n_2}& a_2,\\ & ⋮& \\ x& {\equiv }_{n_k}& a_k.\end{array}$

Dowód

Niech $N=n_1\cdot \dots \cdot n_k$. Dla liczby $a$ rozważmy ciąg $\bar{a}=(a_1,\dots ,a_k)$ reszt z dzielenia $a$ odpowiednio przez $n_1,\dots ,n_k$.

Niech teraz $0\le a<b<N$. Gdyby $\bar{a}=\bar{b}$, to

$\begin{array}{rlr}a& {\equiv }_{n_1}& b,\\ a& {\equiv }_{n_2}& b,\\ & ⋮& \\ a& {\equiv }_{n_k}& b.\end{array}$

Z drugiej strony $n_1\dots n_i\perp n_{i+1}$, więc stosując wielokrotnie Obserwację 11.7 otrzymujemy $i{\equiv }_{N}j$, czyli $N|j-i$, co jest niemożliwe wobec $0<j-i<N$. Sprzeczność ta pokazuje, że liczby ze zbioru $\left\{0,1,\dots ,N-1\right\}$ mają różne ciągi reszt. Oznacza to, że ciągów postaci $\bar{a}$ jest dokładnie $N$, czyli tyle ile wszystkich możliwych ciągów w ${\mathbb{\mathbb{Z}}}_{n_1}\times \dots \times {\mathbb{\mathbb{Z}}}_{n_k}$. Tym samym przyporządkowanie ${\mathbb{\mathbb{Z}}}_N\ni a\mapsto \bar{a}\in {\mathbb{\mathbb{Z}}}_{n_1}\times \dots \times {\mathbb{\mathbb{Z}}}_{n_k}$ jest bijekcją, co kończy dowód twierdzenia.

Chińskie Twierdzenie o Resztach podaje warunki wystarczające na istnienie rozwiązania układu równań modularnych (1). Nie podaje jednak metody jego uzyskania.

Konstrukcja rozwiązania.

Niech $N_j=N/n_j$, czyli $N_j$ jest iloczynem wszystkich $n_i$ poza $n_j$. Oczywiście, $\mathsf{N}\mathsf{W}\mathsf{D}(n_i,N_i)=1$. Rozszerzony algorytm Euklidesa pozwala więc znaleźć liczby $x_i$ takie, że $N_i{x}_i{\equiv }_{n_i}1$. Połóżmy

$x=\sum _{i=1}^k{a}_i{x}_i{N}_i$

Wtedy $n_i$ dzieli wszystkie czynniki sumy poza $i$-tym, ponieważ $n_i|N_j$ dla $j\ne i$. A więc, dla dowolnego $i$ mamy:

$x{\equiv }_{n_i}{a}_i{x}_i{N}_i{\equiv }_{n_i}{a}_i\cdot 1=a_i$

To oznacza, że $x$ jest rozwiązaniem układu równań modularnych (1).

Oszacujmy czas działania tego algorytmu. Niech $l_1,\dots ,l_k$ będą długościami odpowiednio $n_1,\dots ,n_k$. Wtedy $N$ ma długość co najwyżej $l=l_1+\dots +l_k$. Kroki algorytmu można wykonać kolejno w czasie:

• $O(kl)$ na wyliczenie wszystkich iloczynów postaci $N_i$ oraz całego iloczynu $N$,

• $O(k{l}^3)$ na wyliczenie kolejnych współczynników $x_i$, czyli $k$-krotną aplikację rozszerzonego algorytmu Euklidesa dla liczb $n_i,N_i\le N$,

• $O(k{l}^2)$ na obliczenie $x$, czyli $O(k)$ mnożeń i dodawań.

Podsumowując wszystkie kroki zostaną wykonane w czasie $O(k{\lg }^{3}N)$.

Przykład

Rozważmy układ równań:

$\begin{array}{rlr}x& {\equiv }_3& 2,\\ x& {\equiv }_{10}& 7,\\ x& {\equiv }_{11}& 10,\\ x& {\equiv }_7& 1.\end{array}$

• $\mathsf{N}\mathsf{W}\mathsf{D}(3,10)=\mathsf{N}\mathsf{W}\mathsf{D}(3,11)=\mathsf{N}\mathsf{W}\mathsf{D}(3,7)=\mathsf{N}\mathsf{W}\mathsf{D}(10,11)=\mathsf{N}\mathsf{W}\mathsf{D}(10,7)=\mathsf{N}\mathsf{W}\mathsf{D}(11,7)=1$,

czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,

• $N=3\cdot 7\cdot 10\cdot 11=2310$,

• $N_1=\frac{2310}{3}=770$,

• $N_2=\frac{2310}{10}=231$,

• $N_3=\frac{2310}{11}=210$,

• $N_4=\frac{2310}{7}=330$.

Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując $x_1,\dots ,x_4$:

• $\mathsf{N}\mathsf{W}\mathsf{D}(3,770)=1=257\cdot 3-1\cdot 770$, $x_1=-1{\equiv }_{3}2$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(10,231)=1=-23\cdot 10+1\cdot 231$, $x_2=1$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(11,210)=1=-19\cdot 11+1\cdot 210$, $x_3=1$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(7,330)=1=-47\cdot 7+1\cdot 330$, $x_4=1$.

Pozostaje policzyć $x$:

$\begin{array}{rl}x& =2\cdot 2\cdot 770+7\cdot 1\cdot 231+10\cdot 1\cdot 210+1\cdot 1\cdot 330\\ & =3080+1617+2100+330\\ & =7127{\equiv }_{2310}197.\end{array}$

A więc $197$ jest najmniejszym dodatnim rozwiązaniem naszego układu równości.

Przykład

Rozważmy jeszcze jeden układ równań:

$\begin{array}{rlr}x& {\equiv }_2& 0,\\ x& {\equiv }_{13}& 12,\\ x& {\equiv }_{15}& 2.\end{array}$

• $\mathsf{N}\mathsf{W}\mathsf{D}(2,13)=\mathsf{N}\mathsf{W}\mathsf{D}(2,15)=\mathsf{N}\mathsf{W}\mathsf{D}(13,15)=1$,

czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,

• $N=2\cdot 13\cdot 15=390$,

• $N_1=\frac{390}{2}=195$,

• $N_2=\frac{390}{13}=30$,

• $N_3=\frac{390}{15}=26$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(2,195)=1=-97\cdot 2+1\cdot 195$, $x_1=1$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(13,30)=1=7\cdot 13-3\cdot 30$, $x_2=-3{\equiv }_{13}10$,

• $\mathsf{N}\mathsf{W}\mathsf{D}(15,26)=1=7\cdot 15-4\cdot 26$, $x_3=-4{\equiv }_{15}11$.

Pozostaje nam obliczenie $x$:

$\begin{array}{rl}x& =0\cdot 1\cdot 195+12\cdot 10\cdot 30+2\cdot 26\cdot 11=4172{\equiv }_{390}=272.\end{array}$

Zatem $272$ jest najmniejszym dodatnim rozwiązaniem naszego układu równań.

Potęgowanie modularne

Potęgowanie modularne. Naszym celem jest policzenie

$a^b\mathsf{m}\mathsf{o}\mathsf{d}n$

Oczywiście, możemy założyć, że $0\le a<n$, bo inaczej najpierw można policzyć resztę $a^{\prime }$ z dzielenia $a$ przez $n$, a dopiero potem $(a^{\prime }{)}^b\mathsf{m}\mathsf{o}\mathsf{d}n$, jako że $(a^{\prime }{)}^b\mathsf{m}\mathsf{o}\mathsf{d}n=a^b\mathsf{m}\mathsf{o}\mathsf{d}n$. Zauważmy, że w przeciwieństwie do zwykłego potęgowania wynik nigdy nie przekracza $n$, czyli nie rośnie wykładniczo w stosunku do $a$. Pozwala to żywić nadzieję na szybsze algorytmy potęgujące. Dla rozgrzewki przeanalizujmy najpierw naiwny sposób liczenia potęgi modulo:

• Naiwne potęgowanie modulo. Wymnóż $a$ przez siebie $b$-krotnie, po każdym mnożeniu weź resztę modulo $n$. Branie reszty po każdym mnożeniu, utrzymuje tymczasowy iloczyn w zbiorze $\left\{0,\dots ,n-1\right\}$. Zatem wykonywanych jest $b$ mnożeń liczb $O(\log n)$-bitowych, czyli wykonywanych jest $O(b{\log }^{2}n)$ operacji bitowych. Jest to zatem algorytm działający w czasie wykładniczym względem rozmiaru wejścia $O(\log b+\log n)$.

• Szybkie potęgowanie modulo. Niech $b=(b_{k-1}\dots b_0{)}_2$ będzie binarnym zapisem liczby $b$. Zauważmy, że $a^b\mathsf{m}\mathsf{o}\mathsf{d}n=\prod _{i=0}^{k-1}{a}^{b_i{2}^i}\mathsf{m}\mathsf{o}\mathsf{d}n$.

Policzmy zatem w następujacy sposób kolejne potęgi $a$ występujące w iloczynie:

$\begin{array}{rlr}a\cdot a\mathsf{m}\mathsf{o}\mathsf{d}n& {\equiv }_n& a^2\mathsf{m}\mathsf{o}\mathsf{d}n,\\ (a^2\mathsf{m}\mathsf{o}\mathsf{d}n)\cdot (a^2\mathsf{m}\mathsf{o}\mathsf{d}n)& {\equiv }_n& a^4\mathsf{m}\mathsf{o}\mathsf{d}n,\\ & \dots & \\ (a^{2^{k-2}}\mathsf{m}\mathsf{o}\mathsf{d}n)\cdot (a^{2^{k-2}}\mathsf{m}\mathsf{o}\mathsf{d}n)& {\equiv }_n& a^{2^{k-1}}\mathsf{m}\mathsf{o}\mathsf{d}n.\end{array}$

Tym sposobem wykonanych zostanie $k-2$ mnożeń i dzieleń liczb $O(\log n)$-bitowych, czyli $O(k{\log }^{2}n)$ operacji bitowych. Aby otrzymać wynik musimy jeszcze wymnożyć przez siebie te potęgi, ktorym odpowiada bit $1$ w liczbie $b$. Wykonanych zostanie więc jeszcze co najwyżej $k$ mnożeń (które przeplatamy braniem reszty modulo $n$) liczb $O(\log n)$-bitowych.

W sumie wykonanych zostanie $O(k{\log }^{2}n)=O(\log b\cdot {\log }^{}n)$ operacji bitowych, a więc znacznie mniej niż sposobem naiwnym. Przedstawiony algorytm jest efektywny (wielomianowy względem długości wejścia).

Przykład

$7^{12}\mathsf{m}\mathsf{o}\mathsf{d}10=?$

• $12=(1100{)}_2$,

• wyznaczamy wybrane potęgi $7$ modulo $10$:
  • $7^2=49{\equiv }_{10}9$,
  • $7^4{\equiv }_{10}9\cdot 9=81{\equiv }_{10}1$,
  • $7^8{\equiv }_{10}1\cdot 1=1$,

• $7^{12}=7^8\cdot 7^4{\equiv }_{10}1\cdot 1=1$.

• wykonane zostały tylko $4$ mnożenia!

Przykład

$3^{51}\mathsf{m}\mathsf{o}\mathsf{d}13=?$

• $51=(110011{)}_2$,

• wyznaczamy wybrane potęgi $3$ modulo $13$:
  • $3^2=9$,
  • $3^4=9\cdot 9=81{\equiv }_{13}3$,
  • $3^8{\equiv }_{13}3\cdot 3=9$,
  • $3^{16}{\equiv }_{13}9\cdot 9=81{\equiv }_{13}3$,
  • $3^{32}{\equiv }_{13}3\cdot 3=9$.

• $3^{51}=3^{32}\cdot 3^{16}\cdot 3^2\cdot 3^1{\equiv }_{13}9\cdot 3\cdot 9\cdot 3=729{\equiv }_{13}1$.

Małe Twierdzenia Fermata

Małego Twierdzenia Fermata. nie należy mylić z tzw. Wielkim Twierdzeniem Fermata, które frapowało matematyków przez wiele stuleci i zostało ostatecznie udowodnione przez Andrew Wiles'a w 1994 roku.

Zgodnie ze swoim zwyczajem, podobnie jak i w przypadku Wielkiego Twierdzenia, Fermat przedstawił Małe Twierdzenie, nie podając dowodu. List, w którym się po raz pierwszy pojawiła ta teza, później nazwana Małym Twierdzeniem Fermata, został napisany dnia 18.IX.1640. Fermat dodał komentarz: "Propozycja ta jest prawdziwa dla wszystkich liczb pierwszych; jej dowód prześlę Ci, jeśli nie będzie zbyt długi". Pierwszy znany dowód tego twierdzenia przedstawił Leibniz w 1683 roku.

Twierdzenie 11.9 [Małe Twierdzenie Fermata]

Dla dowolnej $p$ liczby pierwszej i dowolnego $a$ zachodzi:

$a^p{\equiv }_{p}a$

Dowód

Poznamy trzy różne dowody. Najpierw jednak zauważmy, że bez straty ogólności możemy przyjąć iż $a\in \left\{0,\dots ,p-1\right\}$, gdyż w miejsce $a$ możemy rozważać resztę z dzielenia $a$ przez $p$. Ponadto, zwróćmy uwagę, iż dla $a=0$ teza jest oczywista, natomiast dla $a\in \left\{1,\dots ,p-1\right\}$ wystarczy udowodnić, że:

$a^{p-1}{\equiv }_{p}1$

Pierwszy dowód. Dla $a\in \left\{1,\dots ,p-1\right\}$ rozważmy ciąg

$a_0,a_1,a_2,\dots ,a_{p-1}$

reszt $a_k=ka\mathsf{m}\mathsf{o}\mathsf{d}p$ liczb $ka$ modulo $p$. Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech $0\le i<j<p$ i, dla dowodu niewprost, niech

$ia{\equiv }_{p}ja$

Wtedy $p|(j-i)a$. Ponieważ $p$ jest liczba pierwszą to $p|j-i$ lub $p|a$. Ponieważ jednak obie liczby $a$ oraz $j-i$ leżą w zbiorze $\left\{1,2,\dots ,p-1\right\}$, żaden z tych dwu przypadków nie jest możliwy. A zatem $\left\{a_0,a_1,a_2,\dots ,a_{p-1}\right\}=\left\{0,1,2,\dots ,p-1\right\}$. Oczywiście $a_0=0$, więc iloczyny pozostałych elementów w tych dwu zbiorach muszą być równe, co daje:

$a\cdot 2a\cdot \dots \cdot (p-1)a{\equiv }_p{a}_1\cdot a_2\cdot \dots \cdot a_{p-1}=1\cdot 2\cdot \dots \cdot (p-1)$,

lub inaczej:

$(p-1)!\cdot a^{p-1}{\equiv }_p(p-1)!$

Ponieważ $p$ jest liczbą pierwszą, wszystkie liczby ze zbioru $\left\{1,\dots ,p-1\right\}$ są względnie pierwsze z $p$, więc i $(p-1)!\perp p$. Można więc zastosować regułę skracania:

$a^{p-1}{\equiv }_{p}1$

Drugi dowód. Dla dowodu indukcyjnego względem $a=0,1,2,\dots ,p-1$ zauważmy najpierw, że w oczywisty sposób $0^p{\equiv }_{p}0$ oraz $1^p{\equiv }_{p}1$ i załóżmy, że $k^p{\equiv }_{p}k$. Aby udowodnić, że:

$(k+1{)}^p{\equiv }_{p}k+1$

pokażemy znacznie mocniejszą równość

$(x+y{)}^p{\equiv }_p{x}^p+y^p$,

która przy $x=k$ i $y=1$ pozwoli zakończyć dowód indukcyjny.

Rozwijając dwumian $(x+y{)}^p$ mamy:

$(x+y{)}^p=\sum _{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})x^i{y}^{p-i}$

Współczynnik $(\genfrac{}{}{0ex}{}{p}{i})=\frac{p!}{i!(p-i)!}$ jest zawsze liczbą całkowitą. Ponadto, jeśli $0<i<p$, to wszystkie czynniki obu silni mianownika są względnie pierwsze z $p$, bo $p$ jest pierwsza, a czynniki te są mniejsze niż $p$. Oznacza to, iż w rozkładzie $(\genfrac{}{}{0ex}{}{p}{i})$ na czynniki pierwsze musi znaleźć się $p$. To zaś implikuje $(\genfrac{}{}{0ex}{}{p}{i}){\equiv }_{p}0$ dla $0<i<p$. A więc

$(x+y{)}^p=\sum _{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})x^i{y}^{p-i}{\equiv }_p\sum _{i\in \left\{0,p\right\}}(\genfrac{}{}{0ex}{}{p}{i})x^i{y}^{p-i}=x^p+y^p$

Trzeci dowód. Niech $a\in \left\{1,\dots ,p-1\right\}$.

Rozważmy słowa długości $p$ nad alfabetem $a$-elementowym.

Przykład

Niech $p=7$, $a=3$. Symbolami alfabetu niech będą A,B,C.

Oto mocno skrócona lista $3^7=2187$ wszystkich słów $7$-literowych nad tym alfabetem.

	AAAAAAA,	AAAAAAB,	AAAAAAC,	AAAAABA,	AAAAABB,
	AAAAABC,	AAAAACA,	AAAAACB,	AAAAACC,	...
			...
	CCCCCBB,	CCCCCBC,	CCCCCCA,	CCCCCCB,	CCCCCCC.

Wszystkich takich słów jest $a^p$. Pokażemy, że po usunięciu słów jednoliterowych, pozostałe $a^p-a$ słów będzie można podzielić na rozłączne $p$-elementowe grupy. To oczywiście natychmiast da $p|a^p-a$, czyli pożądaną równość $a^p{\equiv }_{p}a$.

Słowo $v$ nazwiemy przesunięciem cyklicznym słowa $w=w_1\dots w_k$ o $i$ liter, jeśli

$v=w_{i+1}{w}_{i+2}\dots w_k{w}_1\dots w_{i-1}{w}_i$

Przykład

Przesunięcia cykliczne słowa CBAABCB:

	CBAABCB,	BAABCBC,	AABCBCB,	ABCBCBA,	BCBCBAA,
	CBCBAAB,	BCBAABC.

Przesunięcia cykliczne słowa ABCABC:

ABCABC,

BCABCA,

CABCAB.

Drugi przykład pokazuje, że niektóre przesuniecia cyklicze sa równe. W istocie mamy:

Lemat 11.10

Niech $v$ będzie słowem, którego nie da się przedstawić jako $u^l=u\dots u$, dla żadnego słowa $u$ i żadnej liczby $l>0$. Z kolei niech $w=v^k=v\dots v$, dla pewnego $k>0$. Wtedy słowo $w$ ma dokładnie $\left|v\right|$ różnych przesunięć cyklicznych.

Dowód

Oczywiście, jeśli liczba liter, o które różnią się dwa przesunięcia cykliczne jest wielokrotnością długousi słowa $v$, to te dwa przesunięcia dają to samo słowo. A zatem $w$ ma co najwyżej $\left|v\right|$ różnych przesunięć cyklicznych. Z drugiej strony, gdyby dwa przesunięcia cykliczne słowa $v$ były równe, to dawałyby to samo słowo. Istotnie, gdy $v=v_1\dots v_m$ i $v_1,\dots ,v_m$ są literami alfabetu, to każde przesunięcie cykliczne prowadzi do jednego ze słów z listy:

$\begin{array}{rcll}{v}_1{v}_2{v}_3\dots v_m& v^{k-1}& & ,\\ v_2{v}_3\dots v_m& v^{k-1}& v_1& ,\\ v_3\dots v_m& v^{k-1}& v_1{v}_2& ,\\ & ⋮& & \\ v_m& v^{k-1}& v_1\dots v_{m-1}& .\end{array}$

Ponieważ $\left|v\right|=m$, pozostaje pokazać, że słowa na tej liście sa różne. Dla dowodu niewprost, bez straty ogólności, możemy założyć, że:

$v_1\dots v_m{v}^{k-1}=v_i\dots v_m{v}^{k-1}{v}_1{v}_2\dots v_{i-1}$,

dla pewnego $1<i\le m$. Wtedy

$v_1\dots v_m=v_i\dots v_m{v}_1\dots v_{i-1}$

To z kolei prowadzi do ciągu równości w poniższym diagramie:

$\begin{array}{lcllcllcl}{v}_1& \dots & v_{m-(i-1)}& v_{m-(i-1)+1}& \dots & v_{m-2(i-1)}& v_{m-2(i-1)+1}& \dots & v_{m-3(i-1)}\dots \\ & \parallel & & & \parallel & & & \parallel & \\ v_i& \dots & v_m& v_1& \dots & v_{m-(i-1)}& v_{m-(i-1)+1}& \dots & v_{m-2(i-1)}\dots \end{array}$

Czyli słowo $v$ jest postaci $v=x^l$ dla $x=v_i\dots v_m$ i $l=\frac{m}{m-(i-1)}$, wbrew założeniom lematu.

Wyposażeni w Lemat, możemy powrócić do trzeciego dowodu Małego Twierdzenia Fermata. Niech więc $w$ będzie słowem, w którym występują dwie różne litery alfabetu. Słowo to nie może być postaci $v^l$, gdzie $l\ge 2$, gdyż inaczej $\left|v\right||p$, a skoro $p$ jest liczbą pierwszą, to $\left|v\right|=1$ lub $\left|v\right|=p=\left|w\right|$. W pierwszym przypadku $w$ jest jednoliterowe, a w drugim $v=w$ i $l=1$. A zatem każde z $a^p-a$ słów $w$ ma dokładnie $p$ różnych przesunięć cyklicznych. To dowodzi, iż $p|a^p-a$, czyli $a^p{\equiv }_{p}a$.

W jednym z dalszych wykładów poznamy jeszcze jeden dowód Małego Twierdzenia Fermata, oparty na elementarnej wiedzy z teorii grup.

Potęgowanie modulo liczba pierwsza.

Wykorzystując Małe Twierdzenie Fermata możemy trochę poprawić szybkość potęgowania modularnego. Asymptotycznie jednak złożoność pozostanie taka sama. Zauważmy bowiem, że:

$a^b{\equiv }_p{a}^{b^{\prime }}$,

gdzie $b^{\prime }$ jest resztą z dzielenia $b$ przez $p-1$.

Przykład

Policzmy $7^{126}\mathsf{m}\mathsf{o}\mathsf{d}11$.

• $11$ jest liczba pierwszą, czyli możemy skorzystać z Małego Twierdzenia Fermata,

• $126\mathsf{m}\mathsf{o}\mathsf{d}10=6$,

• $7^{126}{\equiv }_{11}{7}^6$,

• $6=(110{)}_2$,

• liczymy wybrane potęgi $7$ modulo $11$:
  • $7^2=49{\equiv }_{11}5$,
  • $7^4{\equiv }_{11}5\cdot 5=25{\equiv }_{11}4$.

• $7^{127}{\equiv }_{11}{7}^6=7^4\cdot 7^2{\equiv }_{11}4\cdot 5=20{\equiv }_{11}9$.

• wykonaliśmy $3$ mnożenia.

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 $\phi$-Eulera to $\phi :\mathbb{\mathbb{N}}-\left\{0\right\}⟶\mathbb{\mathbb{N}}$ zdefiniowaną poprzez

$\phi (n)=\left|\left\{1\le a<n:\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=1\right\}\right|$

Obserwacja 11.11

Dla dowolnej liczby pierwszej $p$ zachodzi:

• $\phi (p)=p-1$,

• $\phi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}=p^{\alpha }(1-\frac{1}{p})$.

Dowód

Ponieważ $p$ jest pierwsza, liczby $1,2,\dots ,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 $\phi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$.

Obserwacja 11.12

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

$\phi (mn)=\phi (m)\phi (n)$

Dowód

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

$\mathsf{N}\mathsf{W}\mathsf{D}(a,mn)=1$ wtedy i tylko wtedy, gdy $\mathsf{N}\mathsf{W}\mathsf{D}(a,m)=1=\mathsf{N}\mathsf{W}\mathsf{D}(a,n)$.

To oznacza, iż liczb $0\le a<mn$ takich, że $a\perp mn$ jest dokładnie tyle co par $(i_1,i_2)$ takich, że $0\le i_1<m$, $0\le 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}\dots p_k^{{\alpha }_k}$ jest rozkładem na liczby pierwsze $p_i$, w którym ${\alpha }_i\ge 1$, to:

$\begin{array}{rl}\phi (n)& =\phi (p_1^{{\alpha }_1})\dots \phi (p_k^{{\alpha }_k})\\ & =p_1^{{\alpha }_1}(1-\frac{1}{p_1})p_2^{{\alpha }_2}(1-\frac{1}{p_2})\dots p_k^{{\alpha }_k}(1-\frac{1}{p_k})\\ & =n\cdot \prod _{p|n}(1-\frac{1}{p}),\end{array}$

gdzie ostatnim iloczyn przebiega po wszystkich liczbach pierwszych $p$ dzielących $n$.

Przykład

Policzmy $\phi (2006)$:

• $2006=2\cdot 17\cdot 59$,

• $\phi (2006)=2006\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{17})\cdot (1-\frac{1}{59})=928$.

Oraz $\phi (1980)$:

• $1980=2^2\cdot 3^2\cdot 5\cdot 11$,

• $\phi (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 $\mathsf{N}\mathsf{W}\mathsf{D}(a,n)=1$ zachodzi:

$a^{\phi (n)}{\equiv }_{n}1$

Dowód

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

$a_1,a_2,\dots ,a_{\phi (n)}$

reszt $a_i=m_{i}a\mathsf{m}\mathsf{o}\mathsf{d}n$ liczb $m_{i}a$ modulo $n$. Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech $1\le i<j\le \phi (n)$ i, dla dowodu niewprost, niech

$m_{i}a{\equiv }_n{m}_{j}a$

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_{i}a-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,\dots ,a_{\phi (n)}$ przyjmują wszystkie wartości $m_1,\dots ,m_{\phi (n)}$ i każdą tylko raz. A zatem

$m_{1}a\cdot m_{2}a\cdot \dots \cdot m_{\phi (n)}a{\equiv }_n{a}_1\cdot a_2\dots a_{\phi (n)}=m_1\cdot m_2\cdot \dots \cdot m_{\phi (n)}$

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

$a^{\phi (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 $\phi$ dla modułu $n$. Jak się przekonamy podczas poznawania algorytmu RSA, wartość $\phi (n)$ jest jednak jest tak trudna do policzenia, jak rozkład $n$ na czynniki pierwsze.

Przykład

Spróbujmy policzyć $13^{101}\mathsf{m}\mathsf{o}\mathsf{d}16$.

• $13\perp 16$, czyli możemy skorzystać z Twierdzenia Eulera,

• $\phi (16)=8$,

• $101\mathsf{m}\mathsf{o}\mathsf{d}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\cdot 13=169{\equiv }_{16}9$,
  • $13^4{\equiv }_{16}9\cdot 9=81{\equiv }_{16}1$.

• $13^{101}{\equiv }_{16}13^5=13^4\cdot 13^1{\equiv }_{16}1\cdot 13=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}\dots p_k^{{\alpha }_k}$ będzie rozkładem na liczby pierwsze $p_i$, w którym ${\alpha }_i\ge 1$. Zdefiniujmy $A_i$ jako zbiór wielokrotności liczby $p_i$ w $\left\{1,\dots ,n-1\right\}$. Wtedy $\phi (n)=n-|A_1\cup \dots \cup A_k|$. Korzystając z Zasady Włączania i Wyłączania otrzymujemy

$\phi (n)=n-|A_1\cup \dots \cup A_k|=n-{\alpha }_1+{\alpha }_2-\dots +(-1{)}^k{\alpha }_k$,

gdzie ${\alpha }_i=\sum _{1\le j_1<\dots <j_i\le k}|A_{j_1}\cap \dots \cap A_{j_i}|$. Zauważmy, że zbiór $A_{j_1}\cap \dots \cap A_{j_i}$ składa się z wielokrotności liczby $P=p_{j_1}\cdot \dots \cdot p_{j_k}$, czyli liczb $P,2P,\dots ,(\frac{n}{P})P$. Zatem $|A_{j_1}\cap \dots \cap A_{j_i}|=\frac{n}{P}=\frac{n}{p_{i_1}\cdot \dots \cdot p_{j_i}}$, skąd

${\alpha }_i=\sum _{1\le j_1<\dots <j_i\le k}\frac{n}{p_{j_1}\cdot \dots \cdot p_{j_i}}=n\sum _{1\le j_1<\dots <j_i\le k}\frac{1}{p_{j_1}\cdot \dots \cdot p_{j_i}}$

Teraz łatwo już policzyć

$\begin{array}{rl}\phi (n)& =n-{\alpha }_1+{\alpha }_2-{\alpha }_3+\dots +(-1{)}^k{\alpha }_k\\ & =n-n(\frac{1}{p_1}+\frac{1}{p_2}+\dots +\frac{1}{p_k})+n(\frac{1}{p_1{p}_2}+\frac{1}{p_1{p}_3}+\dots )-\dots \\ & & \dots +n(-1{)}^k\frac{1}{p_1\cdot \dots \cdot p_k}(*)\\ & =n(1-\frac{1}{p_1})\cdot \dots \cdot (1-\frac{1}{p_k}).\end{array}$

Przyjrzyjmy się temu dowodowi trochę dokładniej. Analizując ostatnią sumę dla $n=60=2^2\cdot 3\cdot 5$ mamy

$\phi (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

$\phi (n)=\sum _{d|n}\mu (d)\frac{n}{d}$,

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

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

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⩾2$ mamy $\sum _{d|n}\mu (d)=0$

Dowód

Niech $n=p_1^{{\alpha }_1}\cdot \dots \cdot p_k^{\alpha }$. Wtedy każdy dzielnik $d$ liczby $n$ ma rozkład $d=p_1^{{\beta }_1}\cdot \dots \cdot p_k^{{\beta }_k}$, gdzie $0⩽{\beta }_i⩽{\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 \left\{0,1\right\}$. Każdy taki dzielnik wyznacza jednoznacznie pewien podzbiór zbioru $\left\{1,\dots ,k\right\}$, 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:

$\sum _{d|n}\mu (d)=1-(\genfrac{}{}{0ex}{}{k}{1})+(\genfrac{}{}{0ex}{}{k}{2})-\dots +(-1{)}^k(\genfrac{}{}{0ex}{}{k}{k})=0$

Obserwacja 11.16 [wzór inwersyjny Mobiusa]

Dla dowolnych funkcji $f,g:\mathbb{\mathbb{N}}⟶\mathbb{ℝ}$, jeśli $f(n)=\sum _{d|n}g(d)$, to $g(n)=\sum _{d|n}\mu (d)f(\frac{n}{d})$.

Dowód

Ponieważ

$f(n)=\sum _{d|n}g(d)$,

to

$\begin{array}{rl}\sum _{d|n}\mu (d)f\left(\frac{n}{d}\right)& =\sum _{d|n}\mu (d)\sum _{c|\frac{n}{d}}g(c)\\ & =\sum _{d|n,c|\frac{n}{d}}\mu (d)g(c).\end{array}$

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

$\begin{array}{rl}\sum _{d|n}\mu (d)f\left(\frac{n}{d}\right)& =\sum _{c|n,d|\frac{n}{c}}\mu (d)g(c)\\ & =\sum _{c|n}g(c)\sum _{d|\frac{n}{c}}\mu (d).\end{array}$

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

$\begin{array}{rl}\sum _{d|n}\mu (d)f\left(\frac{n}{d}\right)& =\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{array}$

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

Wniosek 11.17

$\sum _{d|n}\phi (d)=n$.