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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Arytmetyka modularna

Liczby przystające modulo to takie dwie liczby , dla których różnica jest wielokrotnością . Fakt ten zapisujemy jako . Innymi słowy, jeśli i mają te same reszty w dzieleniu przez .

Obserwacja 11.

Dla dowolnych oraz zachodzi:

  • ,
  • wtedy i tylko wtedy, gdy ,
  • jeśli i to .

Powyższe własności świadczą o tym, że przystawanie modulo jest relacją równoważności na zbiorze . Dlatego czasem relacja ta nazywana jest równością modulo . Okazuje się też, że relacja 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 oraz mamy:

  • jeśli i , to ,
  • jeśli i , to ,
  • jeśli i , to .

Podane w dwu poprzednich obserwacjach własności relacji równości modulo pozwalają na wprowadzenie działań w zbiorze ilorazowym , tzn. w zbiorze klas równoważności. , poprzez:

  • ,
  • ,
  • ,

Ponieważ w każdej klasie jest jakaś liczba spośród , a mianowicie reszta z dzielenia liczby przez , to wygodniej jest po prostu mówić o arytmetyce (modularnej) na zbiorze tych reszt i pisać np.:

  • ,
  • ,
  • .

Tak więc, dla możemy zidentyfikować zbiór ilorazowy ze zbiorem reszt modulo . Po wprowadzeniu do tego zbioru działań arytmetycznych dostajemy pierścień, przemienny z jedynką . 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: , ale . Okazuje się, że w równości modulo możemy skracać czynniki względnie pierwsze z .

Obserwacja 11.3 [Reguła skracania]

Dla , jeśli i , to .

Dowód

Ponieważ , rozszerzony algorytm Euklidesa gwarantuje istnienie takich, że , czyli . Mnożąc teraz obie strony przez , otrzymujemy , czyli .

End of proof.gif

Przykład

  • oraz implikuje ,
  • oraz implikuje .

Chcąc móc skracać w pierscieniu dowolne niezerowe czynniki wymagamy, by wszystkie liczby były względnie pierwsze z . To nic innego, jak wymaganie, by było liczbą pierwszą.

Obserwacja 11.4

Pierścień jest ciałem, wtedy i tylko wtedy, gdy jest liczba pierwszą.

Rozwiązywanie równań modularnych

Oczywiście w ciele, każde równanie postaci ma dokładnie jedno rozwiązanie , o ile . Zobaczmy czy są, jak wyglądają i jak otrzymać rozwiązania równania modularnego postaci w liczbach całkowitych , gdzie oraz .

Obserwacja 11.5

Dla rozwiązania równania modularnego z jedną niewiadomą :



zależą od wielkości w następujący sposób:

  • jeśli ,

to istnieje nieskończenie wiele rozwiązań; wszystkie one są postaci , gdzie jest jakimś rozwiązaniem, a ,

  • jeśli ,

to równanie ma rozwiązanie wtedy i tylko wtedy, gdy również . W tym przypadku rozwiązania równania pokrywają się z rozwiązaniami równania .

Ponadto,

  • ponadto, jeśli , to rozwiązanie

równania , lub jego brak, można wskazać wykonując operacji bitowych.

Dowód

Zauważmy najpierw, że jeśli są resztami z dzielenia odpowiednio i przez , to rozwiązania równań i są takie same. Istotnie, wynika to natychmiast z tego, że oraz . Możemy więc przyjąć, że . Ponadto odnotujmy, że z tych samych powodów, jeśli spełnia równanie, to spełnia je również każda liczba postaci , gdzie .

Załóżmy najpierw, że . Rozszerzony algorytm Euklidesa gwarantuje istnienie takich, że . Łatwo teraz sprawdzić, że reszta z dzielenia przez jest rozwiązaniem. A więc i wszystkie liczby postaci , są również rozwiązaniami. Pozostaje pokazać, że wszystkie rozwiązania są takiej właśnie postaci. Niech więc . Ponieważ , to możemy skrócić otrzymując , co implikuje że , dla pewnej liczby całkowitej .

Niech teraz . Najpierw pokażemy, że jeśli równanie ma rozwiązanie, to . Rzeczywiście, jeśli dla pewnego , to , a więc i . Ale , więc . Na odwrót, gdy , to liczby są podzielne przez . Niech więc , i . Wtedy i, na mocy pierwszego punktu, równanie ma nieskończenie wiele rozwiązań. Pozostaje pokazać, że są to te same rozwiązania, co dla równania . Niech więc . Wtedy . Gdy zaś , to dla pewnego . A zatem i, po wydzieleniu przez , dostajemy , czyli .

Na podstawie dowodu poprzednich dwu punktów wiemy więc, że by rozwiązać równanie wystarczy:

  • policzyć oraz współczynniki takie, że ,
  • jeśli , to jest poszukiwanym rozwiązaniem,
  • jeśli i , to równanie nie posiada rozwiązań,
  • jeśli i , to jest szukanym rozwiązaniem.

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

End of proof.gif

Wniosek 11.6

Jeśli jest liczbą pierwszą, to równania postaci dla dowolnych i zawsze mają rozwiązanie i można je znaleźć wykonując operacji bitowych.

Przykład

Rozwiążemy równanie .

  • , czyli równanie ma nieskończenie wiele rozwiązań,
  • ,

czyli zbiór rozwiązań to .

A następnie równanie .

  • , ale , czyli równanie nie ma rozwiązania.

Wreszcie rozważmy równanie .

  • oraz , czyli równanie ma nieskończenie wiele rozwiązań,
  • ,

czyli zbiór rozwiązań to .

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

Obserwacja 11.7

Niech , gdzie i . Wtedy jest równoważne temu, że równocześnie i .

Dowód

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

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 będą parami względnie pierwsze, tzn. dla . Wtedy dla dowolnych istnieje dokładnie jedna liczba taka, że:



Dowód

Niech . Dla liczby rozważmy ciąg reszt z dzielenia odpowiednio przez .

Niech teraz . Gdyby , to



Z drugiej strony , więc stosując wielokrotnie Obserwację 11.7 otrzymujemy , czyli , co jest niemożliwe wobec . Sprzeczność ta pokazuje, że liczby ze zbioru mają różne ciągi reszt. Oznacza to, że ciągów postaci jest dokładnie , czyli tyle ile wszystkich możliwych ciągów w . Tym samym przyporządkowanie jest bijekcją, co kończy dowód twierdzenia.

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 , czyli jest iloczynem wszystkich poza . Oczywiście, . Rozszerzony algorytm Euklidesa pozwala więc znaleźć liczby takie, że . Połóżmy



Wtedy dzieli wszystkie czynniki sumy poza -tym, ponieważ dla . A więc, dla dowolnego mamy:



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

Oszacujmy czas działania tego algorytmu. Niech będą długościami odpowiednio . Wtedy ma długość co najwyżej . Kroki algorytmu można wykonać kolejno w czasie:

  • na wyliczenie wszystkich iloczynów postaci oraz całego iloczynu ,
  • na wyliczenie kolejnych współczynników , czyli -krotną aplikację rozszerzonego algorytmu Euklidesa dla liczb ,
  • na obliczenie , czyli mnożeń i dodawań.

Podsumowując wszystkie kroki zostaną wykonane w czasie .

Przykład

Rozważmy układ równań:



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

  • ,
  • ,
  • ,
  • ,
  • .

Zgodnie z procedurą czterokrotnie używamy rozszerzonego algorytmu Euklidesa otrzymując :

  • , ,
  • , ,
  • , ,
  • , .

Pozostaje policzyć :



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

Przykład

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


  • ,

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

  • ,
  • ,
  • ,
  • ,
  • , ,
  • , ,
  • , .

Pozostaje nam obliczenie :



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

Potęgowanie modularne

Potęgowanie modularne. Naszym celem jest policzenie



Oczywiście, możemy założyć, że , bo inaczej najpierw można policzyć resztę z dzielenia przez , a dopiero potem , jako że . Zauważmy, że w przeciwieństwie do zwykłego potęgowania wynik nigdy nie przekracza , czyli nie rośnie wykładniczo w stosunku do . 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óż przez siebie -krotnie, po każdym mnożeniu weź resztę modulo . Branie reszty po każdym mnożeniu, utrzymuje tymczasowy iloczyn w zbiorze . Zatem wykonywanych jest mnożeń liczb -bitowych, czyli wykonywanych jest operacji bitowych. Jest to zatem algorytm działający w czasie wykładniczym względem rozmiaru wejścia .
  • Szybkie potęgowanie modulo. Niech będzie binarnym zapisem liczby . Zauważmy, że .

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



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

W sumie wykonanych zostanie operacji bitowych, a więc znacznie mniej niż sposobem naiwnym. Przedstawiony algorytm jest efektywny (wielomianowy względem długości wejścia).

Przykład


  • ,
  • wyznaczamy wybrane potęgi modulo :
    • ,
    • ,
    • ,
  • .
  • wykonane zostały tylko mnożenia!

Przykład


  • ,
  • wyznaczamy wybrane potęgi modulo :
    • ,
    • ,
    • ,
    • ,
    • .
  • .

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 liczby pierwszej i dowolnego zachodzi:



Dowód

Poznamy trzy różne dowody. Najpierw jednak zauważmy, że bez straty ogólności możemy przyjąć iż , gdyż w miejsce możemy rozważać resztę z dzielenia przez . Ponadto, zwróćmy uwagę, iż dla teza jest oczywista, natomiast dla wystarczy udowodnić, że:



Pierwszy dowód. Dla rozważmy ciąg



reszt liczb modulo . Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech i, dla dowodu niewprost, niech



Wtedy . Ponieważ jest liczba pierwszą to lub . Ponieważ jednak obie liczby oraz leżą w zbiorze , żaden z tych dwu przypadków nie jest możliwy. A zatem . Oczywiście , więc iloczyny pozostałych elementów w tych dwu zbiorach muszą być równe, co daje:



lub inaczej:



Ponieważ jest liczbą pierwszą, wszystkie liczby ze zbioru są względnie pierwsze z , więc i . Można więc zastosować regułę skracania:



Drugi dowód. Dla dowodu indukcyjnego względem zauważmy najpierw, że w oczywisty sposób oraz i załóżmy, że . Aby udowodnić, że:



pokażemy znacznie mocniejszą równość



która przy i pozwoli zakończyć dowód indukcyjny.

Rozwijając dwumian mamy:



Współczynnik jest zawsze liczbą całkowitą. Ponadto, jeśli , to wszystkie czynniki obu silni mianownika są względnie pierwsze z , bo jest pierwsza, a czynniki te są mniejsze niż . Oznacza to, iż w rozkładzie na czynniki pierwsze musi znaleźć się . To zaś implikuje dla . A więc



Trzeci dowód. Niech .

Rozważmy słowa długości nad alfabetem -elementowym. End of proof.gif

Przykład

Niech , . Symbolami alfabetu niech będą A,B,C.

Oto mocno skrócona lista wszystkich słów -literowych nad tym alfabetem.


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


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

Słowo nazwiemy przesunięciem cyklicznym słowa o liter, jeśli



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 będzie słowem, którego nie da się przedstawić jako , dla żadnego słowa i żadnej liczby . Z kolei niech , dla pewnego . Wtedy słowo 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 , to te dwa przesunięcia dają to samo słowo. A zatem ma co najwyżej różnych przesunięć cyklicznych. Z drugiej strony, gdyby dwa przesunięcia cykliczne słowa były równe, to dawałyby to samo słowo. Istotnie, gdy i są literami alfabetu, to każde przesunięcie cykliczne prowadzi do jednego ze słów z listy:



Ponieważ , 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:



dla pewnego . Wtedy



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



Czyli słowo jest postaci dla i , wbrew założeniom lematu.

End of proof.gif

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

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:

gdzie jest resztą z dzielenia przez .

Przykład

Policzmy .

  • jest liczba pierwszą, czyli możemy skorzystać z Małego Twierdzenia Fermata,
  • ,
  • ,
  • ,
  • liczymy wybrane potęgi modulo :
    • ,
    • .
  • .
  • wykonaliśmy 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ą .

Funkcja -Eulera to zdefiniowaną poprzez



Obserwacja 11.11

Dla dowolnej liczby pierwszej zachodzi:

  • ,
  • .

Dowód

Ponieważ jest pierwsza, liczby są z nią względnie pierwsze, co dowodzi pierwszego punktu. Dla dowodu punktu drugiego zauważmy najpierw, że jedynie wielokrotności liczby mają nietrywialny wspólny dzielnik z . Wielokrotności tych w przedziale [] jest dokładnie , stąd .

End of proof.gif

Obserwacja 11.12

Dla dowolnych takich, że zachodzi



Dowód

Z Chińskiego Twierdzenia o Resztach wiemy, iż każda liczba z przedziału jest jednoznacznie wyznaczona przez jej reszty modulo i modulo . Wiemy także, że dla dowolnego :


wtedy i tylko wtedy, gdy .


To oznacza, iż liczb takich, że jest dokładnie tyle co par takich, że , oraz , .

End of proof.gif

Wniosek 11.13

Jeśli jest rozkładem na liczby pierwsze , w którym , to:



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

Przykład

Policzmy :

  • ,
  • .

Oraz :

  • ,
  • .

Twierdzenie 11.14 [Euler 1736]

Dla dowolnych , gdzie zachodzi:



Dowód

Zmodyfikujmy pierwszy z poznanych dowodów Małego Twierdzenia Fermata. Niech będą wszystkimi liczbami względnie pierwszymi z i niewiększymi od . Rozważmy ciąg



reszt liczb modulo . Pokażemy, że żadna wartość w tym ciągu się nie powtarza. Niech i, dla dowodu niewprost, niech



Wtedy , a ponieważ , to , co jest niemożliwe wobec .

Ponadto pokażmy, że każde jest względnie pierwsze z . Załóżmy zatem, że oraz . Ponieważ dla pewnego , to . Z drugiej strony , i , co daje i . A więc , czyli w istocie .

Wiemy więc, że liczby przyjmują wszystkie wartości i każdą tylko raz. A zatem



Ponieważ liczby są względnie pierwsze z możemy zastosować regułę skracania, by dostać



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

Przykład

Spróbujmy policzyć .

  • , czyli możemy skorzystać z Twierdzenia Eulera,
  • ,
  • ,
  • ,
  • ,
  • liczymy wybrane potęgi modulo :
    • ,
    • ,
    • .
  • .

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 będzie rozkładem na liczby pierwsze , w którym . Zdefiniujmy jako zbiór wielokrotności liczby w . Wtedy . Korzystając z Zasady Włączania i Wyłączania otrzymujemy



gdzie . Zauważmy, że zbiór składa się z wielokrotności liczby , czyli liczb . Zatem , skąd



Teraz łatwo już policzyć



End of proof.gif

Przyjrzyjmy się temu dowodowi trochę dokładniej. Analizując ostatnią sumę dla mamy



Po prawej stronie mamy naprzemienną sumę składników , gdzie przebiega kolejne dzielniki liczby , będące iloczynem różnych liczb pierwszych. Czynnik jest dodawany, jeśli jest iloczynem parzystej liczby liczb pierwszych i odejmowany, jeśli jest iloczynem nieparzystej liczby liczb pierwszych. Zależność tę możemy ogólniej zapisać w postaci



gdzie zadana jest przez:



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

Dowód

Niech . Wtedy każdy dzielnik liczby ma rozkład , gdzie . Jeśli choć jedno , to . Rozważmy więc tylko te dzielniki dla których . Każdy taki dzielnik wyznacza jednoznacznie pewien podzbiór zbioru , przy czym wartościom , dla których odpowiadają podzbiory o parzystej liczbie elementów, a wartościom , dla których odpowiadają podzbiory o nieparzystej liczbie elementów. A zatem:



End of proof.gif

Obserwacja 11.16 [wzór inwersyjny Mobiusa]

Dla dowolnych funkcji , jeśli , to .

Dowód

Ponieważ



to



Zauważmy, iż . Zatem



Z Obserwacji 11.15 wiemy, że wewnętrze sumy zerują się dla wszystkich . Zatem jedyny interesujący składnik zewnętrznej sumy dostajemy przy :



End of proof.gif

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

Wniosek 11.17

.