Rozwiązywanie porównań pierwszego stopnia. Rozwiązywanie kongruencji i ich zastosowania. Podzielność i porównania modulo

Treść.

Wstęp

§1. Porównanie modulo

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

1. Właściwości porównania niezależnego od modułu
2. Właściwości porównawcze specyficzne dla modułu

§3. System odliczeń

1. Kompletny system odliczeń
2. Zredukowany 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 podejmowaniem decyzji o porównaniach

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. Metoda ułamków ciągłych

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

§4. Podział porównań potęg wyższych

§5. Pierwiastki pierwotne i indeksy

1. Nakaz klasy odliczeń
2. Pierwiastki pierwotne modulo prim
3. Indeksy modulo prim

Rozdział 3 Zastosowanie teorii porównań

§1. Znaki podzielności

§2. Sprawdzanie wyników operacji arytmetycznych

§3. Zamiana ułamka zwykłego na skończony

Ułamek dziesiętny

Wniosek

Literatura

Wstęp

W naszym życiu często mamy do czynienia z liczbami całkowitymi i zadaniami z nimi związanymi. W niniejszej pracy zajmuję się teorią porównywania liczb całkowitych.

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

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

Stwierdzenie „a jest przystające do b modulo m” jest zwykle zapisywane jako ab (mod m) i nazywa się porównaniem.

Definicja porównania została sformułowana w książce K. Gaussa „Arithmetic Research”. Dzieło to, napisane po łacinie, zaczęto drukować w 1797 r., Ale książka została opublikowana dopiero w 1801 r. Ze względu na fakt, że proces drukowania w tym czasie był niezwykle pracochłonny i długotrwały. Pierwsza część książki Gaussa nosi tytuł „O ogólnym porównaniu liczb”.

Porównania są bardzo wygodne w użyciu w przypadkach, gdy wystarczy znać liczby w dowolnych badaniach do wielokrotności określonej liczby.

Na przykład, jeśli interesuje nas, jaką cyfrą kończy się sześcian liczby całkowitej, to wystarczy, że znamy a tylko do wielokrotności 10 i możemy korzystać z porównań modulo 10.

Celem tej pracy jest rozważenie teorii porównań i zbadanie głównych 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, z których każdy podzielony jest na paragrafy, a paragrafy na paragrafy.

Pierwszy rozdział dotyczy ogólnych zagadnień teorii porównań. Rozważymy tu pojęcie porównania modulo, własności porównań, zupełny i zredukowany system reszt, funkcję Eulera, twierdzenie Eulera i Fermata.

Drugi rozdział poświęcony jest teorii porównań z nieznanym. Przedstawia podstawowe pojęcia związane z rozwiązywaniem porównań, rozważa metody rozwiązywania porównań pierwszego stopnia (metoda selekcji, metoda Eulera, metoda algorytmu Euklidesa, metoda ułamków ciągłych, z wykorzystaniem indeksów), systemy porównań pierwszego stopnia z jedną niewiadomą , porównania wyższych stopni itp. .

Rozdział trzeci zawiera kilka zastosowań teorii liczb w matematyce szkolnej. Uwzględniane są znaki podzielności, weryfikacja wyników działań, 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-pierścień liczb całkowitych, m-stała liczba całkowita i m z-zbiór wszystkich liczb całkowitych podzielnych przez m.

Definicja 1. Mówimy, że dwie liczby całkowite aib są przystające modulo m, jeśli m dzieli a-b.

Jeśli liczby a i b są porównywalne modulo m, to napisz a b (mod m).

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

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

Definiujemy, że relacja porównywalności modulo m pokrywa się z relacją porównywalności modulo (-m) (podzielność przez m jest równoważna 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 aib są porównywalne modulo m wtedy i tylko wtedy, gdy aib mają taką samą resztę z dzielenia przez m.

Dowód.

Niech reszty z dzielenia a i b przez m będą równe, to znaczy 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 b (mod m).

I odwrotnie, niech a b (mod m). To oznacza a-b m lub a-b=mt, t z (3)

Podziel b przez m; otrzymamy b=mq+r w (3), będziemy mieli a=m(q+t)+r, czyli dzielenie a przez m daje taką samą resztę jak dzielenie 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 dają taką samą resztę z dzielenia przez m, nazywamy równoodległymi lub porównywalnymi modulo m.

Przykłady.

Mamy: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) jest podzielne przez m => nasze porównanie jest poprawne.

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

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

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

gcd(4,10) = 2, gcd(25,10) = 5, więc nasze porównanie jest błędne.

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

1. Właściwości porównania niezależne od modułów.

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 jest porównywalny do siebie modulo m);

C) 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). Dlatego 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), a następnie (-1) +1 0 (mod 13), czyli pozostała część podziału o 13 to 0.

a-c b-d (mod m).

Dowód.

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

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

Dowód.

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

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

a c d (mod m).

Dowód.

Warunkowo a-b є mz, c-d є mz. Stąd a c-b d = (a c - b c)+(b c- b d)=(a-b) c+b (c-d) є mz, tj. a c d (mod m).

Konsekwencja. Obie części 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ą, więc a s b s (mod m).

Przykłady.

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

2-1 (moda 3)

5 -1 (mod 3), więc

- 1-1 0 (mod 13)

Odpowiedź: żądana reszta wynosi zero, a A jest podzielne przez 3.

Rozwiązanie:

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

1+ =1+ 1+ =

Ponieważ 27 to 1 (mod 13), wynika z tego, że 1+ 1+1 3+1 9 (mod 13).

htd

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

Mamy: 1 (mod 24), więc

1 (mod 24)

Dodając 55 do obu części porównania, otrzymujemy:

(mod 24).

Mamy: (mod 24), więc

(mod 24) dla dowolnego k є N.

Stąd (mod 24). Od (-8)16 (mod 24), pożądana reszta to 16.

1. Obie części 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ę po podzieleniu 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 części porównania i moduł można pomnożyć przez tę samą dodatnią liczbę całkowitą.

Dowód.

Niech a b (mod m ) i c jest dodatnią liczbą całkowitą. Wtedy a-b = mt i ac-bc=mtc, czyli ac pne (mod mc).

Przykład.

Sprawdź, czy wartość wyrażenia to cały numer.

Rozwiązanie:

Przedstawmy ułamki w postaci porównań: 4(moda 3)

1 (moda 9)

31 (mod 27)

Dodajemy te porównania termin po terminie (właściwość 2), otrzymujemy 124(mod 27) Widzimy, że 124 nie jest liczbą całkowitą podzielną przez 27, stąd wartość wyrażeniarównież nie jest liczbą całkowitą.

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

Dowód.

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

Przykład.

60 9 (mod 17), po podzieleniu obu części porównania przez 3 otrzymujemy:

20 (mod 17).

Ogólnie rzecz biorąc, nie można podzielić obu części porównania przez liczbę, która nie jest względnie pierwsza z modułem, ponieważ po dzieleniu można otrzymać liczby, które w tym module są nieporównywalne.

Przykład.

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

1. Obie części porównania i moduł można podzielić przez ich wspólny dzielnik.

Dowód.

Jeśli ka kb (mod km), to k (a-b) jest podzielne przez km. Dlatego a-b jest podzielne przez m, to znaczy 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żenie obu części każdego z wynikowych n + 1 porównań przez c n-k , otrzymujemy:

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

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

(mod m). Zatem w kongruencji modulo m poszczególne terminy i czynniki można zastąpić liczbami przystającymi modulo m.

Jednocześnie należy zwrócić uwagę na to, że napotkanych w porównaniach wykładników nie da się zastąpić w ten sposób: od

a n c(mod m) i n k(mod m) nie implikuje, że a k z (mod m).

Właściwość 11 ma wiele ważnych zastosowań. W szczególności może służyć do teoretycznego uzasadnienia znaków podzielności. Dla ilustracji, jako przykład, podamy wyprowadzenie testu podzielności przez 3.

Przykład.

Dowolną 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+za n . Ponieważ

10 1 (mod 3), a 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), tj. 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. Kompletny system rozliczeniowy.

Liczby równoodległe, czyli, co na jedno wychodzi, porównywalne modulo m, tworzą klasę liczb modulo m.

Z definicji tej wynika, że ​​ta sama reszta r odpowiada wszystkim liczbom klasy, a wszystkie liczby tej klasy otrzymamy, jeśli zmusimy q do przejścia przez wszystkie liczby całkowite w postaci mq + r.

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

Dowolna liczba klasy nazywana jest resztą modulo m w odniesieniu do wszystkich liczb tej samej klasy. Resztę otrzymaną przy q=0, równą reszcie r, nazywamy najmniejszą resztą nieujemną.

Reszta ρ, najmniejsza pod względem wartości bezwzględnej, nazywana jest resztą absolutnie najmniejszą.

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

Wybieramy z każdej klasy reszt modulo T po jednym numerze. Dostawać m liczby całkowite: x 1 ,…, x m . Zbiór (x 1, ..., x t) nazywamy kompletny system reszt modulo m.

Ponieważ każda klasa zawiera nieprzeliczalny zbiór reszt, możliwe jest skomponowanie nieprzeliczalnego zbioru różnych kompletnych układów reszt modulo m, z których każdy zawiera odliczenia.

Przykład.

Skomponuj kilka kompletnych układów reszt modulo T = 5. Mamy klasy: 0, 1, 2, 3, 4.

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

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

Zróbmy 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.

Najbardziej używane:

1. Kompletny system najmniejszych reszt nieujemnych: 0, 1, t -1 W powyższym przykładzie: 0, 1, 2, 3, 4. Taki układ reszt jest prosty: należy wypisać wszystkie nieujemne reszty z dzielenia przez m.
2. Kompletny system najmniej dodatnich reszt(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 najmniejszych pozostałości.W przypadku m nieparzystych bezwzględnie najmniejsze reszty pojawiają się obok siebie.

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

aw 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 główne właściwości kompletnego systemu reszt.

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

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

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

Dowód.

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

x 1, x 2,…, x t jest kompletnym systemem reszt modulo m.

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

Dowód.

Rozważać

topór 1 + b, topór 2 + b, ..., topór m + b (2)

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

Rzeczywiście, gdyby w (2) były dwie liczby takie, że

topór i + b topór j + b (mod m), (i = j), wtedy otrzymalibyśmy topór i topór j (mod m). 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 m) dla (i = j) , ponieważ x 1 ,x 2 , ..., x m - pełny system odliczeń.

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

Więc topór 1 + b, topór 2 + b, ..., topór m + b to kompletny system reszt modulo m.

Przykład.

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

Weźmy pełny układ reszt modulo 10, na przykład: 0, 1, 2, ..., 9. Skomponujmy liczby postaci topór + b. Otrzymujemy: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Otrzymany zbiór liczb jest kompletnym układem reszt modulo 10.

1. Dany system odliczeń.

Udowodnijmy następujące twierdzenie.

Twierdzenie 1.

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

Dowód.

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

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

I odwrotnie, jeśli m δ i b δ, to a = b + mt jest podzielna przez δ, a zatem 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 dowolną liczbę a z tej klasy odliczeń za T zwany największym wspólnym dzielnikiem T i tej klasy pozostałości.

Definicja 2. Klasa pozostałości a modulo m nazywa się względnie pierwszą z modulo M jeśli jest największym wspólnym dzielnikiem 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. Reszta klasy 2 składa się z liczb (..., -10, -4, 2, 8, 14, ...). Największym wspólnym dzielnikiem dowolnej z tych liczb i modułu 6 jest 2. Zatem (2, 6) = 2. Największym wspólnym dzielnikiem dowolnej liczby z klasy 5 i modułu 6 jest 1. Zatem klasa 5 jest względnie pierwsza do modułu 6.

Wybierzmy z każdej klasy reszt względnie pierwszych z modulo m jedną liczbą. Otrzymujemy system odliczeń, który jest częścią pełnego systemu odliczeń. Nazywają jązredukowany układ reszt modulo m.

Definicja 3. Zbiór reszt modulo m, pobierany pojedynczo z każdej względnie pierwszej z T klasa reszt modulo moduł ten nazywany jest systemem reszt zredukowanych.

Definicja 3 implikuje metodę otrzymywania zredukowanego układu reszt modulo T: konieczne jest napisanie pełnego układu reszt i usunięcie z niego wszystkich reszt, które nie są względnie pierwsze z m. Pozostały zestaw odliczeń to zredukowany system odliczeń. Istnieje oczywiście nieskończona liczba zredukowanych układów reszt modulo m.

Jeżeli jako początkowy przyjmiemy kompletny układ najmniej nieujemnych lub absolutnie najmniejszych reszt, to we wskazany sposób otrzymamy odpowiednio zredukowany układ najmniejszych nieujemnych lub absolutnie najmniejszych reszt modulo m.

Przykład.

jeśli T = 8, następnie 1, 3, 5, 7 - zredukowany układ najmniejszych reszt nieujemnych, 1, 3, -3, -1- zredukowany system absolutnie najmniejszych pozostałości.

Twierdzenie 2.

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

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

Dowód

A) Każda liczba w zbiorze (1) należy do jakiejś klasy.

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

Dlatego zestaw liczb(1) - zredukowany układ reszt modulo T.

§4. Funkcja Eulera.

Twierdzenia Eulera i Fermata.

1. Funkcja Eulera.

Oznacz przez φ(T) liczba klas reszt modulo m względnie pierwsza z m, czyli liczba elementów zredukowanego układu reszt modulo t. Funkcja φ (t) jest numeryczny. Nazywają jąFunkcja Eulera.

Wybieramy jako przedstawicieli klas reszt modulo t liczby 1, ... , t - 1, t. Wtedy φ (t) jest liczbą takich liczb względnie pierwszych t. Innymi słowy, φ (t) - liczba liczb dodatnich nieprzekraczająca m i względnie pierwsza do m.

Przykłady.

1. niech t = 9. Kompletny system 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 od 9. Skoro więc liczba tych liczb wynosi 6, to φ (9) = 6.
2. Niech t = 12. Cały system 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 od 12. Dlatego

φ(12) = 4.

o godz = 1, cały system reszt składa się z jednej klasy 1. Wspólnym naturalnym dzielnikiem liczb 1 i 1 jest 1, (1, 1) = 1. Na tej podstawie stawiamy φ(1) = 1.

Przejdźmy do obliczenia funkcji Eulera.

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

Dowód.

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

2) Jeśli m = pk - potęga liczby pierwszej p., więc

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

Dowód.

Kompletny system reszt modulo t = pk składa się z cyfr 1,..., p k - 1, p k naturalne dzielniki T są stopnie R. Dlatego liczba Amoże mieć wspólny dzielnik z m inny niż 1, tylko kiedyApodzielony przezR.Ale wśród liczb 1, ... , Pk -1 NARdzieląc tylko liczbyp, 2p, ..., str2 , ... RDo, których liczba jestRDo: p = strk-1. Dlatego porównaj zt = strDoodpoczynekRDo- Rk-1= strkl(p-1)liczby. Udowodniono zatem, że

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

Twierdzenie1.

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

Dowód.

Pierwszy warunek definicji funkcji multiplikatywnej jest spełniony w trywialny sposób: funkcja Eulera jest zdefiniowana dla wszystkich liczb naturalnych, a φ (1) = 1. Musimy tylko pokazać, że jeślitypwzględnie pierwsze liczby

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

Ułóż cały system reszt modulotpJakPXT -macierze

1 2 T

t+1 t+2 2t

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

(P -1) t+1 (P -1) m +2 pt

PonieważTIPwzględnie pierwsza, a następnie liczbaXwzajemnie proste ztpwtedy i tylko wtedy gdyXwzajemnie proste zTIXwzajemnie proste zP. Ale numerkm + twzajemnie proste zTwtedy i tylko wtedy gdyTwzajemnie proste zT.Dlatego liczby względnie pierwsze do m znajdują się w tych kolumnach, dla którychTprzebiega przez zredukowany system reszt moduloT.Liczba takich kolumn to φ(T).Każda kolumna przedstawia kompletny system reszt moduloP.Z tych reszt φ(P)względnie pierwsze zP.Stąd całkowita liczba liczb względnie pierwszych izTa przy n równa się φ(T)φ(rzecz)

(φ (T)kolumny, z których każda zajmuje φ(P)liczby). Te liczby i tylko one są względnie pierwszeitp.Udowodniono zatem, że

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

Przykłady.

№1 . Udowodnij następujące 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 mnożnik(m) mamy:

(m)=.

Ale zgodnie ze wzorem (1) otrzymujemy to

-1), a zatem

(3)

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

Ponieważ= m, zatem(4)

Formuła (3) lub, co jest tożsame, (4) jest pożądana.

Przykłady.

№1 . Jaka jest kwota

Rozwiązanie:,

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

№2 . Opierając się na własnościach funkcji liczbowej Eulera, udowodnij, że istnieje nieskończony zbiór liczb pierwszych w ciągu liczb naturalnych.

Rozwiązanie:Załóżmy, że spłaszczamy liczbę liczb pierwszych skończonym zbioremjest największą liczbą pierwszą i niech a=jest iloczynem wszystkich liczb pierwszych, opartym na jednej z właściwości funkcji liczby 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, a zatem 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 pod warunkiem=2.

Ekspres od=2 , dostajemy, wstawmy

:

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

Wtedy x=, x=11 13=143.

Odpowiedź:x= 143

2. Twierdzenie Eulera i Fermat.

W teorii porównań ważną rolę odgrywa twierdzenie Eulera.

Twierdzenie Eulera.

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

(1)

Dowód.Pozwalać

(2)

jest zredukowanym układem reszt modulo m.

JeśliAjest więc liczbą całkowitą względnie pierwszą do m

(3)

W n dają taką samą resztę.

Równoważne sformułowania: aib porównywalne modulo n jeśli ich różnica A - B jest podzielna przez n lub jeśli a można przedstawić jako A = B + kN , Gdzie k jest pewną liczbą całkowitą. Na przykład: 32 i −10 są przystające modulo 7, ponieważ

Stwierdzenie „a i b są przystające modulo n” jest zapisane jako:

Właściwości równości modulo

Relacja porównania modulo ma właściwości

Dowolne dwie liczby całkowite A I B są porównywalne modulo 1.

W kolejności numerów A I B były porównywalne modulo N, konieczne i wystarczające jest, aby ich różnica była podzielna przez N.

Jeśli liczby i są porównywalne parami modulo N, to ich sumy i , a także iloczyny i są również porównywalne modulo N.

Jeśli liczby A I B porównywalne modulo N, a następnie ich stopnie naukowe A k I B k są również porównywalne modulo N dla każdego naturalnego k.

Jeśli liczby A I B porównywalne modulo N, I N podzielony przez M, To A I B porównywalne modulo M.

W kolejności numerów A I B były porównywalne modulo N, reprezentowany jako jego kanoniczny rozkład na czynniki pierwsze P I

konieczne i wystarczające do

Relacja porównania jest relacją równoważności i ma wiele właściwości zwykłych równości. Na przykład można je dodawać i mnożyć: if

Porównania jednak, ogólnie rzecz biorąc, nie mogą być dzielone przez siebie lub przez inne liczby. Przykład: jednak zmniejszając o 2 otrzymujemy błędne porównanie: . Reguły redukcji dla porównań są następujące.

Nie można również wykonywać operacji na porównaniach, jeśli ich moduły nie są zgodne.

Inne właściwości:

Powiązane definicje

Klasy dedukcji

Zbiór wszystkich liczb porównywalnych do A modulo N zwany klasa odliczeń A modulo N i jest zwykle oznaczane przez [ A] N Lub . Zatem porównanie jest równoważne z równością klas reszt [A] N = [B] N .

Ponieważ porównanie modulo N jest relacją równoważności na zbiorze liczb całkowitych, a następnie klasami reszt modulo N są klasami równoważności; ich liczba to N. Zbiór wszystkich klas reszt modulo N oznaczony przez lub .

Operacje dodawania i mnożenia na indukują odpowiednie operacje na zbiorze:

[A] N + [B] N = [A + B] N

W odniesieniu do tych operacji zbiór jest skończonym pierścieniem i jeśli N proste - końcowe pole .

Systemy odliczeń

System reszt umożliwia wykonywanie operacji arytmetycznych na skończonym zbiorze liczb bez wychodzenia poza niego. Kompletny system odliczeń modulo n to dowolny zbiór n liczb całkowitych, które są nieporównywalne modulo n. Zwykle jako kompletny system reszt modulo n przyjmuje się najmniejsze reszty nieujemne

0,1,...,N − 1

lub absolutnie najmniejsze reszty składające się z liczb

,

w przypadku nieparzystego N i liczby

w przypadku parzystego N .

Decyzja porównawcza

Porównania pierwszego stopnia

W teorii liczb, kryptografii i innych dziedzinach nauki często pojawia się problem znalezienia rozwiązań dla porównania pierwszego stopnia postaci:

Rozwiązanie takiego porównania zaczyna się od obliczenia gcd (a, m)=d. W takim przypadku możliwe są 2 przypadki:

• Jeśli B nie wielokrotność D, to porównanie nie ma rozwiązań.
• Jeśli B wiele D, to porównanie ma unikalne rozwiązanie modulo M / D lub, co jest tym samym, D rozwiązania modulo M. W tym przypadku w wyniku pomniejszenia pierwotnego porównania o D wyniki porównania:

Gdzie A 1 = A / D , B 1 = B / D I M 1 = M / D są liczbami całkowitymi i A 1 i M 1 są względnie pierwsze. Dlatego liczba A 1 można odwrócić modulo M 1 , czyli znaleźć taką liczbę Cże (innymi słowy ). Teraz rozwiązanie można znaleźć, mnożąc wynikowe porównanie przez C:

Kalkulacja wartości praktycznej C można to zrobić na różne sposoby: za pomocą twierdzenia Eulera, algorytmu Euklidesa, teorii ułamków ciągłych (patrz algorytm) itp. W szczególności twierdzenie Eulera pozwala zapisać wartość C Jak:

Przykład

Dla porównania mamy D= 2 , więc modulo 22 porównanie ma dwa rozwiązania. Zamieńmy 26 na 4, co jest porównywalnym modulo 22, a następnie anulujmy wszystkie 3 liczby przez 2:

Ponieważ 2 jest względnie pierwsze z modulo 11, możemy zmniejszyć lewy i prawy bok o 2. W rezultacie otrzymujemy jedno rozwiązanie modulo 11: , co odpowiada dwóm rozwiązaniom modulo 22: .

Porównania drugiego stopnia

Rozwiązywanie porównań drugiego stopnia sprowadza się do ustalenia, czy dana liczba jest resztą kwadratową (stosując kwadratowe prawo wzajemności), a następnie obliczenia pierwiastka kwadratowego modulo this.

Fabuła

Chińskie twierdzenie o resztach, znane od wielu stuleci, stwierdza (we współczesnym języku matematycznym), że reszta pierścieniowa modulo iloczynu kilku liczb względnie pierwszych wynosi

Rozważ porównanie formy X 2 ≡A(mod P a), gdzie P jest prostą liczbą nieparzystą. Jak pokazano w sekcji 4 §4, rozwiązanie tej kongruencji można znaleźć, rozwiązując kongruencję X 2 ≡A(mod P). I porównanie X 2 ≡A(mod Pα) będzie miał dwa rozwiązania, jeśli A jest kwadratową resztą modulo P.

Przykład:

Rozwiąż porównanie kwadratowe X 2 ≡86 (mod 125).

125 = 5 3 , 5 jest liczbą pierwszą. Sprawdźmy, czy 86 jest kwadratem modulo 5.

Oryginalne porównanie zawiera 2 rozwiązania.

Znajdźmy rozwiązanie porównawcze X 2 ≡86 (mod 5).

X 2 ≡1 (mod 5).

To porównanie można rozwiązać w sposób wskazany w poprzednim akapicie, ale wykorzystamy fakt, że pierwiastek kwadratowy z 1 modulo wynosi ±1, a porównanie ma dokładnie dwa rozwiązania. Zatem rozwiązaniem kongruencji modulo 5 jest

X≡ ± 1 (mod 5) lub inaczej X=±(1+5 T 1).

Podstaw wynikowe rozwiązanie w porównaniu modulo 5 2 =25:

X 2 ≡86 (mod 25)

X 2 ≡11 (mod 25)

(1+5T 1) 2 ≡11 (mod 25)

1+10T 1 +25T 1 2 ≡11 (mod 25)

10T 1 ≡10 (mod 25)

2T 1 ≡2 (mod 5)

T 1 ≡1 (mod 5) lub równoważnie, T 1 =1+5T 2 .

Wtedy rozwiązaniem kongruencji modulo 25 jest X=±(1+5(1+5 T 2))=±(6+25 T 2). Podstaw wynikowe rozwiązanie w porównaniu modulo 5 3 =125:

X 2 ≡86 (mod 125)

(6+25T 2) 2 ≡86 (mod 125)

36+12 25 T 2 +625T 2 2 ≡86 (mod 125)

12 25 T 2 ≡50 (mod 125)

12T 2 ≡2 (mod 5)

2T 2 ≡2 (mod 5)

T 2 ≡1 (mod 5), lub T 2 =1+5T 3 .

Wtedy rozwiązaniem porównania modulo 125 jest X=±(6+25(1+5 T 3))=±(31+125 T 3).

Odpowiedź: X≡ ± 31 (mod 125).

Rozważmy teraz porównanie formy X 2 ≡A(mod2α). Takie porównanie nie zawsze ma dwa rozwiązania. Dla takiego modułu możliwe są następujące przypadki:

1) α=1. Wtedy porównanie ma rozwiązanie tylko wtedy, gdy A≡1 (mod 2), a rozwiązaniem jest X≡1 (mod 2) (jedno rozwiązanie).

2) α=2. Porównanie ma rozwiązania tylko wtedy, gdy A≡1 (mod 4), a rozwiązaniem jest X≡ ± 1 (mod 4) (dwa rozwiązania).

3) α≥3. Porównanie ma rozwiązania tylko wtedy, gdy A≡1(mod 8) i będą cztery takie rozwiązania. Porównanie X 2 ≡A(mod 2 α) dla α≥3 rozwiązuje się w taki sam sposób jak porównania postaci X 2 ≡A(mod Pα), tylko rozwiązania modulo 8 działają jako rozwiązanie początkowe: X≡ ± 1 (mod 8) i X≡ ± 3 (mod 8). Należy je porównać modulo 16, następnie modulo 32 i tak dalej, aż do modulo 2 α .

Przykład:

Rozwiąż porównanie X 2 ≡33 (mod 64)

64=26. Sprawdźmy, czy oryginalne porównanie ma rozwiązanie. 33≡1(mod 8), więc porównanie ma 4 rozwiązania.

Modulo 8 tymi rozwiązaniami będą: X≡ ± 1 (mod 8) i X≡ ± 3 (mod 8), co można przedstawić jako X=±(1+4 T 1). Zastąp to wyrażenie w porównaniu modulo 16

X 2 ≡33 (mod 16)

(1+4T 1) 2 ≡1 (mod 16)

1+8T 1 +16T 1 2 ≡1 (mod 16)

8T 1 ≡0 (mod 16)

T 1 ≡0 (mod 2)

Wtedy rozwiązanie przybierze formę X=±(1+4 T 1)=±(1+4(0+2 T 2))=±(1+8 T 2). Zastąp otrzymane rozwiązanie modulo kongruencji 32:

X 2 ≡33 (mod 32)

(1+8T 2) 2 ≡1 (mod 32)

1+16T 2 +64T 2 2 ≡1 (mod 32)

16T 2 ≡0 (mod 32)

T 2 ≡0 (mod 2)

Wtedy rozwiązanie przybierze formę X=±(1+8 T 2) =±(1+8(0+2t 3)) =±(1+16 T 3). Podstaw wynikowe rozwiązanie w porównaniu modulo 64:

X 2 ≡33 (mod 64)

(1+16T 3) 2 ≡33 (mod 64)

1+32T 3 +256T 3 2 ≡33 (mod 64)

32T 3 ≡32 (mod 64)

T 3 ≡1 (mod 2)

Wtedy rozwiązanie przybierze formę X=±(1+16 T 3) =±(1+16(1+2t 4)) =±(17+32 T 4). Tak więc, modulo 64, oryginalne porównanie ma cztery rozwiązania: X≡ ± 17 (mod 64) i X≡ ± 49 (mod 64).

Rozważmy teraz ogólne porównanie: X 2 ≡A(mod M), (A,M)=1, - kanoniczna dekompozycja modułu M. Zgodnie z Twierdzeniem z punktu 4 §4 porównanie to jest równoważne systemowi

Jeśli każde porównanie tego systemu jest rozstrzygalne, to cały system jest rozstrzygalny. Po znalezieniu rozwiązania każdego porównania tego układu otrzymujemy układ porównań pierwszego stopnia, rozwiązując go, korzystając z chińskiego twierdzenia o resztach, otrzymujemy rozwiązanie porównania pierwotnego. Co więcej, liczba różnych rozwiązań oryginalnego porównania (jeśli jest rozwiązywalne) wynosi 2 k, jeśli α=1, 2 k+1 jeśli α=2, 2 k+2 jeśli α≥3.

Przykład:

Rozwiąż porównanie X 2 ≡4 (mod 21).

Porównanie z jedną niewiadomą X ma formę

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

Decyzja 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ń to porównanie spełni wszystkie liczby całkowite porównywalne z X 0 modulo M. Dlatego wszystkie rozwiązania porównawcze należą do tej samej klasy reszt modulo T, rozważymy jako jedno rozwiązanie. Zatem porównanie ma tyle rozwiązań, ile jest elementów pełnego systemu reszt, które je spełniają.

Nazywamy porównania, których zestawy rozwiązań są takie same równowartość.

2.2.1 Porównania pierwszego stopnia

Porównanie pierwszego stopnia z jedną niewiadomą X ma formę

(2.2)

Twierdzenie 2.4. Aby porównanie miało co najmniej jedno rozwiązanie, konieczna i wystarczająca jest liczba B podzielone przez NWD( 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 liczba całkowita Q, Co Oh 0 − B = qm. Stąd B= ach 0 − qm. I od D, jako wspólny dzielnik dzieli liczby A I T, następnie odliczanie i odejmowanie są dzielone przez D, i stąd 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, zgodnie z definicją podzielności, istnieją liczby całkowite A 1 , B 1 ,T 1 , Co .

Korzystając z rozszerzonego algorytmu Euclida, znajdujemy liniową reprezentację liczby 1 = gcd( A 1 , M 1 ):

dla niektórych X 0 , y 0 . Mnożymy obie części ostatniej równości przez B 1 D:

lub, co jest tym samym,

,

czyli , 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 kongruencja (2.2) będzie rozstrzygalna i D = NWD( A, M). Wtedy zbiór rozwiązań porównania (2.2) składa się z D klasy reszt modulo T, mianowicie, jeśli X 0 jest jednym z rozwiązań, to wszystkie inne rozwiązania są

Dowód. Pozwalać X 0 jest rozwiązaniem porównania (2.2), tj. I , . Więc jest taki Q, Co Oh 0 − B = qm. Podstawiając teraz 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 to: X 0 \u003d 2, x 0 + 4 \u003d 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żmy, jak rozwiązać porównanie pierwszego stopnia. Bez utraty ogólności założymy, że NWD( A, t) = 1. Wtedy rozwiązania kongruencji (2.2) można szukać np. za pomocą algorytmu Euklidesa. Rzeczywiście, używając rozszerzonego algorytmu euklidesowego, przedstawiamy liczbę 1 jako liniową kombinację liczb A I T:

Pomnóż obie strony tego równania przez B, otrzymujemy: B = abq + mrb, Gdzie abq - B = - mrb, to jest A ∙ (bq) = B(mod M) I bq jest rozwiązaniem porównania (2.2).

Innym sposobem rozwiązania jest użycie twierdzenia Eulera. Ponownie zakładamy, że NWD(a, T)= 1. Stosujemy twierdzenie Eulera: . Pomnóż obie strony porównania przez B: . Przepisanie ostatniego wyrażenia jako , otrzymujemy, że jest to rozwiązanie kongruencji (2.2).

Niech teraz NWD( A, M) = D>1. Następnie A = ATD, M = MTD, gdzie gcd( 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, bo NWD( A 1 , M 1) = 1, zatem X 0 będzie decyzja i porównanie A 1 xdd = baza danych 1 (mod M 1), czyli oryginalne porównanie (2.2). Odpoczynek D- 1 rozwiązania znajdują się na podstawie Twierdzenia 2.5.

Porównywanie liczb modulo

Projekt przygotowała: Irina Zutikova

MAOU „Liceum nr 6”

Klasa: 10 "a"

Doradca naukowy: Zheltova Olga Nikolaevna

Tambow

2016

• Problem
• Cel projektu
• Hipoteza
• Cele projektu i plan ich osiągnięcia
• Porównania i ich właściwości
• Przykładowe zadania i ich rozwiązania
• Wykorzystane strony i literatura

Problem:

Większość uczniów rzadko używa porównania modulo liczb do rozwiązywania zadań niestandardowych i olimpiad.

Cel projektu:

Pokaż, jak porównując liczby modulo, możesz rozwiązywać zadania niestandardowe i olimpijskie.

Hipoteza:

Głębsze przestudiowanie tematu „Modulo porównania liczb” pomoże uczniom rozwiązać niektóre zadania niestandardowe i olimpijskie.

Cele projektu i plan ich osiągnięcia:

1. Przestudiuj szczegółowo temat „Porównanie liczb modulo”.

2. Rozwiąż kilka zadań niestandardowych i olimpiadowych, używając modulo porównania liczb.

3. Utwórz notatkę dla uczniów na temat „Porównanie liczb modulo”.

4. Przeprowadź lekcję na temat „Porównanie modulo liczb” w klasie 10 „a”.

5. Zadaj klasie pracę domową na temat „Porównanie modułów”.

6. Porównaj czas wykonania zadania przed i po zapoznaniu się z tematem „Porównanie modułów”.

7. Wyciągnij wnioski.

Zanim zacząłem szczegółowo studiować temat „Porównywanie liczb modulo”, postanowiłem porównać, jak jest on prezentowany w różnych podręcznikach.

• Algebra i początki analizy matematycznej. Głęboki poziom. Klasa 10 (Yu.M. Kolyagin i inni)
• Matematyka: algebra, funkcje, analiza danych. Klasa 7 (LG Peterson i inni)
• Algebra i początki analizy matematycznej. poziom profilu. Klasa 10 (EP Nelin i inni)
• Algebra i początki analizy matematycznej. poziom profilu. Klasa 10 (GK Muravin i inni)

Jak się dowiedziałem, w niektórych podręcznikach temat ten nie jest nawet poruszany, pomimo poziomu pogłębienia. A najbardziej zrozumiały i przystępny temat jest przedstawiony w podręczniku L.G. Petersona (Rozdział: Wprowadzenie do teorii podzielności), więc spróbujmy zrozumieć „Porównanie liczb modulo”, oparte na teorii z tego podręcznika.

Porównania i ich właściwości.

Definicja: Jeśli dwie liczby całkowite aib mają taką samą resztę z dzielenia przez pewną liczbę całkowitą m (m>0), to mówią, żeaib są przystające modulo m, i napisz:

Twierdzenie: wtedy i tylko wtedy, gdy różnica między a i b jest podzielna przez m.

Nieruchomości:

1. Refleksyjność porównań.Każda liczba a jest porównywalna z samą sobą modulo m (m>0; a,m są liczbami całkowitymi).
2. Symetria porównań.Jeśli liczba a jest zgodna z liczbą b modulo m, to liczba b jest zgodna z liczbą a modulo m (m>0; a, b, m są liczbami całkowitymi).
3. Przechodniość porównań.Jeśli liczba a jest przystająca do b modulo m, a b jest przystająca do c modulo m, to a jest przystająca do c modulo m(m>0; a,b,c,m są liczbami całkowitymi).
4. Jeśli liczba a jest przystająca do liczby b modulo m, to liczba a N porównywalna z liczbą b N modulo m(m>0; a,b,m to liczby całkowite; n to liczba naturalna).

Przykładowe zadania i ich rozwiązania.

1. Znajdź ostatnią cyfrę liczby 3 999 .

Rozwiązanie:

Ponieważ ostatnia cyfra liczby jest zatem resztą z dzielenia przez 10

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7 (mod 10)

(Ponieważ 34=81 1 (mod 10); 81 n 1 (mod10) (według właściwości))

Odpowiedź: 7.

2. Udowodnij, że 2 4n -1 dzieli się przez 15 bez reszty. (Phystech2012)

Rozwiązanie:

Ponieważ 16 1 (mod 15), zatem

16n-1 0 (mod 15) (według właściwości); 16n= (2 4) przyp

2 4n -1 0 (mod 15)

3. Udowodnij, że 12 2n+1 +11n+2 podzielna bez reszty przez 133.

Rozwiązanie:

12 2n+1 =12*144n 12*11n (mod 133) (według właściwości)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Numer (11n *133) dzieli się bez reszty przez 133. Zatem (12 2n+1 +11n+2 ) jest podzielna przez 133 bez reszty.

4. Znajdź resztę z dzielenia przez 15 z liczby 2 2015 .

Rozwiązanie:

Od 16 1 (mod 15), więc

2 2015 8 (mod 15)

Odpowiedź: 8.

5. Znajdź resztę z dzielenia przez 17 z liczby 2 2015 . (Fizyka 2015)

Rozwiązanie:

2 2015 =2 3 *2 2012 =8*16 503

Od 16 -1 (mod 17), więc

2 2015-8 (mod 15)

8 9 (mod 17)

Odpowiedź:9.

6. Udowodnij, że liczba to 11 100 -1 dzieli się przez 100 bez reszty. (Fizyka 2015)

Rozwiązanie:

11 100 =121 50

121 50 21 50 (mod 100) (według właściwości)

21 50 =441 25

441 25 41 25 (mod 100) (według właściwości)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (według właściwości)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100) (według właściwości)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (według właściwości)

41*21 3 =41*21*441

441 41 (mod 100) (według właściwości)

21*41 2 =21*1681

1681 -19 (mod 100) (według właściwości)

21*(-19)=-399

399 1 (mod 100) (według właściwości)

Więc 11 100 1 (mod 100)

11 100 -1 0 (mod 100) (według właściwości)

7. Podano trzy liczby: 1771,1935,2222. Znajdź liczbę, przez którą po podzieleniu reszta z trzech podanych liczb będzie równa. (HSE2016)

Rozwiązanie:

Niech więc nieznana liczba będzie równa a

2222 1935 (mod a); 1935 1771 (moda); 2222 1771 (mod a)

2222-1935 0 (moda) (właściwość); 1935-17710(moda) (według właściwości); 2222-17710 (moda) (według właściwości)

287 0 (mod a); 164 0 (mod a); 451 0 (mod a)

287-164 0(moda) (według właściwości); 451-2870 (moda) (według właściwości)

123 0 (mod a); 164 0 (mod a)

164-123 0 (mod a) (właściwość)

41

Olimpiada BHP 2016