Zbieżność ciągu liczb całkowitych jest związkiem, który może połączyć dwie liczby całkowite . Po raz pierwszy została zbadana jako struktury przez matematyka niemieckiego Carla Friedricha Gaussa w końcu XVIII -go wieku i zaprezentowane publicznie w jego Disquisitiones Arithmeticae w 1801 roku . Obecnie jest szeroko stosowany w teorii liczb , algebrze ogólnej i kryptografii . Stanowi podstawę gałęzi matematyki zwanej arytmetyką modularną .
Jest to arytmetyka, w której nie wnioskuje się bezpośrednio na liczbach, ale na ich odpowiednich resztach przez dzielenie euklidesowe przez pewną liczbę całkowitą: moduł (co będzie zaznaczone n w całym artykule). Mówimy wtedy o kongruencji .
Historia, narzędzia opracowane dla arytmetyki modularnej, a także aplikacje są omówione w artykule „ Arytmetyka modularna ”. Bardziej wyczerpującą i mniej dydaktyczną analizę proponuje artykuł „ Anneau ℤ / n ℤ ”.
Arytmetyka modularna to system arytmetyczny zmodyfikowanych liczb całkowitych, w którym liczby są „obniżane”, gdy osiągną określoną wartość.
Jako przykład podajmy „arytmetykę zegara”, która odnosi się do „dodawania” godzin wskazanych przez małą wskazówkę zegara: konkretnie, jeśli zaczniemy o godzinie 9 i dodamy 4 godziny, to raczej niż kończyć o 13:00 (jak na normalnym rachunku), jesteśmy na 1 godzinę. Podobnie, jeśli zaczynamy o północy i trzy razy z rzędu czekamy o 7 rano, spotykamy się o 9 rano (zamiast o 21).
Zasadniczo, kiedy trafimy 12, zaczynamy od zera; pracujemy modulo 12. Wracając do poprzedniego przykładu, mówimy, że 9 i 21 to przystające modulo 12. Liczby 9, 21, 33, 45 itd. są uważane za równe podczas pracy modulo 12.
Aby uogólnić, możemy wyobrazić sobie zegar, który zawiera dowolną liczbę godzin i wykonać obliczenia za pomocą nowego modułu.
Definicja - Niech n będzie liczbą naturalną .
O dwóch względnych liczbach całkowitych a i b mówi się, że są przystające modulo n, jeśli ich różnica jest podzielna przez n , tj. Jeśli a ma postać b + kn z k liczbą całkowitą.
Wykluczamy teraz trywialny przypadek n = 0 (kongruencja modulo 0 to równość ; możemy przypadkowo zauważyć, że modulo 1, dowolne dwie liczby całkowite są równoważne).
Definicja równoważna, jeśli n > 0 - Niech n będzie niezerową liczbą całkowitą.
Dwie liczby A i B są uważane za przystające modulo n , gdy pozostała część euklidesowej Division of przez n jest równa podziału b o n .
Znakiem używanym do wyrażenia zgodności dwóch liczb całkowitych jest ≡ .
Możemy wyrazić, że a i b są przystającymi modulo n w czterech formach:
Ostatnim jest zalecany przez normę ISO / IEC 80000-2 z 2009 roku.
Niezależnie od wybranej notacji, brzmi to „ a jest przystające do b modulo n ”.
Na przykład : 26 ≡ 12 (7) ponieważ 26-12 = 14, wielokrotność 7 (definicja powyżej ), lub znowu: ponieważ 26 i 12 mają 5 jako resztę w dzieleniu przez 7 (równoważna definicja powyżej ).
UwagiZgodność modulo n ma następujące właściwości:
Jest to zatem relacja równoważności .
Właściwości algebraiczneMa również niezwykłe właściwości algebraiczne:
tak a 1 ≡ b 1 ( n ) oraz a 2 ≡ b 2 ( n ), więc
(Możemy łatwo wywnioskować inne, na przykład: jeśli a ≡ b ( n ) to ac ≡ bc ( n ) dla wszystkich liczb całkowitych c i a q ≡ b q ( n ) dla wszystkich liczb całkowitych q ≥ 0)
Można mówić o pewnej „zgodności” z operacjami dodawania i mnożenia liczb całkowitych, czyli o „zgodności” z pierścieniową strukturą (ℤ, +, ×). Tych kilka właściwości pozwoli nam zdefiniować dziedzinę arytmetyki modularnej: zbiory ilorazów ℤ / n ℤ.
Poprzednie właściwości pokazują, że dwie liczby przystające do siebie modulo n są wymienne podczas dodawania lub mnożenia, podczas modulo n . Następnie pojawia się pomysł, aby zgrupować wszystkie liczby przystające do siebie modulo n w tej samej klasie, którą nazywamy klasą równoważności, i pracować tylko z określonym przedstawicielem tej klasy. Ponieważ wszystkie liczby tej samej klasy mają taką samą resztę w dzieleniu przez n , faworyzujemy reszty z dzielenia przez n i pracujemy na zbiorze oznaczonym ℤ n lub ℤ / n ℤ składającym się z n elementów lub prościej {0 , 1, 2, ..., n - 1} zbiór modulo n reszt , które nazywamy resztkowym pierścieniem modulo n lub nawet ilorazem pierścienia
Na tym zbiorze można zdefiniować dodawanie i mnożenie analogiczne do zdefiniowanego na zbiorze ℤ względnych liczb całkowitych :
Następnie możemy zbudować następujące tabele operacji:
+ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 2 | 3 | 4 | 5 | 0 |
2 | 2 | 3 | 4 | 5 | 0 | 1 |
3 | 3 | 4 | 5 | 0 | 1 | 2 |
4 | 4 | 5 | 0 | 1 | 2 | 3 |
5 | 5 | 0 | 1 | 2 | 3 | 4 |
× | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 0 | 2 | 4 | 0 | 2 | 4 |
3 | 0 | 3 | 0 | 3 | 0 | 3 |
4 | 0 | 4 | 2 | 0 | 4 | 2 |
5 | 0 | 5 | 4 | 3 | 2 | 1 |
Te operacje mają prawie takie same właściwości jak dodawanie i mnożenie w ℤ.
Zestaw z dwiema operacjami posiadającymi te właściwości nazywany jest pierścieniem .
Jedyną operacją, którą zwykle wykonujemy w ℤ i która nie zawsze jest właściwa w ringu ℤ / n ℤ, jest uproszczenie.
Rzeczywiście, jeśli 2 a = 4 w ℤ, wiemy, że a = 2. Ale modulo 6, jeśli 2 a = 4, wiemy tylko, że 2 a ma resztę 4 w dzieleniu przez 6, tak że a ma dla reszty 2 w dzielenie przez 3. a może zatem mieć jako resztę z dzielenia przez 6 2 lub 5. Mówiąc prościej: mamy 2 × 2 ≡ 2 × 5 bez 2 ≡ 5.
Podobnie, właściwość stale używana w zbiorach liczb klasycznych "aby iloczyn dwóch wyrazów wynosił zero, konieczne i wystarczające jest, aby jeden z wyrazów" nie zawsze był realizowany w ℤ / n ℤ modulo 6, mamy 2 × 3 ≡ 0, przy czym 2 ani 3 nie są przystające do 0.
Mówimy, że pierścień ℤ / 6ℤ nie jest całkowy .
Rozwiązywanie równań może zatem stać się nieco problematyczne, gdy w grę wchodzą mnożenia:
Możemy zobaczyć, że równanie AX = B o nieznanej X w ℤ / n ℤ ma unikalne rozwiązanie, wtedy i tylko wtedy, gdy i n są względnie pierwsze.
Poszukiwanie rozwiązań równania, które według wartości n i a może mieć żadne, jedno, dwa rozwiązania, a nawet więcej, prowadzi do badania reszt kwadratowych i do sformułowania prawa kwadratowa wzajemność .
Konstrukcja ℤ / n ℤ jako pierścienia ilorazowego przez ideał i algebraiczne własności pierścienia ℤ / n ℤ są omówione w artykule „ Pierścień ℤ / n ℤ ”.
Z mnożenia w ℤ / n ℤ naturalne jest zainteresowanie kolejnymi potęgami. Istnieje tylko n - 1, więc ewentualne resztki n - 1 możliwych wartości a k , dlatego muszą uzyskać taką samą wartość kilkakrotnie. Tak więc istnieje k oraz m , tak że K i m mają takie samo modulo n resztę . Ponieważ konstrukcja jest k opiera się na nawrót, jak tylko możemy natknąć się na resztę już spotkaliśmy, wiemy, że sekwencja uprawnień staje się cykliczna z tej mocy i możemy przerwać poszukiwania.
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 |
k = 2 | ... | 4 | 2 | 2 | 4 | 1 |
k = 3 | ... | 1 | 6 | 1 | 6 | ... |
k = 4 | ... | ... | 4 | ... | 2 | ... |
k = 5 | ... | ... | 5 | ... | 3 | ... |
k = 6 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
k = 2 | ... | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 |
k = 3 | ... | 8 | 12 | ... | 5 | ... | 13 | 2 | 9 | ... | ... | 3 | 7 | ... |
k = 4 | ... | 1 | 6 | ... | ... | ... | 1 | 1 | ... | ... | ... | 6 | 1 | ... |
k = 5 | ... | ... | 3 | ... | ... | ... | ... | ... | ... | ... | ... | 12 | ... | ... |
... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
k = 8 | 1 | 1 | ... | 1 | ... | ... | 1 | 1 | ... | ... | 1 | ... | 1 | 1 |
Obserwacja na potęg ℤ / 7ℤ i ℤ / 15ℤ pokazuje, że w pierwszym przypadku, dla każdego z sile z 7 (czyli nie jest wielokrotnością 7), mamy do 6 przystający do 1 modulo 7, a w drugim przypadku, jedyne sekwencje przechodzące przez 1 odpowiadają liczbom całkowitym pierwszym z 15; są liczbami całkowitymi z 8 prime 15 i zauważamy, że w sile wieku z 15, 8 przystaje do 1 modulo 15.
Te dwie obserwacje odpowiadają dwóm twierdzeniom: