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

From Studia Informatyczne

Spis treści

Arytmetyka modularna

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:

  • 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{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{Z}/\equiv_n, tzn. w zbiorze klas równoważności. {\left\{ {[a]_n : a\in \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,\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 {\left\{ {0,1,2,\ldots,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{Z}/\equiv_n ze zbiorem \mathbb{Z}_n={\left\{ {0,\ldots n-1} \right\} } reszt modulo n. Po wprowadzeniu do tego zbioru działań arytmetycznych dostajemy pierścień, przemienny z jedynką \mathbb{Z}_n=({\left\{ {0,\ldots 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\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ż \mbox{\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.

image:End_of_proof.gif

Przykład

  • 15=3\cdot5\equiv_7 10\cdot5=50 oraz 5\perp7 implikuje 3\equiv_7 10,
  • 8=2^3\equiv_3 2 oraz 2\perp3 implikuje 4=2^2\equiv_3 1.

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=({\left\{ {0,\ldots 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\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 \mbox{\sf NWD}(a,n)=1 w następujący sposób:

  • jeśli \mbox{\sf NWD}(a,n)=1,

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

  • jeśli \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\leq a,b<n, to rozwiązanie 0\leq x_0 <n

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 \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 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 \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 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 \mbox{\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:

  • policzyć d:=\mbox{\sf NWD}(a,n) oraz współczynniki y,z takie, że ya+zn=d,
  • jeśli d=1, to x_0 =yb \mbox{ {\sf mod} } n jest poszukiwanym rozwiązaniem,
  • jeśli d>1 i d\not| 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.

image:End_of_proof.gif

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.

  • \mbox{\sf NWD}(3,7)=1, czyli równanie ma nieskończenie wiele rozwiązań,
  • 1=1\cdot7-2\cdot3,

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

A następnie równanie 3x\equiv_{12}4.

  • \mbox{\sf NWD}(3,12)=3, ale 3\not| 4, czyli równanie nie ma rozwiązania.

Wreszcie rozważmy równanie 9x\equiv_{21}12.

  • \mbox{\sf NWD}(9,21)=3 oraz 3|12, czyli równanie ma nieskończenie wiele rozwiązań,
  • 3=1\cdot21-2\cdot9,

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

image:End_of_proof.gif

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}-{\left\{ {0} \right\} } 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:


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


\aligned a&\equiv_{n_1}&b,\\ a&\equiv_{n_2}&b,\\ &\vdots&\\ a&\equiv_{n_k}&b. \endaligned


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 {\left\{ {0,1,\ldots,N-1} \right\} } 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.

image:End_of_proof.gif

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, \mbox{\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:

  • O(kl) na wyliczenie wszystkich iloczynów postaci N_i oraz całego iloczynu N,
  • O(kl^3) na wyliczenie kolejnych współczynników x_i, czyli k-krotną aplikację rozszerzonego algorytmu Euklidesa dla liczb n_i, N_i\leq N,
  • O(kl^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ń:


\aligned x&\equiv_3& 2,\\ x&\equiv_{10}& 7,\\ x&\equiv_{11}& 10,\\ x&\equiv_7& 1. \endaligned


  • \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\cdot7\cdot10\cdot11=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,\ldots,x_4:

  • \mbox{\sf NWD}(3,770)=1=257\cdot3-1\cdot770, x_1=-1\equiv_3 2,
  • \mbox{\sf NWD}(10,231)=1=-23\cdot10+1\cdot231, x_2=1,
  • \mbox{\sf NWD}(11,210)=1=-19\cdot11+1\cdot210, x_3=1,
  • \mbox{\sf NWD}(7,330)=1=-47\cdot7+1\cdot330, x_4=1.

Pozostaje policzyć x:


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


\aligned x&\equiv_2&0,\\ x&\equiv_{13}&12,\\ x&\equiv_{15}&2. \endaligned
  • \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\cdot13\cdot15=390,
  • N_1=\frac{390}{2}=195,
  • N_2=\frac{390}{13}=30,
  • N_3=\frac{390}{15}=26,
  • \mbox{\sf NWD}(2,195)=1=-97\cdot2+1\cdot195, x_1=1,
  • \mbox{\sf NWD}(13,30)=1=7\cdot13-3\cdot30, x_2=-3\equiv_{13} 10,
  • \mbox{\sf NWD}(15,26)=1=7\cdot15-4\cdot26, x_3=-4\equiv_{15}11.

Pozostaje nam obliczenie x:


\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


a^b \mbox{ {\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 \mbox{ {\sf mod} } n, jako że (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,\ldots,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}\ldots b_0)_2 będzie binarnym zapisem liczby b. Zauważmy, że 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:


\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^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} \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\cdot9=81\equiv_{10}1,
    • 7^8\equiv_{10}1\cdot1=1,
  • 7^{12}=7^8\cdot7^4\equiv_{10}1\cdot1=1.
  • wykonane zostały tylko 4 mnożenia!

Przykład


3^{51} \mbox{ {\sf mod} } 13 =?
  • 51=(110011)_2,
  • wyznaczamy wybrane potęgi 3 modulo 13:
    • 3^2=9,
    • 3^4=9\cdot9=81\equiv_{13}3,
    • 3^8\equiv_{13}3\cdot3=9,
    • 3^{16}\equiv_{13}9\cdot9=81\equiv_{13}3,
    • 3^{32}\equiv_{13}3\cdot3=9.
  • 3^{51}=3^{32}\cdot3^{16}\cdot3^2\cdot3^1\equiv_{13}9\cdot3\cdot9\cdot3=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,\ldots,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,\ldots,p-1} \right\} } wystarczy udowodnić, że:


a^{p-1}\ \equiv_{p}1 .


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


a_0, a_1, a_2,\ldots, a_{p-1}


reszt 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\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 {\left\{ {1,2,\ldots,p-1} \right\} }, żaden z tych dwu przypadków nie jest możliwy. A zatem {\left\{ {a_0, a_1, a_2,\ldots, a_{p-1}} \right\} }= {\left\{ {0,1,2,\ldots,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\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 {\left\{ {1,\ldots,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,\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{\left\{ {0,p} \right\} }}{p\choose i}x^iy^{p-i} =x^p+y^p.


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

Rozważmy słowa długości p nad alfabetem a-elementowym. image:End_of_proof.gif

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 \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 \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\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ż \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\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.

image:End_of_proof.gif

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 \left\vertv\right\vert|p, a skoro p jest liczbą pierwszą, to \left\vertv\right\vert=1 lub \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'},

gdzie b' jest resztą z dzielenia b przez p-1.

Przykład

Policzmy 7^{126} \mbox{ {\sf mod} } 11.

  • 11 jest liczba pierwszą, czyli możemy skorzystać z Małego Twierdzenia Fermata,
  • 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\cdot5=25\equiv_{11}4.
  • 7^{127}\equiv_{11}7^6=7^4\cdot7^2\equiv_{11}4\cdot5=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 \varphi-Eulera to \varphi:\mathbb{N}-{\left\{ {0} \right\} }\longrightarrow\mathbb{N} zdefiniowaną poprzez


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


Obserwacja 11.11

Dla dowolnej liczby pierwszej p zachodzi:

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

Dowód

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

image:End_of_proof.gif

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:


\mbox{\sf NWD}(a,mn)=1 wtedy i tylko wtedy, gdy \mbox{\sf NWD}(a,m)=1=\mbox{\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.

image:End_of_proof.gif

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:


\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 \varphi(2006):

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

Oraz \varphi(1980):

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

Twierdzenie 11.14 [Euler 1736]

Dla dowolnych a,n, gdzie \mbox{\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 \mbox{ {\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 .


image:End_of_proof.gif

Zastosowanie Twierdzenia Eulera do szybkiego potęgowania.

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

Przykład

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

  • 13\perp16, czyli możemy skorzystać z Twierdzenia Eulera,
  • \varphi(16)=8,
  • 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\cdot13= 169 \equiv_{16} 9,
    • 13^4\equiv_{16}9\cdot9=81\equiv_{16}1.
  • 13^{101}\equiv_{16}13^5=13^4\cdot13^1\equiv_{16}1\cdot13=13.

Funkcja Mobiusa

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

Dowód

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


\varphi(n)=n-\left\vertA_1\cup\ldots\cup A_k\right\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}\left\vertA_{j_1}\cap\ldots\cap A_{j_i}\right\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 \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


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


\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


image:End_of_proof.gif

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

Dla dowolnego n\geqslant2 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\leqslant\beta_i\leqslant\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,\ldots,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:


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


image:End_of_proof.gif

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


to


\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


\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 11.15 wiemy, że wewnętrze sumy zerują się dla wszystkich \frac{n}{c}\geqslant2. Zatem jedyny interesujący składnik zewnętrznej sumy dostajemy przy c=n:


\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


image:End_of_proof.gif

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

Wniosek 11.17

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