Liczby przystające modulo \( n>0 \) to takie dwie liczby \( a,b\in\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:
Powyższe własności świadczą o tym, że przystawanie \( \equiv_{n} \) modulo \( n \) jest relacją równoważności na zbiorze \( \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:
Podane w dwu poprzednich obserwacjach własności relacji równości modulo \( n \) pozwalają na wprowadzenie działań w zbiorze ilorazowym \( \mathbb{Z}/\equiv_n \), tzn. w zbiorze klas równoważności. \( {\{ {[a]_n : a\in \mathbb{Z}} \} } \), poprzez:
Ponieważ w każdej klasie \( [a]_n \) jest jakaś liczba spośród \( 0,1,2,\ldots,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 \( {\{ {0,1,2,\ldots,n-1} \} } \) i pisać np.:
Tak więc, dla \( n>0 \) możemy zidentyfikować zbiór ilorazowy \( \mathbb{Z}/\equiv_n \) ze zbiorem \( \mathbb{Z}_n={\{ {0,\ldots n-1} \} } \) reszt modulo \( n \). Po wprowadzeniu do tego zbioru działań arytmetycznych dostajemy pierścień, przemienny z jedynką \( \mathbb{Z}_n=({\{ {0,\ldots n-1} \} },+,\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\cdot2=4\ \equiv_{6}10 =2\cdot5 \), ale \( 2\not\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ż \( {\sf NWD}\ (d,n)=1 \), rozszerzony algorytm Euklidesa gwarantuje istnienie \( x,y\in \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
Chcąc móc skracać w pierscieniu \( \mathbb{Z}_n \) dowolne niezerowe czynniki wymagamy, by wszystkie liczby \( 1,2,\ldots,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{Z}_n=({\{ {0,\ldots n-1} \} },+,\cdot) \) jest ciałem, wtedy i tylko wtedy, gdy \( n \) jest liczba pierwszą.
Oczywiście w ciele, każde równanie postaci \( ax=b \) ma dokładnie jedno rozwiązanie \( x \), o ile \( a\neq 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{Z} \) oraz \( a\neq 0 \).
Obserwacja 11.5
Dla \( a,b \in \mathbb{Z}, a\neq 0 \) rozwiązania równania modularnego z jedną niewiadomą \( x \):
\( ax\ \equiv_{n}b , \)
zależą od wielkości \( {\sf NWD}\ (a,n)=1 \) w następujący sposób:
to istnieje nieskończenie wiele rozwiązań; wszystkie one są postaci \( x=x_0+kn \), gdzie \( 0\leq x_0 < n \) jest jakimś rozwiązaniem, a \( k\in\mathbb{Z} \),
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,
równania \( ax\ \equiv_{n}b \), lub jego brak, można wskazać wykonując \( O(lg^3{n}) \) operacji bitowych.
Dowód
Zauważmy najpierw, że jeśli \( a',b' \) są resztami z dzielenia odpowiednio \( a \) i \( b \) przez \( n \), to rozwiązania równań \( ax\ \equiv_{n}b \) i \( a'x\ \equiv_{n}b' \) są takie same. Istotnie, wynika to natychmiast z tego, że \( a'x\ \equiv_{n}ax \) oraz \( b'\ \equiv_{n}b \). Możemy więc przyjąć, że \( 0\leq 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{Z} \).
Załóżmy najpierw, że \( {\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 ax_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 \( {\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 \( ax_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'=a/d \), \( b'=b/d \) i \( n'=n/d \). Wtedy \( {\sf NWD}\ (a',n')=1 \) i, na mocy pierwszego punktu, równanie \( a'x\ \equiv_{n'}b' \) 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'|a'x-b' \). Wtedy \( n=dn'|d(a'x-b') = ax-b \). Gdy zaś \( ax\ \equiv_{n}b \), to \( ax=b+kn \) dla pewnego \( k\in\mathbb{Z} \). A zatem \( da'x=db'+kdn' \) i, po wydzieleniu przez \( d>1 \), dostajemy \( a'x=b'+kn' \), czyli \( a'x\ \equiv_{n'}b' \).
Na podstawie dowodu poprzednich dwu punktów wiemy więc, że by rozwiązać równanie \( ax\ \equiv_{n}b \) wystarczy:
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\leq b < p \) zawsze mają rozwiązanie i można je znaleźć wykonując \( O(lg^3{p}) \) operacji bitowych.
Przykład
Rozwiążemy równanie \( 3x\equiv_7 4 \).
czyli zbiór rozwiązań to \( {\{ {-2\cdot4+7k: k\in\mathbb{Z}} \} }={\{ {7k-1:k\in\mathbb{Z}} \} } \).
A następnie równanie \( 3x\equiv_{12}4 \).
Wreszcie rozważmy równanie \( 9x\equiv_{21}12 \).
czyli zbiór rozwiązań to \( {\{ {-2\cdot\frac{12}{3}+ \frac{21}{3}k : k\in\mathbb{Z}} \} }={\{ {13+7k : k\in\mathbb{Z}} \} } \).
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{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,\ldots,n_k\in\mathbb{N}-{\{ {0} \} } \) będą parami względnie pierwsze, tzn. \( n_i\perp n_j \) dla \( i\neq j \). Wtedy dla dowolnych \( a_1,\ldots,a_k \) istnieje dokładnie jedna liczba \( 0\leq x < n_1\cdot\ldots\cdot n_k \) taka, że:
\( \begin{align*} x & \equiv_{n_1} & a_1,\nonumber \\ x & \equiv_{n_2} & a_2,\nonumber \\ & \vdots & \\ x & \equiv_{n_k} & a_k.\nonumber \end{align*} \)
Dowód
Niech \( N=n_1\cdot\ldots\cdot n_k \). Dla liczby \( a \) rozważmy ciąg \( \overline{a}=(a_1,\ldots,a_k) \) reszt z dzielenia \( a \) odpowiednio przez \( n_1,\ldots,n_k \).
Niech teraz \( 0\leq a < b < N \). Gdyby \( \overline{a}=\overline{b} \), to
\( \begin{align*} a & \equiv_{n_1} & b, \\ a & \equiv_{n_2} & b, \\ & \vdots & \\ a & \equiv_{n_k} & b. \end{align*} \)
Z drugiej strony \( n_1\ldots 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 \( {\{ {0,1,\ldots,N-1} \} } \) mają różne ciągi reszt. Oznacza to, że ciągów postaci \( \overline{a} \) jest dokładnie \( N \), czyli tyle ile wszystkich możliwych ciągów w \( \mathbb{Z}_{n_1}\times\ldots\times\mathbb{Z}_{n_k} \). Tym samym przyporządkowanie \( \mathbb{Z}_N \ni a \mapsto \overline{a} \in \mathbb{Z}_{n_1}\times\ldots\times\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.
Niech \( N_j=N/n_j \), czyli \( N_j \) jest iloczynem wszystkich \( n_i \) poza \( n_j \). Oczywiście, \( {\sf NWD}\ (n_i,N_i)=1 \). Rozszerzony algorytm Euklidesa pozwala więc znaleźć liczby \( x_i \) takie, że \( N_ix_i\ \equiv_{n_i}1 \). Połóżmy
\( \displaystyle 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\neq i \). A więc, dla dowolnego \( i \) mamy:
\( x\equiv_{n_i}a_ix_iN_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,\ldots,l_k \) będą długościami odpowiednio \( n_1,\ldots,n_k \). Wtedy \( N \) ma długość co najwyżej \( l=l_1+\ldots+l_k \). Kroki algorytmu można wykonać kolejno w czasie:
Podsumowując wszystkie kroki zostaną wykonane w czasie \( O(k\lg^3{N}) \).
Przykład
Rozważmy układ równań:
\( \begin{align*} x & \equiv_3 & 2, \\ x & \equiv_{10} & 7, \\ x & \equiv_{11} & 10, \\ x & \equiv_7 & 1. \end{align*} \)
czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,
Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując \( x_1,\ldots,x_4 \):
Pozostaje policzyć \( x \):
\( \begin{align*} x & =2\cdot2\cdot770+7\cdot1\cdot231+10\cdot1\cdot210+1\cdot1\cdot330 \\ & =3080+1617+2100+330 \\ & =7127\equiv_{2310} 197. \end{align*} \)
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{align*} x & \equiv_2 & 0, \\ x & \equiv_{13} & 12, \\ x & \equiv_{15} & 2. \end{align*} \)
czyli możemy zaaplikować Chińskie Twierdzenie o Resztach,
Pozostaje nam obliczenie \( x \):
\( \begin{align*} x & =0\cdot1\cdot195+12\cdot10\cdot30+2\cdot26\cdot11=4172\equiv_{390}=272. \end{align*} \)
Zatem \( 272 \) jest najmniejszym dodatnim rozwiązaniem naszego układu równań.
Potęgowanie modularne. Naszym celem jest policzenie
\( a^b\ {\sf mod} \ n . \)
Oczywiście, możemy założyć, że \( 0\leq a < n \), bo inaczej najpierw można policzyć resztę \( a' \) z dzielenia \( a \) przez \( n \), a dopiero potem \( (a')^b \ {\sf mod} \ n \), jako że \( (a')^b \ {\sf mod}\ n =a^b \ {\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:
Policzmy zatem w następujacy sposób kolejne potęgi \( a \) występujące w iloczynie:
\( \begin{align*} a \cdot a \ {\sf mod} \ n & \equiv_n & a^2 \ {\sf mod} \ n , \\ (a^2 \ {\sf mod} \ n )\cdot(a^2 \ {\sf mod}\ n ) & \equiv_n & a^4 \ {\sf mod} \ n , \\ & \ldots & \\ (a^{2^{k-2}} \ {\sf mod} \ n )\cdot(a^{2^{k-2}} \ {\sf mod} \ n ) & \equiv_n & a^{2^{k-1}} \ {\sf mod} \ n . \end{align*} \)
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^2{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} \ {\sf mod} \ 10 =? \)
Przykład
\( 3^{51} \ {\sf mod} \ 13 =? \)
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{\{ {0,\ldots,p-1} \} } \), 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{\{ {1,\ldots,p-1} \} } \) wystarczy udowodnić, że:
\( a^{p-1}\ \equiv_{p}1 . \)
Pierwszy dowód. Dla \( a\in{\{ {1,\ldots,p-1} \} } \) rozważmy ciąg
\( a_0, a_1, a_2,\ldots, a_{p-1} \)
reszt \( a_k = ka \ {\sf mod} \ p \) liczb \( ka \) modulo \( p \). Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech \( 0\leq 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 \( {\{ {1,2,\ldots,p-1} \} } \), żaden z tych dwu przypadków nie jest możliwy. A zatem \( {\{ {a_0, a_1, a_2,\ldots, a_{p-1}} \} }= {\{ {0,1,2,\ldots,p-1} \} } \). 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\ldots\cdot(p-1)a \equiv_p a_1 \cdot a_ 2\cdot\ldots\cdot a_{p-1} = 1\cdot2\cdot\ldots\cdot(p-1), \)
lub inaczej:
\( (p-1)! \cdot a^{p-1} \equiv_p (p-1)!. \)
Ponieważ \( p \) jest liczbą pierwszą, wszystkie liczby ze zbioru \( {\{ {1,\ldots,p-1} \} } \) 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,\ldots,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:
\( \displaystyle (x+y)^p=\sum_{i=0}^p{p\choose i}x^iy^{p-i}. \)
Współczynnik \( {p\choose 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 \( {p\choose i} \) na czynniki pierwsze musi znaleźć się \( p \). To zaś implikuje \( {p\choose i}\ \equiv_{p}0 \) dla \( 0 < i < p \). A więc
\( \displaystyle (x+y)^p =\sum_{i=0}^p{p\choose i}x^iy^{p-i} \equiv_p \sum_{i\in{\{ {0,p} \} }}{p\choose i}x^iy^{p-i} =x^p+y^p. \)
Trzeci dowód. Niech \( a\in{\{ {1,\ldots,p-1} \} } \).
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\ldots w_k \) o \( i \) liter, jeśli
\( v=w_{i+1}w_{i+2}\ldots w_kw_1\ldots 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\ldots u \), dla żadnego słowa \( u \) i żadnej liczby \( l>0 \). Z kolei niech \( w= v^k=v\ldots v \), dla pewnego \( k>0 \). Wtedy słowo \( w \) ma dokładnie \(| \) 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 \( | \) 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\ldots v_m \) i \( v_1,\ldots,v_m \) są literami alfabetu, to każde przesunięcie cykliczne prowadzi do jednego ze słów z listy:
\( \begin{array} {rcll} v_1v_2v_3\ldots v_m & v^{k-1} & & , \\ v_2v_3\ldots v_m & v^{k-1} & v_1 & , \\ v_3\ldots v_m & v^{k-1} & v_1v_2 & , \\ & \vdots & & \\ v_m & v^{k-1} & v_1\ldots v_{m-1} & . \end{array} \)
Ponieważ \( |=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\ldots v_m v^{k-1}=v_i\ldots v_m v^{k-1}v_1v_2\ldots v_{i-1}, \)
dla pewnego \( 1 < i\leq m \). Wtedy
\( v_1\ldots v_m=v_i\ldots v_mv_1\ldots v_{i-1}. \)
To z kolei prowadzi do ciągu równości w poniższym diagramie:
\( \begin{array} {lcllcllcl} v_1 & \ldots & v_{m-(i-1)} & v_{m-(i-1)+1} & \ldots & v_{m-2(i-1)} & v_{m-2(i-1)+1} & \ldots & v_{m-3(i-1)}\ldots \\ & \parallel & & & \parallel & & & \parallel & \\ v_i & \ldots & v_m & v_1 & \ldots & v_{m-(i-1)} & v_{m-(i-1)+1} & \ldots & v_{m-2(i-1)}\ldots \end{array} \)
Czyli słowo \( v \) jest postaci \( v=x^l \) dla \( x=v_i\ldots 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\geq2 \), gdyż inaczej \( | |p \), a skoro \( p \) jest liczbą pierwszą, to \( |=1 \) lub \( |=p=| \). 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.
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'}, \)
gdzie \( b' \) jest resztą z dzielenia \( b \) przez \( p-1 \).
Przykład
Policzmy \( 7^{126} \ {\sf mod} \ 11 \).
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:
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) \):
Oraz \( \varphi(1980) \):
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 . \)
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 \).
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 \).