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ż Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,n)=1} w następujący sposób:

• jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a',n')=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ć Parser nie mógł rozpoznać (błąd składni): {\displaystyle d:=\mbox{\sf NWD}(a,n)} oraz współczynniki $y,z$ takie, że $ya+zn=d$,

• jeśli $d=1$, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_0 =yb \mbox{ {\sf mod} } 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$.

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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$.

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(3,12)=3} , ale $3|4$, czyli równanie nie ma rozwiązania.

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x&\equiv_{n_1}&a_1,\nonumber \\ x&\equiv_{n_2}&a_2,\nonumber \\ &\vdots& \\ x&\equiv_{n_k}&a_k.\nonumber \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned a&\equiv_{n_1}&b,\\ a&\equiv_{n_2}&b,\\ &\vdots&\\ a&\equiv_{n_k}&b. \endaligned}

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, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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ń:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x&\equiv_3& 2,\\ x&\equiv_{10}& 7,\\ x&\equiv_{11}& 10,\\ x&\equiv_7& 1. \endaligned}

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(3,10)=\mbox{\sf NWD}(3,11)=\mbox{\sf NWD}(3,7)=\mbox{\sf NWD}(10,11)=\mbox{\sf NWD}(10,7)=\mbox{\sf NWD}(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$:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(3,770)=1=257\cdot3-1\cdot770} , $x_1=-1{\equiv }_{3}2$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(10,231)=1=-23\cdot10+1\cdot231} , $x_2=1$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(11,210)=1=-19\cdot11+1\cdot210} , $x_3=1$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(7,330)=1=-47\cdot7+1\cdot330} , $x_4=1$.

Pozostaje policzyć $x$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x&=2\cdot2\cdot770+7\cdot1\cdot231+10\cdot1\cdot210+1\cdot1\cdot330\\ &=3080+1617+2100+330\\ &=7127\equiv_{2310} 197. \endaligned}

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ń:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x&\equiv_2&0,\\ x&\equiv_{13}&12,\\ x&\equiv_{15}&2. \endaligned}

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(2,13)=\mbox{\sf NWD}(2,15)=\mbox{\sf NWD}(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$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(2,195)=1=-97\cdot2+1\cdot195} , $x_1=1$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(13,30)=1=7\cdot13-3\cdot30} , $x_2=-3{\equiv }_{13}10$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(15,26)=1=7\cdot15-4\cdot26} , $x_3=-4{\equiv }_{15}11$.

Pozostaje nam obliczenie $x$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x&=0\cdot1\cdot195+12\cdot10\cdot30+2\cdot26\cdot11=4172\equiv_{390}=272. \endaligned}

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

Potęgowanie modularne

Potęgowanie modularne.

Naszym celem jest policzenie

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a^b \mbox{ {\sf mod} } 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle (a')^b \mbox{ {\sf mod} } n } , jako że Parser nie mógł rozpoznać (błąd składni): {\displaystyle (a')^b \mbox{ {\sf mod} } n =a^b \mbox{ {\sf mod} } 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle a^b \mbox{ {\sf mod} } n =\prod_{i=0}^{k-1}a^{b_i2^i} \mbox{ {\sf mod} } n } . Policzmy zatem w następujacy sposób kolejne potęgi $a$ występujące w iloczynie:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned a\cdot a \mbox{ {\sf mod} } n &\equiv_n&a^2 \mbox{ {\sf mod} } n ,\\ (a^2 \mbox{ {\sf mod} } n )\cdot(a^2 \mbox{ {\sf mod} } n )&\equiv_n&a^4 \mbox{ {\sf mod} } n ,\\ &\ldots&\\ (a^{2^{k-2}} \mbox{ {\sf mod} } n )\cdot(a^{2^{k-2}} \mbox{ {\sf mod} } n )&\equiv_n&a^{2^{k-1}} \mbox{ {\sf mod} } n . \endaligned}

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 7^{12} \mbox{ {\sf mod} } 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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 3^{51} \mbox{ {\sf mod} } 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 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_k = ka \mbox{ {\sf mod} } 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.

{

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:

{

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

Lemat

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert} 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert} 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ż Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert=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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert|p} , a skoro $p$ jest liczbą pierwszą, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert=1} lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertv\right\vert=p=\left\vertw\right\vert} . 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 7^{126} \mbox{ {\sf mod} } 11 } .

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle 126 \mbox{ {\sf mod} } 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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varphi(n)=\left\vert{\left\{ {1\leq a<n\quad:\quad \mbox{\sf NWD}(a,n)=1} \right\} }\right\vert. }

Obserwacja

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,mn)=1} wtedy i tylko wtedy, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,m)=1=\mbox{\sf NWD}(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

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \varphi(n) &=\varphi(p_1^{\alpha_1})\ldots\varphi(p_k^{\alpha_k})\\ &=p_1^{\alpha_1}\left(1-\frac{1}{p_1}\right)p_2^{\alpha_2}\left(1-\frac{1}{p_2}\right)\ldots p_k^{\alpha_k}\left(1-\frac{1}{p_k}\right)\\ &=n\cdot\prod_{p|n}\left(1-\frac{1}{p}\right), \endaligned}

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}{)}^2(1-\frac{1}{3}{)}^2\cdot (1-\frac{1}{5})\cdot (1-\frac{1}{11})=480$.

Twierdzenie Euler 1736

Dla dowolnych $a,n$, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_i = m_i a \mbox{ {\sf mod} } 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ć Parser nie mógł rozpoznać (błąd składni): {\displaystyle 13^{101} \mbox{ {\sf mod} } 16 } .

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

• $\phi (16)=8$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle 101 \mbox{ {\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\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 Uzupelnic phi(n)| wyprowadziliśmy już bezpośrednio z Obserwacji Uzupelnic phi(p)| i Uzupelnic phi iloczynu|, 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varphi(n)=n-\left\vertA_1\cup\ldots\cup A_k\right\vert} . Korzystając z Zasady Włączania i Wyłączania otrzymujemy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varphi(n)=n-\left\vertA_1\cup\ldots\cup A_k\right\vert=n-\alpha_1+\alpha_2-\ldots+(-1)^k\alpha_k, }

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha_i=\sum_{1\leq j_1<\ldots<j_i\leq k}\left\vertA_{j_1}\cap\ldots\cap A_{j_i}\right\vert} . 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA_{j_1}\cap\ldots\cap A_{j_i}\right\vert=\frac{n}{P}=\frac{n}{p_{i_1}\cdot\ldots\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ć

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \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}). \endaligned}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \mu(d)= \left\{\begin{array} {cl} 1,&\textrm{jeśli \textsl{d}=1,}\\ (-1)^k,&\textrm{jeśli \textsl{d} jest iloczynem \textsl{k} różnych liczb pierwszych,}\\ 0,&\textrm{jeśli w rozkładzie \textsl{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

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \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). \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \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). \endaligned}

Z Obserwacji Uzupelnic obserwacja - suma naprzemienna mu| 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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \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). \endaligned}

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

Wniosek

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