Porównanie modulo liczby naturalnej. Rozwiązywanie porównań i ich zastosowania Rozwiązywanie porównań

Porównanie z jedną niewiadomą X wygląda jak

Gdzie . Jeśli A N nie podzielne przez M, tak to się nazywa stopień porównania.

Decyzją porównanie jest dowolną liczbą całkowitą X 0 , dla którego

Jeśli X 0 spełnia porównanie, to zgodnie z właściwością 9 porównań wszystkie liczby całkowite są porównywalne X 0 modulo M. Dlatego wszystkie rozwiązania porównawcze należą do tej samej klasy reszt modulo T, rozważymy to jako jedno rozwiązanie. Porównanie ma zatem tyle rozwiązań, ile elementów pełnego układu reszt je spełnia.

Porównania, których zbiory rozwiązań są zbieżne, nazywane są równowartość.

2.2.1 Porównania pierwszego stopnia

Porównanie pierwszego stopnia z jedną niewiadomą X wygląda jak

(2.2)

Twierdzenie 2.4. Aby porównanie miało co najmniej jedno rozwiązanie, konieczne i wystarczające jest podanie liczby B podzielone przez GCD( A, M).

Dowód. Najpierw udowodnimy konieczność. Pozwalać D = NWD( A, M) I X 0 - rozwiązanie porównawcze. Następnie , czyli różnica Oh 0 − B podzielony przez T. Istnieje więc taka liczba całkowita Q, Co Oh 0 − B = mkw. Stąd B= aha 0 − mkw. I od D, jako wspólny dzielnik dzieli liczby A I T, następnie odjemna i odejmowana są dzielone przez D, i dlatego B podzielony przez D.

Teraz udowodnijmy wystarczalność. Pozwalać D- największy wspólny dzielnik liczb A I T, I B podzielony przez D. Następnie, z definicji podzielności, istnieją następujące liczby całkowite A 1 , B 1 ,T 1 , Co .

Używając rozszerzonego algorytmu Euklidesa, znajdujemy liniową reprezentację liczby 1 = gcd( A 1 , M 1 ):

dla niektórych X 0 , y 0 . Pomnóżmy obie strony ostatniej równości przez B 1 D:

lub, co jest takie samo,

,

to znaczy i jest rozwiązaniem porównania. □

Przykład 2.10. Porównanie 9 X= 6 (mod 12) ma rozwiązanie, ponieważ gcd(9, 12) = 3 i 6 jest podzielne przez 3. □

Przykład 2.11. Porównanie 6x= 9 (mod 12) nie ma rozwiązań, ponieważ gcd(6, 12) = 6 i 9 nie jest podzielne przez 6. □

Twierdzenie 2.5. Niech porównanie (2.2) będzie rozwiązywalne i D = NWD( A, M). Następnie składa się zestaw rozwiązań porównawczych (2.2). D klasy reszt modulo T, mianowicie, jeśli X 0 - jedno z rozwiązań, wówczas wszystkie inne rozwiązania są

Dowód. Pozwalać X 0 - rozwiązanie porównania (2.2), tj I , . Zatem istnieje coś takiego Q, Co Oh 0 − B = mkw. Teraz podstawiając do ostatniej równości zamiast X 0 dowolne rozwiązanie postaci, gdzie otrzymujemy wyrażenie

, podzielne przez M. □

Przykład 2.12. Porównanie 9 X=6 (mod 12) ma dokładnie trzy rozwiązania, ponieważ gcd(9, 12)=3. Te rozwiązania: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Przykład 2.13. Porównanie 11 X=2 (mod 15) ma unikalne rozwiązanie X 0 = 7, ponieważ NWD(11,15)=1.□

Pokażemy Ci jak rozwiązywać porównania pierwszego stopnia. Bez utraty ogólności założymy, że NWD( A, t) = 1. Następnie rozwiązania porównania (2.2) można szukać np. korzystając z algorytmu Euklidesa. Rzeczywiście, używając rozszerzonego algorytmu Euklidesa, reprezentujemy liczbę 1 jako liniową kombinację liczb A I T:

Pomnóżmy obie strony tej równości przez B, otrzymujemy: B = abk + mrb, Gdzie abk - B = - mrb, to jest A ∙ (bq) = B(mod M) I bq- rozwiązanie porównania (2.2).

Innym rozwiązaniem jest skorzystanie z twierdzenia Eulera. Ponownie wierzymy, że NWD(a, T)= 1. Stosujemy twierdzenie Eulera: . Pomnóż obie strony porównania przez B: . Przepisywanie ostatniego wyrażenia jako , otrzymujemy, że jest to rozwiązanie porównania (2.2).

Niech teraz NWD( A, M) = D>1. Następnie A = ATD, M = MTD, gdzie NWD( A 1 , M 1) = 1. Ponadto jest to konieczne B = B 1 D, aby porównanie było rozstrzygalne. Jeśli X 0 - rozwiązanie porównawcze A 1 X = B 1 (mod M 1), i jedyny, gdyż NWD( A 1 , M 1) = 1, zatem X 0 będzie rozwiązaniem i porównaniem A 1 xd = pierś 1 (mod M 1), czyli oryginalne porównanie (2.2). Odpoczynek D- 1 rozwiązania znajdują się na podstawie Twierdzenia 2.5.

Treść.

Wstęp

§1. Porównanie modulo

§2. Porównanie właściwości

1. Właściwości porównania niezależne od modułu
2. Zależne od modułu właściwości porównań

§3. System odliczeń

1. Pełny system odliczeń
2. Obniżony system odliczeń

§4. Twierdzenie Eulera i Fermat

1. Funkcja Eulera
2. Twierdzenie Eulera i Fermat

Rozdział 2. Teoria porównań ze zmienną

§1. Podstawowe pojęcia związane z rozwiązywaniem porównań

1. Korzenie porównań
2. Równoważność porównań
3. Twierdzenie Wilsona

§2. Porównania pierwszego stopnia i ich rozwiązania

1. Metoda selekcji
2. Metody Eulera
3. Metoda algorytmu Euklidesa
4. Ciąg dalszy metody frakcjonowania

§3. Systemy porównań I stopnia z jedną niewiadomą

§4. Podział porównań wyższych stopni

§5. Pierwiastki i indeksy pierwotne

1. Kolejność klasy odliczeniowej
2. Pierwiastki pierwotne modulo prime
3. Indeksy modulo prime

Rozdział 3. Zastosowanie teorii porównań

§1. Znaki podzielności

§2. Sprawdzanie wyników działań arytmetycznych

§3. Zamiana ułamka zwykłego na ułamek końcowy

dziesiętny ułamek systematyczny

Wniosek

Literatura

Wstęp

W naszym życiu często mamy do czynienia z liczbami całkowitymi i problemami z nimi związanymi. W tej pracy rozważam teorię porównania liczb całkowitych.

Dwie liczby całkowite, których różnica jest wielokrotnością danej liczby naturalnej M nazywane są porównywalnymi modułami M.

Słowo „moduł” pochodzi od łacińskiego modułu, co w języku rosyjskim oznacza „miarę”, „wielkość”.

Zdanie „a jest porównywalne z b modulo m” zwykle zapisuje się jako ab (mod m) i nazywa się porównaniem.

Definicja porównania została sformułowana w książce K. Gaussa „Arithmetic Studies”. Dzieło to, napisane po łacinie, zaczęto drukować w 1797 r., jednak księgę wydano dopiero w 1801 r., gdyż ówczesny proces drukarski był niezwykle pracochłonny i długotrwały. Pierwsza część książki Gaussa nosi tytuł: „O porównywaniu liczb w ogóle”.

Porównania są bardzo wygodne w przypadkach, gdy w niektórych badaniach wystarczy znać liczby z dokładnością do wielokrotności pewnej liczby.

Przykładowo, jeśli interesuje nas, na jaką cyfrę kończy się sześcian liczby całkowitej a, to wystarczy, że znamy tylko wielokrotności 10 i możemy zastosować porównania modulo 10.

Celem tej pracy jest rozważenie teorii porównań i poznanie podstawowych metod rozwiązywania porównań z niewiadomymi, a także zbadanie zastosowania teorii porównań w matematyce szkolnej.

Praca składa się z trzech rozdziałów, każdy rozdział podzielony jest na akapity, a akapity na akapity.

W pierwszym rozdziale przedstawiono ogólne zagadnienia teorii porównań. Rozważamy tutaj pojęcie porównania modulo, właściwości porównań, pełny i zredukowany układ reszt, funkcję Eulera, twierdzenie Eulera i Fermata.

Rozdział drugi poświęcony jest teorii porównań z nieznanym. Zarysowuje podstawowe pojęcia związane z rozwiązywaniem porównań, omawia metody rozwiązywania porównań pierwszego stopnia (metoda selekcji, metoda Eulera, metoda algorytmu Euklidesa, metoda ułamków ciągłych, wykorzystanie wskaźników), systemy porównań pierwszego stopnia z jedną niewiadomą, porównania wyższych stopni itp.

Rozdział trzeci zawiera niektóre zastosowania teorii liczb w matematyce szkolnej. Rozważane są znaki podzielności, sprawdzanie wyników działań i zamiana ułamków zwykłych na systematyczne ułamki dziesiętne.

Prezentacji materiału teoretycznego towarzyszy duża liczba przykładów, które ukazują istotę wprowadzonych pojęć i definicji.

Rozdział 1. Ogólne zagadnienia teorii porównań

§1. Porównanie modulo

Niech z będzie pierścieniem liczb całkowitych, m będzie stałą liczbą całkowitą, a m·z będzie zbiorem wszystkich liczb całkowitych będących wielokrotnościami m.

Definicja 1. Mówi się, że dwie liczby całkowite aib są porównywalne modulo m, jeśli m dzieli a-b.

Jeżeli liczby aib są porównywalne modulo m, to napisz a b (mod m).

Warunek A b (mod m) oznacza, że ​​a-b jest podzielne przez m.

a b (mod m)↔(a-b) m

Zdefiniujmy, że relacja porównywalności modulo m pokrywa się z relacją porównywalności modulo (-m) (podzielność przez m jest równoznaczna z podzielnością przez –m). Dlatego bez utraty ogólności możemy założyć, że m>0.

Przykłady.

Twierdzenie. (znak porównywalności liczb spirytusowych modulo m): Dwie liczby całkowite a i b są porównywalne modulo m wtedy i tylko wtedy, gdy a i b mają takie same reszty z dzielenia przez m.

Dowód.

Niech reszty z dzielenia aib przez m będą równe, czyli a=mq₁+r,(1)

B=mq₂+r, (2)

Gdzie 0≤r≥m.

Odejmij (2) od (1), otrzymamy a-b= m(q₁- q₂), czyli a-b m lub a b (mod m).

I odwrotnie, niech a b (mod m). Oznacza to, że a-b m lub a-b=mt, t z (3)

Podziel b przez m; dostajemy b=mq+r w (3), będziemy mieli a=m(q+t)+r, czyli dzieląc a przez m otrzymamy taką samą resztę jak przy dzieleniu b przez m.

Przykłady.

5=4·(-2)+3

23=4,5+3

24=3,8+0

10=3·3+1

Definicja 2. Dwie lub więcej liczb, które przy dzieleniu przez m dają identyczne reszty, nazywane są resztami równymi lub porównywalnymi modulo m.

Przykłady.

Mamy: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) dzieli się przez m => nasze porównanie jest prawidłowe.

1. Udowodnij, że poniższe porównania są fałszywe:

Jeśli liczby są porównywalne modulo m, to mają z sobą to samo gcd.

Mamy: 4=2·2, 10=2·5, 25=5,5

NWD(4,10) = 2, NWD(25,10) = 5, zatem nasze porównanie jest błędne.

§2. Porównanie właściwości

1. Niezależne od modułu właściwości porównań.

Wiele właściwości porównań jest podobnych do właściwości równości.

a) refleksyjność:a (mod m) (dowolna liczba całkowita A porównywalny ze sobą modulo m);

B) symetria: jeśli a b (mod m), następnie b a (mod m);

C) przechodniość: jeśli a b (mod m) i b z (mod m), następnie a z (mod m).

Dowód.

Według warunku m/(a-b) i m/ (c-d). Zatem m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Przykłady.

Znajdź resztę podczas dzielenia o 13.

Rozwiązanie: -1 (mod 13) i 1 (mod 13), następnie (-1)+1 0 (mod 13), czyli pozostała część podziału do 13 wynosi 0.

a-c b-d (mod m).

Dowód.

Według warunku m/(a-b) i m/(c-d). Zatem m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (konsekwencja właściwości 1, 2, 3). Możesz dodać tę samą liczbę całkowitą do obu stron porównania.

Dowód.

Niech a b (mod m) i k jest dowolną liczbą całkowitą. Z właściwości refleksyjności

k=k (mod m), a zgodnie z właściwościami 2 i 3 mamy a+k b+k (mod m).

a·c·d (mod m).

Dowód.

Według warunku a-b є mz, c-d є mz. Zatem a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, czyli a·c·d (mod m).

Konsekwencja. Obie strony porównania można podnieść do tej samej nieujemnej potęgi całkowitej: jeśli ab (mod m) i s jest nieujemną liczbą całkowitą, wówczas a s b s (mod m).

Przykłady.

Rozwiązanie: oczywiście 13 1 (mod 3)

2 -1 (mod 3)

Zatem 5 -1 (mod 3).

- · 1-1 0 (mod 13)

Odpowiedź: wymagana reszta wynosi zero, a A jest podzielne przez 3.

Rozwiązanie:

Udowodnijmy, że 1+ 0(mod13) lub 1+ 0(mod 13)

1+ =1+ 1+ =

Od 27 1 (mod 13), to 1+ 1+1·3+1·9 (mod 13).

itp.

3. Znajdź resztę z dzielenia przez resztę liczby o 24.

Mamy: 1 (mod 24), tzw

1 (mod 24)

Dodając 55 do obu stron porównania, otrzymujemy:

(mod 24).

Mamy zatem: (mod 24).

(mod 24) dla dowolnego k є N.

Stąd (mod 24). Od (-8)16 (mod 24), wymagana reszta to 16.

1. Obie strony porównania można pomnożyć przez tę samą liczbę całkowitą.

2.Właściwości porównań w zależności od modułu.

Dowód.

Ponieważ a b (mod t), to (a - b) t. A ponieważ t n , to ze względu na przechodniość relacji podzielności(a - b n), czyli a b (mod n).

Przykład.

Znajdź resztę z dzielenia 196 przez 7.

Rozwiązanie:

Wiedząc, że 196= , możemy napisać 196(mod 14). Skorzystajmy z poprzedniej własności, 14 7, otrzymujemy 196 (mod 7), czyli 196 7.

1. Obie strony porównania i moduł można pomnożyć przez tę samą dodatnią liczbę całkowitą.

Dowód.

Niech a b (mod t ) i c jest dodatnią liczbą całkowitą. Następnie a-b = mt i ac-bc=mtc lub ac BC (mod mc).

Przykład.

Określ, czy wartość wyrażenia wynosi Liczba całkowita.

Rozwiązanie:

Przedstawmy ułamki w formie porównań: 4(mod 3)

1 (mod 9)

31 (mod 27)

Dodajmy te porównania termin po wyrazie (właściwość 2), otrzymamy 124(mod 27) Widzimy, że 124 nie jest liczbą całkowitą podzielną przez 27, stąd znaczenie wyrażenianie jest również liczbą całkowitą.

1. Obie strony porównania można podzielić przez ich wspólny współczynnik, jeśli jest on względnie pierwszy do modułu.

Dowód.

Jeśli ok cb (mod m), czyli m/c(a-b) i liczba Z liczba względnie pierwsza do m, (c,m)=1, następnie m dzieli a-b. Stąd, a b (mod t).

Przykład.

60 9 (mod 17), po podzieleniu obu stron porównania przez 3 otrzymujemy:

20 (mod 17).

Ogólnie rzecz biorąc, nie da się podzielić obu stron porównania przez liczbę, która nie jest względnie pierwsza względem modułu, gdyż po podzieleniu można otrzymać liczby nieporównywalne pod względem danego modułu.

Przykład.

8 (mod 4), ale 2 (mod 4).

1. Obie strony porównania i moduł można podzielić przez ich wspólny dzielnik.

Dowód.

Jeśli ka kb (mod km), następnie k (a-b) dzieli się przez km. Zatem a-b jest podzielne przez m, tj a b (mod t).

Dowód.

Niech P (x) = do 0 x n + do 1 x n-1 + ... + do n-1 x+ do n. Zatem według warunku a b (mod t).

a k b k (mod m) dla k = 0, 1, 2, …, n. Mnożąc obie strony każdego z uzyskanych porównań n+1 przez c n-k, otrzymujemy:

c n-k a k c n-k b k (mod m), gdzie k = 0, 1, 2, …,n.

Sumując ostatnie porównania otrzymujemy: P (a) P (b) (mod m). Jeśli a (mod m) i ci d i (mod m), 0 ≤ i ≤n, to

(mod m). Zatem przy porównaniu modulo m poszczególne terminy i czynniki można zastąpić liczbami porównywalnymi modulo m.

Jednocześnie należy zwrócić uwagę na fakt, że wykładników znalezionych w porównaniach nie można zastąpić w ten sposób: z

an c(mod m) i n k(mod m) nie wynika z tego, że a ks (mod m).

Właściwość 11 ma szereg ważnych zastosowań. W szczególności za jego pomocą można podać teoretyczne uzasadnienie znaków podzielności. Aby to zilustrować, jako przykład podamy wyprowadzenie testu podzielności przez 3.

Przykład.

Każdą liczbę naturalną N można przedstawić jako liczbę systematyczną: N = a 0 10 n + za 1 10 n-1 + ... + za n-1 10 + za n .

Rozważmy wielomian f(x) = a 0 x n + za 1 x n-1 + ... + za n-1 x+a n . Ponieważ

10 1 (mod 3), następnie według właściwości 10 f (10) f(1) (mod 3) lub

N = za 0 10 n + za 1 10 n-1 + ... + za n-1 10 + za n za 1 + za 2 +…+ za n-1 + za n (mod 3), czyli aby N było podzielne przez 3, konieczne i wystarczające jest, aby suma cyfr tej liczby była podzielna przez 3.

§3. Systemy odliczeń

1. Pełny system odliczeń.

Równe liczby resztkowe lub, co to jest to samo, porównywalne modulo m, tworzą klasę liczb modulo m.

Z tej definicji wynika, że ​​wszystkie liczby w klasie odpowiadają tej samej reszcie r i otrzymamy wszystkie liczby w klasie, jeśli w postaci mq+r sprawimy, że q przejdzie przez wszystkie liczby całkowite.

Odpowiednio przy m różnych wartościach r mamy m klas liczb modulo m.

Dowolną liczbę należącą do klasy nazywamy resztą modulo m w odniesieniu do wszystkich liczb tej samej klasy. Pozostałość otrzymaną przy q=0, równą reszcie r, nazywa się najmniejszą resztą nieujemną.

Pozostałość ρ, najmniejsza w wartości bezwzględnej, nazywana jest resztą absolutnie najmniejszą.

Oczywiście dla r mamy ρ=r; w r> mamy ρ=r-m; w końcu, jeśli m jest parzyste i r=, to dowolną z dwóch liczb można przyjąć jako ρ i -m= - .

Wybierzmy z każdej klasy reszt modulo T jeden numer na raz. Dostajemy t liczby całkowite: x 1,…, x m. Zbiór (x 1,…, x t) nazywamy kompletny system odliczeń modulo m.

Ponieważ każda klasa zawiera nieskończoną liczbę reszt, możliwe jest złożenie nieskończonej liczby różnych kompletnych układów reszt dla danego modułu m, z których każdy zawiera t odliczenia.

Przykład.

Skompiluj kilka kompletnych systemów odliczeń modulo T = 5. Mamy klasy: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Stwórzmy kilka kompletnych systemów odliczeń, biorąc po jednym odliczeniu z każdej klasy:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

itp.

Najpopularniejszy:

1. Kompletny system najmniejszych reszt nieujemnych: 0, 1, t -1 W powyższym przykładzie: 0, 1, 2, 3, 4. Ten układ reszt jest prosty do stworzenia: należy zapisać wszystkie nieujemne reszty otrzymane z dzielenia przez m.
2. Kompletny system reszt najmniej dodatnich(z każdej klasy pobierane jest najmniejsze dodatnie odliczenie):

1, 2, …, m. W naszym przykładzie: 1, 2, 3, 4, 5.

1. Kompletny system absolutnie minimalnych odliczeń.W przypadku nieparzystego m, absolutnie najmniejsze reszty są reprezentowane obok siebie.

- ,…, -1, 0, 1,…, ,

a w przypadku parzystego m, jeden z dwóch rzędów

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

W podanym przykładzie: -2, -1, 0, 1, 2.

Rozważmy teraz podstawowe właściwości całego układu reszt.

Twierdzenie 1 . Dowolny zbiór m liczb całkowitych:

x l , x 2 ,…, x m (1)

parami nieporównywalny modulo m, tworzy kompletny system reszt modulo m.

Dowód.

1. Każda z liczb w zbiorze (1) należy do określonej klasy.
2. Dowolne dwie liczby x i oraz x j z (1) są ze sobą nieporównywalne, tj. należą do różnych klas.
3. W (1) jest m liczb, czyli tyle samo, ile jest klas modulo T.

x 1, x 2,…, x t - kompletny system odliczeń modulo m.

Twierdzenie 2. Niech (a, m) = 1, b - dowolna liczba całkowita; a następnie, jeśli x 1, x 2,…, x t jest kompletnym systemem reszt modulo m, to zbiór liczb ax 1 + b, topór 2 + b,…, topór m + b jest także kompletnym układem reszt modulo m.

Dowód.

Rozważmy

Topór 1 + b, topór 2 + b,…, topór m + b (2)

1. Każda z liczb w zbiorze (2) należy do określonej klasy.
2. Dowolne dwie liczby ax i +b i ax j + b z (2) są ze sobą nieporównywalne, to znaczy należą do różnych klas.

Rzeczywiście, jeśli w (2) byłyby dwie takie liczby, że

topór i +b topór j + b (mod m), (i = j), wtedy otrzymalibyśmy topór i topór j (mod t). Ponieważ (a, t) = 1, to właściwość porównań może zredukować obie części porównania o A . Otrzymujemy x i x j (mod m).

Według warunku x i x j (mod t) w (i = j) , ponieważ x 1, x 2, ..., x m - kompletny system odliczeń.

1. Zbiór liczb (2) zawiera T liczb, czyli tyle, ile jest klas modulo m.

Zatem topór 1 + b, topór 2 + b,…, topór m + b - kompletny układ reszt modulo m.

Przykład.

Niech m = 10, a = 3, b = 4.

Weźmy jakiś kompletny układ reszt modulo 10, na przykład: 0, 1, 2,…, 9. Ułóżmy liczby w postaci topór + b. Otrzymujemy: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Otrzymany zbiór liczb stanowi kompletny układ reszt modulo 10.

1. Dany system odliczeń.

Udowodnimy następujące twierdzenie.

Twierdzenie 1.

Liczby tej samej klasy reszt modulo m mają ten sam największy wspólny dzielnik z m: if a b (mod m), wówczas (a, m) = (b, m).

Dowód.

Niech a b (mod m). Wtedy a = b + mt, gdzie t є z. Z tej równości wynika, że ​​(a, t) = (b, t).

Rzeczywiście, niech δ będzie wspólnym dzielnikiem a i m, a następnie aδ, m δ. Ponieważ a = b + mt, wtedy b=a-mt, zatem bδ. Dlatego każdy wspólny dzielnik liczb a i m jest wspólnym dzielnikiem m i b.

I odwrotnie, jeśli m δ i b δ, to a = b +mt jest podzielna przez δ i dlatego każdy wspólny dzielnik m i b jest wspólnym dzielnikiem a i m. Twierdzenie zostało udowodnione.

Definicja 1. Największy wspólny dzielnik modułu t i dowolna liczba a z tej klasy odliczeń wg T zwany największym wspólnym dzielnikiem T i ta klasa odliczeń.

Definicja 2. Klasa pozostałości a modulo t nazywa się względnie pierwszym do modułu M , jeśli jest to największy wspólny dzielnik a i t równa się 1 (to znaczy, jeśli m i dowolna liczba z a są względnie pierwsze).

Przykład.

Niech t = 6. Klasa pozostałości 2 składa się z liczb (..., -10, -4, 2, 8, 14, ...). Największy wspólny dzielnik którejkolwiek z tych liczb i modułu 6 wynosi 2. Zatem (2, 6) = 2. Największy wspólny dzielnik dowolnej liczby z klasy 5 i modułu 6 wynosi 1. Zatem klasa 5 jest względnie pierwsza do modułu 6 .

Wybierzmy po jednej liczbie z każdej klasy reszt, która jest względnie pierwsza z modulo m. Otrzymujemy system odliczeń będący częścią pełnego systemu odliczeń. Dzwonią do niejzredukowany układ reszt modulo m.

Definicja 3. Zbiór reszt modulo m, wziętych po jednej z każdej liczby względnie pierwszej T klasa reszt dla tego modułu nazywana jest zredukowanym układem reszt.

Z definicji 3 wynika sposób otrzymywania zredukowanego układu reszt modulo T: należy spisać jakiś kompletny układ reszt i usunąć z niego wszystkie reszty, które nie są względnie pierwsze z m. Pozostały zestaw odliczeń stanowi obniżony system odliczeń. Oczywiście można złożyć nieskończoną liczbę układów reszt modulo m.

Jeśli za układ początkowy przyjmiemy kompletny układ najmniejszych nieujemnych lub absolutnie najmniejszych reszt, to stosując wskazaną metodę otrzymamy odpowiednio zredukowany układ najmniej nieujemnych lub absolutnie najmniejszych reszt modulo m.

Przykład.

Jeśli T = 8, wówczas 1, 3, 5, 7 to zredukowany układ najmniejszych reszt nieujemnych, 1, 3, -3, -1- zredukowany system absolutnie najmniejszych odliczeń.

Twierdzenie 2.

Pozwalać liczba klas względnie pierwsza do m jest równa k.Następnie dowolny zbiór k liczb całkowitych

parami nieporównywalny modulo m i względnie pierwszy do m, jest zredukowanym układem reszt modulo m.

Dowód

A) Każda liczba w populacji (1) należy do określonej klasy.

1. Wszystkie liczby z (1) są parami nieporównywalne pod względem modułu T, to znaczy należą do różnych klas modulo m.
2. Każda liczba z (1) jest względnie pierwsza T, to znaczy, że wszystkie te liczby należą do różnych klas względnie pierwszych do modulo m.
3. Razem (1) dostępne k liczb, czyli tyle, ile powinien zawierać zredukowany układ reszt modulo m.

Dlatego zbiór liczb(1) - zredukowany system odliczeń modulo T.

§4. Funkcja Eulera.

Twierdzenia Eulera i Fermata.

1. Funkcja Eulera.

Oznaczmy przez φ(T) liczba klas reszt modulo m względnie pierwsza do m, czyli liczba elementów zredukowanego układu reszt modulo t. Funkcja φ (t) jest numeryczny. Dzwonią do niejFunkcja Eulera.

Wybierzmy jako przedstawicieli klas reszt modulo t liczby 1, ..., t - 1, t. Następnie φ (t) - liczba takich liczb względnie pierwszych t. Innymi słowy, φ (t) - liczba liczb dodatnich nieprzekraczających m i względnie pierwszych do m.

Przykłady.

1. Niech t = 9. Kompletny układ reszt modulo 9 składa się z liczb 1, 2, 3, 4, 5, 6, 7, 8, 9. Spośród nich liczby 1,2,4, 5, 7, 8 są względnie pierwsze do 9. Skoro liczba tych liczb wynosi 6, to φ (9) = 6.
2. Niech t = 12. Kompletny układ reszt składa się z liczb 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Spośród nich liczby 1, 5, 7, 11 są względnie pierwsze do 12 . To znaczy

φ(12) = 4.

O godz = 1, kompletny układ reszt składa się z jednej klasy 1. Wspólnym naturalnym dzielnikiem liczb 1 i 1 jest 1, (1, 1) = 1. Na tej podstawie przyjmujemy φ(1) = 1.

Przejdźmy do obliczenia funkcji Eulera.

1) Jeśli t = p jest liczbą pierwszą, to φ(p) = p-1.

Dowód.

Odliczenia 1, 2, ..., p- 1 i tylko one są względnie pierwsze z liczbą pierwszą R. Dlatego φ (р) = р - 1.

2) Jeśli t = p k - moc główna p., zatem

φ(t) = (p - 1) . (1)

Dowód.

Kompletny system odliczeń modulo t = p k składa się z cyfr 1,..., p k - 1, p k Dzielniki naturalne T są stopnie R. Dlatego liczba Amoże mieć wspólny dzielnik z m innym niż 1, tylko w przypadku kiedyApodzielony przezR.Ale wśród liczb 1, ... , Pk -1 NARtylko liczby są podzielnep, 2p, ..., s2 , ... RDo, których liczba jest równaRDo: p = pk-1. Oznacza to, że są one porównywalnet = pDoodpoczynekRDo- Rk-1= strk-l(p-1)liczby. To tego dowodzi

φ (RDo) = strk-1(p-1).

Twierdzenie1.

Funkcja Eulera jest multiplikatywna, to znaczy dla liczb względnie pierwszych m i n mamy φ (mn) = φ(m) φ (n).

Dowód.

Pierwszy wymóg definicji funkcji multiplikatywnej jest spełniony w trywialny sposób: funkcję Eulera definiuje się dla wszystkich liczb naturalnych, a φ (1) = 1. Musimy to tylko pokazać jeślitypnastępnie liczby względnie pierwsze

φ (tp)= φ (T) φ (P).(2)

Uporządkujmy cały system odliczeń modulotpJakPXT -matryce

1 2 T

t +1 t +2 2t

………………………………

(P -1) t+1 (P -1) m+2 piątek

PonieważTIPsą względnie pierwsze, to liczbaXwzajemnie, po prostu ztpwtedy i tylko kiedyXwzajemnie, po prostu zTIXwzajemnie, po prostu zP. Ale numerkm+twzajemnie, po prostu zTwtedy i tylko wtedy gdyTwzajemnie, po prostu zT.Dlatego liczby względnie pierwsze do m znajdują się w tych kolumnach, dla którychTprzebiega przez zredukowany układ reszt moduloT.Liczba takich kolumn jest równa φ(T).Każda kolumna przedstawia kompletny system odliczeń moduloP.Z tych odliczeń φ(P)porównaj zP.Oznacza to, że całkowita liczba liczb względnie pierwszych izTi przy n równym φ(T)φ(rzecz)

(φ (T)kolumny, w każdej z nich brane jest φ(P)liczby). Te liczby i tylko one są względnie pierwszeitp.To tego dowodzi

φ (tp)= φ (T) φ (P).

Przykłady.

№1 . Udowodnij prawdziwość następujących równości

φ(4n) =

Dowód.

№2 . Rozwiązać równanie

Rozwiązanie:ponieważ(m)=, To= , to jest=600, =75, =3·, wtedy x-1=1, x=2,

y-1=2, y=3

Odpowiedź: x=2, y=3

Możemy obliczyć wartość funkcji Eulera(m), znając kanoniczną reprezentację liczby m:

m=.

Ze względu na multiplikatywność(m) mamy:

(m)=.

Ale zgodnie ze wzorem (1) znajdujemy to

-1) i dlatego

(3)

Równość (3) można przepisać jako:

Ponieważ= m, zatem(4)

Formuła (3) lub, co jest tym samym, (4) jest tym, czego szukamy.

Przykłady.

№1 . Jaka jest kwota?

Rozwiązanie:,

, =18 (1- ) (1- =18 , Następnie= 1+1+2+2+6+6=18.

№2 . Na podstawie własności funkcji liczbowej Eulera wykazać, że w ciągu liczb naturalnych istnieje nieskończony zbiór liczb pierwszych.

Rozwiązanie:Zakładając, że liczba liczb pierwszych jest zbiorem skończonym, zakładamy to- największa liczba pierwsza i niech a=jest iloczynem wszystkich liczb pierwszych, w oparciu o jedną z właściwości funkcji liczbowej Eulera

Ponieważ a≥, to a jest liczbą złożoną, ale ponieważ jej kanoniczna reprezentacja zawiera wszystkie liczby pierwsze, to=1. Mamy:

=1 ,

co jest niemożliwe i w ten sposób udowodniono, że zbiór liczb pierwszych jest nieskończony.

№3 .Rozwiązać równanie, gdzie x=I=2.

Rozwiązanie:Korzystamy z własności funkcji numerycznej Eulera,

,

i według warunku=2.

Wyraźmy z=2 , otrzymujemy, zamień w

:

(1+ -1=120, =11 =>

Wtedy x=, x=11·13=143.

Odpowiedź:x= 143

2. Twierdzenie Eulera i Fermat.

Twierdzenie Eulera odgrywa ważną rolę w teorii porównań.

Twierdzenie Eulera.

Jeśli liczba całkowita a jest względnie pierwsza do m, to

(1)

Dowód.Pozwalać

(2)

istnieje zredukowany układ reszt modulo m.

JeśliAjest zatem liczbą całkowitą względnie pierwszą m

(3)

Porównanie pierwszego stopnia z jedną niewiadomą ma postać:

F(X) 0 (mod M); F(X) = Oh + oraz n. (1)

Rozwiąż porównanie- oznacza znalezienie wszystkich wartości x, które je spełniają. Nazywa się dwa porównania, które spełniają te same wartości x równowartość.

Jeśli porównanie (1) jest spełnione przez którekolwiek X = X 1, to (według 49) wszystkie liczby porównywalne X 1, moduł M: x x 1 (mod M). Uważa się, że cała ta klasa liczb jest jedno rozwiązanie. Przy takim porozumieniu można wyciągnąć następujący wniosek.

66.C wyrównanie (1) będzie miał tyle rozwiązań, ile reszt pełnego układu je spełnia.

Przykład. Porównanie

6X– 4 0 (mod 8)

Spośród liczb 0, 1,2, 3, 4, 5, 6, 7 dwie liczby spełniają pełny układ reszt modulo 8: X= 2 i X= 6. Dlatego to porównanie ma dwa rozwiązania:

X 2 (mod 8), X 6 (mod 8).

Porównanie pierwszego stopnia poprzez przesunięcie wyrazu wolnego (o przeciwnym znaku) na prawą stronę można sprowadzić do postaci

topór B(mod M). (2)

Rozważmy porównanie spełniające warunek ( A, M) = 1.

Według 66, nasze porównanie ma tyle rozwiązań, ile jest reszt pełnego układu, które je spełniają. Ale kiedy X przebiega przez cały system reszt modulo T, To Oh przebiega przez cały system odliczeń (spośród 60). Dlatego dla jednej i tylko jednej wartości X, pobrane z całego systemu, Oh będzie porównywalny z B. Więc,

67. Gdy (a, m) = 1 oś porównania B(mod M)ma jedno rozwiązanie.

Niech teraz ( A, M) = D> 1. Zatem dla porównania (2) aby mieć rozwiązania konieczne jest (z 55) tego B podzielony przez D, w przeciwnym razie porównanie (2) jest niemożliwe dla dowolnej liczby całkowitej x . Zakładając zatem B wielokrotności D, włóżmy A = A 1 D, B = B 1 D, M = M 1 D. Wtedy porównanie (2) będzie równoważne temu (w skrócie D): A 1 X B 1 (mod M), w którym już ( A 1 , M 1) = 1, i dlatego będzie miało jedno rozwiązanie modulo M 1. Pozwalać X 1 – najmniejsza nieujemna reszta tego rozwiązania modulo m 1 , wtedy wszystkie liczby to x , tworzące to rozwiązanie znajdują się w formie

X X 1 (mod M 1). (3)

Modulo m, liczby (3) tworzą nie jedno rozwiązanie, ale więcej, dokładnie tyle rozwiązań, ile jest liczb (3) w szeregu 0, 1, 2, ..., M - 1 najmniejsza nieujemna reszta modulo M. Ale spadną tutaj następujące liczby (3):

X 1 , X 1 + M 1 , X 1 + 2M 1 , ..., X 1 + (D – 1) M 1 ,

te. Całkowity D liczby (3); zatem porównanie (2) ma D decyzje.

Otrzymujemy twierdzenie:

68. Niech (a, m) = d. Porównanie topora b ( mod m) jest niemożliwe, jeśli b nie jest podzielne przez d. Gdy b jest wielokrotnością d, porównanie ma d rozwiązań.

69. Metoda rozwiązywania porównań pierwszego stopnia oparta na teorii ułamków ciągłych:

Rozwinięcie relacji na ułamek ciągły mama,

i patrząc na dwa ostatnie pasujące ułamki:

zgodnie z właściwościami ułamków ciągłych (wg 30 ) mamy

Zatem porównanie ma rozwiązanie

znaleźć, co wystarczy do obliczenia P. n– 1 według metody określonej w 30.

Przykład. Rozwiążmy porównanie

111X= 75 (mod 321). (4)

Tutaj (111, 321) = 3, a 75 jest wielokrotnością 3. Dlatego porównanie ma trzy rozwiązania.

Dzieląc obie strony porównania i moduł przez 3, otrzymujemy porównanie

37X= 25 (mod 107), (5)

które musimy najpierw rozwiązać. Mamy

Q
P 3

Zatem w tym przypadku N = 4, Pn – 1 = 26, B= 25 i mamy rozwiązanie porównania (5) w postaci

X–26 ∙ 25 99 (mod 107).

Stąd rozwiązania porównania (4) przedstawiają się następująco:

X 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod 321).

Obliczanie elementu odwrotnego o zadany modulo

70.Jeśli liczby są liczbami całkowitymi A I N są względnie pierwsze, to istnieje liczba A', satysfakcjonujące porównanie za ∙ za′ ≡ 1 (mod N). Numer A' zwany multiplikatywna odwrotność modulo n i używana do tego notacja to A- 1 (mod N).

Obliczenia wielkości wzajemnych modulo pewnej wartości można dokonać rozwiązując porównanie pierwszego stopnia z niewiadomą, w którym X numer zaakceptowany A'.

Aby znaleźć rozwiązanie porównawcze

a∙x≡ 1 (mod M),

Gdzie ( jestem)= 1,

możesz skorzystać z algorytmu Euklidesa (69) lub twierdzenia Fermata-Eulera, które stwierdza, że ​​jeśli ( jestem) = 1, zatem

A φ( M) ≡ 1(mod M).

X ≡ A φ( M)–1 (mod M).

Grupy i ich własności

Grupy są jedną z klas taksonomicznych stosowanych w klasyfikacji struktur matematycznych o wspólnych charakterystycznych właściwościach. Grupy składają się z dwóch elementów: pęczek (G) I operacje() zdefiniowane w tym zestawie.

Pojęcia zbioru, elementu i przynależności to podstawowe, niezdefiniowane pojęcia współczesnej matematyki. Każdy zbiór jest definiowany przez zawarte w nim elementy (które z kolei mogą być również zbiorami). Zatem mówimy, że zbiór jest zdefiniowany lub dany, jeśli dla dowolnego elementu możemy stwierdzić, czy należy on do tego zbioru, czy nie.

Na dwa komplety A, B dokumentacja B A, B A, B∩ A, B A, B \ A, A × B odpowiednio to oznaczają B jest podzbiorem zbioru A(tj. dowolny element z B zawarta jest także w A np. zbiór liczb naturalnych zawiera się w zbiorze liczb rzeczywistych; poza tym zawsze A A), B jest podzbiorem właściwym zbioru A(te. B A I B ≠ A), skrzyżowanie wielu B I A(tj. wszystkie takie elementy, które leżą jednocześnie w A, i w B, na przykład przecięcie liczb całkowitych i dodatnich liczb rzeczywistych jest zbiorem liczb naturalnych), suma zbiorów B I A(tj. zbiór składający się z elementów leżących albo w A, albo w B), ustaw różnicę B I A(tj. zbiór elementów znajdujących się w B, ale nie kłam A), Iloczyn kartezjański zbiorów A I B(tj. zbiór par postaci ( A, B), Gdzie A A, B B). Przez | A| potęga zbioru jest zawsze oznaczana A, tj. liczba elementów w zestawie A.

Operacja to reguła, według której dowolne dwa elementy zbioru G(A I B) jest dopasowywany do trzeciego elementu z G: a b.

Dużo elementów G z operacją nazywa się Grupa, jeżeli spełnione są poniższe warunki.

Rozważmy system porównań

Gdzie f1(x), f2(x), …. , fs(x)€Z[x].

Twierdzenie 1. Niech M = będzie najmniejszą wspólną wielokrotnością liczb m1,m2,…,ms. Jeżeli spełnia system (2), to dowolna liczba z klasy a modulo M spełnia ten system.

Dowód. Niech b€ do klasy a. Ponieważ a ≡ b(mod M), to a ≡b(mod m), i= 1,2,...,s (właściwość porównawcza 16). W konsekwencji b, podobnie jak a, spełnia każde porównanie systemu, co dowodzi twierdzenia. Naturalnym jest zatem uznanie rozwiązania układu (2) za klasę modulo M.

Definicja. Rozwiązanie układu porównań(2) jest klasą liczb modulo M = spełniających każde porównanie układu.

12. Zauważmy od razu, że liczby nieparzyste nie spełniają drugiego porównania. Biorąc liczby parzyste z pełnego układu reszt modulo 12, poprzez bezpośrednią weryfikację przekonujemy się, że liczby 2, -2, 6 spełniają drugie porównanie, a układ ma dwa rozwiązania: x ≡ 2(mod l2), x ≡ - 2 (mod 12).

Rozważmy system porównań pierwszego stopnia (3)

Twierdzenie 2. Niech d=(m1,m2), M = .

Jeśli c1 - c2 nie jest podzielne przez d, to układ (3) nie ma rozwiązań.

Jeżeli (c1 -c2):d, to układ (3) ma jedno rozwiązanie - klasę modulo M.

Dowód. Z pierwszego porównania x = c1+m1t, t€Z. Podstaw do drugiego porównania: с1+ m1t ≡ c2(mod m2) lub

m1t ≡ c2-cl (mod m2). Porównanie to ma rozwiązanie tylko wtedy, gdy (c2 – c1): d.

Rozwiązaniem jest klasa modulo (Twierdzenie 4 z §2).

Niech rozwiązaniem będzie , czyli gdzie k€Z.

M== , czyli x≡c1+m1t0(mod M) jest rozwiązaniem

Przykłady.

1. :2, system ma jedną klasę rozwiązań modulo 24. Z 1. porównania x =2+6t. Podstawiając x do drugiego porównania, mamy: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, czyli x≡-4(mod 24).

2. 7-3 nie jest podzielne przez 3, układ nie ma rozwiązań.

Wniosek 1. System porównawczy (4)

Albo nie ma rozwiązań, albo ma jedno rozwiązanie - klasę modulo M=.

Dowód. Jeżeli układ dwóch pierwszych porównań nie ma rozwiązań, to (4) nie ma rozwiązań. Jeśli ma rozwiązanie x ≡ a(mod), to dodając do tego porównania trzecie porównanie układu, ponownie otrzymujemy układ postaci (3), który albo ma jedno rozwiązanie, albo nie ma żadnych rozwiązań. Jeśli ma rozwiązanie, będziemy kontynuować tę drogę, aż wyczerpamy wszystkie porównania układu (4). Jeśli istnieje rozwiązanie, to jest to klasa modulo M.

Komentarz. Wykorzystano tutaj właściwość LCM: =.

Konsekwencja 2. Jeżeli m1,m2,…,ms są parami względnie pierwsze, to układ (4) ma jedno rozwiązanie – klasę modulo M=m1m2…ms.

Przykład:

Ponieważ moduły są stosunkowo proste parami, system ma jedno rozwiązanie - klasa modulo 105 = 5*3*7. Od pierwszego porównania

Do drugiego porównania podstawiamy: 2 +5t≡ 0(mod 3) lub 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Podstawmy w trzecim porównaniu:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. wtedy x=-3+15(1+7l); x=12+105l; x≡12 (mod 105).

Poznajmy się inni sposób rozwiązania tego układu, (Wykorzystujemy fakt, że układ ma jedno rozwiązanie.) Pomnóżmy obie części i moduł pierwszego porównania przez 21, drugiego przez 35, a trzeciego przez 15: z sumy pierwsze i trzecie odejmujemy drugie:

(36-35)x ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Rozważmy teraz system porównań pierwszego stopnia formy ogólnej

Jeśli jakieś porównanie tego systemu nie ma rozwiązań, to system nie ma rozwiązań. Jeżeli każde porównanie układu (5) jest rozwiązywalne, to rozwiązujemy je dla x i otrzymujemy układ równoważny postaci (4):

Gdzie (Twierdzenie 4, §2).

Z wniosku 1 wynika, że ​​układ albo nie ma rozwiązań, albo ma jedno rozwiązanie.

Przykład:

Po rozwiązaniu każdego porównania układu otrzymujemy układ równoważny

Układ ten ma jedno rozwiązanie - klasę modulo 105. Mnożąc pierwsze porównanie i moduł przez 3, a drugie przez 35, otrzymujemy

Odejmując pierwsze porównanie pomnożone przez 11 od drugiego porównania, otrzymujemy 2x ≡-62(modl05), z czego x ≡ -31(modl05).

Problemy sprowadzające się do rozważenia systemu porównań pierwszego stopnia były rozważane w arytmetyce chińskiego matematyka Sun Tzu, który żył na początku naszej ery. Jego pytanie zostało postawione w następującej formie: znajdź liczbę, która przy dzieleniu przez dane liczby daje dane reszty. Daje również rozwiązanie równoważne następującemu twierdzeniu.

Twierdzenie (chiński twierdzenie o resztach). Niech m1,m2,…,ms będą parami liczb względnie pierwszych, M = mlm2…ms, β1, β2,…, βs wybranych tak, że

Następnie rozwiązanie układu

Będzie wyglądać jak x≡x0(mod M).

Dowód. Ponieważ otrzymujemy x0≡

W podobny sposób sprawdzamy, czy x0≡c2(mod m2),…, x0≡cs(mod ms), czyli x0 spełnia wszystkie

porównania systemów.

10. Porównania I stopnia. Niepewne równania

§ 2. Porównania pierwszego stopnia. Niepewne równania

Porównanie pierwszego stopnia można sprowadzić do postaci ax≡b(mod m).

Twierdzenie 4. Jeśli (a,m) = 1, to oś porównania ≡b(mod m) (2) ma jednoznaczne rozwiązanie.

Dowód. Weźmy 0,1,2,...,m-1 - kompletny układ reszt modulo m. Ponieważ (a,m) = 1, to 0,a,2a,...,(m-1)a jest także kompletnym układem reszt (Twierdzenie 3, §2, Rozdział 2.). Zawiera jedną i tylko jedną liczbę porównywalną z b modulo m (należącą do tej samej klasy co b). Niech to będzie topór 0, to znaczy topór 0 € klasa b lub topór 0 ≡b(mod m). x ≡x 0 (mod m) jest jedynym rozwiązaniem (2). Twierdzenie zostało udowodnione.

Twierdzenie 5. Jeśli (a, m)= 1, to rozwiązaniem porównania ax≡b(mod m) jest klasa x 0 ≡a φ (m)-1 b(mod m).

Dowód. Ponieważ (a,m) = 1, to zgodnie z zasadą Eulera a φ(m) ≡1(mod m). Łatwo zauważyć, że x 0 ≡a φ (m)-1 b (mod m) jest rozwiązaniem porównania (2). Rzeczywiście, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Z Twierdzenia 4 wynika, że ​​rozwiązanie to jest unikalne.

Rozważmy metody rozwiązań porównawczych topór ≡b(mod m).

1. Metoda selekcji. Biorąc pełny układ reszt modulo m, wybieramy liczby, które spełniają porównanie.

2. Wykorzystanie twierdzenia Eulera (Twierdzenie 5).

3. Metoda konwersji współczynników. Musimy spróbować przekształcić współczynniki tak, aby prawa strona mogła zostać podzielona przez współczynnik x. Przekształcenia, o których mowa, to: zastąpienie współczynników najmniejszymi resztami bezwzględnymi, zastąpienie liczby b liczbą porównywalną co do wartości bezwzględnej (dodanie liczby będącej wielokrotnością wartości bezwzględnej) tak, aby ta ostatnia była podzielna przez a, przesunięcie od aib do innych porównywalnych z nimi liczb, które miałyby wspólny dzielnik itp. W tym przypadku korzystamy z właściwości porównań i twierdzeń o opartych na nich porównaniach równoważnych.

1) 223x ≡ 115 (mod II).

Najpierw zastępujemy współczynniki najmniejszymi odliczeniami wartości bezwzględnych: 3х ≡ 5(mod 11). Jeśli skorzystamy z twierdzenia

Zatem Eulera

x≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Jednak łatwiej jest przeliczyć współczynniki. Zastąpmy porównanie równoważnym, dodając po prawej stronie liczbę będącą wielokrotnością modułu:

3x ≡ 5 + 22 (mod 11). Dzieląc obie strony przez liczbę 3, porównaną do modułu, otrzymujemy x ≡ 9(mod l1).

2) 111x≡ 8 (mod 34).

Stosujemy metodę konwersji współczynników.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16 (mod 34).

Twierdzenie 6. Jeśli (a, m) = d i b nie jest podzielne przez d, to porównanie (1) nie ma rozwiązań.

Dowód (przez zaprzeczenie). Niech klasa x 0 będzie rozwiązaniem, czyli ax 0 ≡b (mod m) lub (ax 0 -b):m, a zatem (ax 0 -b):d. Ale a:d, to b:d jest sprzecznością. Dlatego porównanie nie ma rozwiązań.

Twierdzenie 7. Jeżeli (a,m)= d, d>1, b:d, to porównanie(1) ma d

rozwiązania, które stanowią jedną klasę reszt modulo i można je znaleźć za pomocą wzorów

Gdzie Z spełnia porównanie pomocnicze

Komentarz. Zgodnie z twierdzeniem porównanie (1) rozwiązuje się w następujący sposób.

1) Upewniwszy się, że (a,m) = d, d> 1 i b:d, dzielimy obie części w porównaniach (2) przez d i otrzymujemy porównanie pomocnicze a 1 x≡b 1 (mod m 1) , Gdzie . Porównanie ma tylko jedno rozwiązanie. Niech klasa c będzie rozwiązaniem.

2) Zapisz odpowiedź x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1) m 1 (mod m).

Dowód. Porównanie pomocnicze zgodnie z Twierdzeniem 2(3) jest równoważne porównaniu pierwotnemu (2). Ponieważ ( 1, Zatem porównanie pomocnicze ma jednoznaczne rozwiązanie - klasa modulo m 1 = . Niech rozwiązaniem będzie x≡c(mod m 1). Klasa liczb c modulo m 1 dzieli się na d klasy modulo m: .

Rzeczywiście, każda liczba z klasy x0 modulo m 1 ma postać x 0 + m 1 t. Podziel t z resztą przez d: t = dq +r, gdzie 0≤r

Zatem porównanie (1) ma d rozwiązań modulo m: x0, x0+m1,..., x0 +(d-1)m1 (linie poziome na górze)

Przykłady.

1) 20x≡ 15 (mod 108). Ponieważ (20,108) = 4 i 15 nie jest podzielne przez 4, nie ma rozwiązań.

2) 20x≡ 44 (mod 108). (20,108) = 4 i 44:4, zatem porównanie ma cztery rozwiązania. Dzieląc obie części i moduł przez 4, otrzymujemy:

5х≡11 (mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Wtedy x≡13 + 27r(mod 108), gdzie r = 0,1,2,3. ja jj

Odpowiedź: x≡13(modl08); x ≡ 40(modl08); x ≡ 67(modl08); x≡94(modl08).

Zastosowanie teorii porównań do rozwiązywania równań niepewnych

Rozważmy nieokreślone lub, jak to się nazywa, równanie diofantyczne pierwszego stopnia z dwiema niewiadomymi ax + by = c, gdzie a, b, c € Z. Musisz rozwiązać to równanie w liczbach całkowitych. Jeżeli (a,b)=d i c nie jest podzielne przez d, to oczywiste jest, że porównanie nie ma rozwiązań w liczbach całkowitych. Jeśli c jest podzielne przez d, to podziel obie strony równania przez d. Wystarczy zatem rozważyć przypadek, gdy (a, b) =1.

Ponieważ ax różni się od c wielokrotnością b, to ax ≡ c(mod b) (bez utraty ogólności możemy założyć, że b > 0). Rozwiązując to porównanie, otrzymujemy x ≡x1 (mod b) lub x=x1+bt, gdzie t€Z. Aby określić odpowiednie wartości y, mamy równanie a(x1 + bt) + by = c, z którego

Co więcej, - jest liczbą całkowitą, jest to cząstkowa wartość nieznanego y, odpowiadająca x1 (okazuje się, podobnie jak x1, w t = 0). Ogólne rozwiązanie równania będzie miało postać układu równań x=x1+bt, y=y1-at, gdzie t jest dowolną liczbą całkowitą.

Notatkaże 1) równanie ax + by = c można rozwiązać zaczynając od porównania przez ≡ c(mod a), ponieważ by różni się od c o wielokrotność a;

2) wygodniej jest wybrać jako moduł najmniejszy moduł a i b.

Przykład, 50x – 42 lata= 34.

Podziel obie strony równania przez 2.

25x ≡ 17(mod2l); 4x ≡ 17 (mod 21) lub 4x ≡ 17-21 ≡ -4 (mod 21).

x ≡ -1 (mod 21), czyli x=-1+21t, t€Z. Podstawmy znaleziony x do równania. 25(-1 + 21t)- 21lat= 17; 21у =-42 + 25* 21t i у =-2 + 25t.