Projekt matematyczny na dany temat

„Porównania modulo”

Zaripova Aisylu

Dzielnica Sowiecka w Kazaniu

MBOU „Szkoła Średnia nr 166”, klasa 7a

Opiekun naukowy: Antonova N.A.

Spis treści

Wprowadzenie__________________________________________________________3

    Co to są porównania______________________________________________4

    1. Pojęcie porównań modulo__________________________4

      Historia powstania koncepcji porównań modulo______4

      Właściwości porównań__________________________________________4

    Stosowanie porównań w rozwiązywaniu problemów____________________________6

    1. Najprostszym zastosowaniem porównań modulo jest określenie podzielności liczb___________________________6

      Jedno zadanie porównawcze______________________________8

      Zastosowanie porównań modulo w działalności zawodowej________________________________________________9

Wniosek____________________________________10

Wykaz wykorzystanej literatury________________________________________11

Wstęp.

Temat: Porównania modulo.

Problem: Wielu uczniów przygotowujących się do olimpiad staje przed problemami, których rozwiązanie opiera się na znajomości reszt z dzielenia liczb całkowitych przez liczbę naturalną. Nas interesowały tego typu problemy i możliwe metody ich rozwiązania. Okazuje się, że można je rozwiązać za pomocą porównań modulo.

Cel: Poznaj istotę porównań modulo, główne metody pracy z porównaniami modulo.

Cele: znaleźć materiał teoretyczny na ten temat, rozważyć problemy rozwiązywane za pomocą porównań modulo, pokazać najczęstsze metody rozwiązywania takich problemów, wyciągnąć wnioski.

Przedmiot studiów: teoria liczb.

Przedmiot badań: teoria porównań modulo.

Praca ma charakter badań teoretycznych i może być wykorzystana w przygotowaniu do olimpiad matematycznych. Jego treść ujawnia podstawowe pojęcia porównań modulo i ich główne właściwości oraz podaje przykłady rozwiązywania problemów na ten temat.

I . Co to są porównania?

    1. Pojęcie porównań modulo.

Liczby i są porównywalne pod względem modułu, jeśli są podzielne przez, innymi słowy, a i b mają takie same reszty przy dzieleniu przez.

Przeznaczenie

Przykłady:

    Liczby 12 i 32 są porównywalne modulo 5, ponieważ 12 przy dzieleniu przez 5 daje resztę 2, a 32 przy dzieleniu przez 2 daje resztę 2. Jest to zapisane12 ;

    101 i 17 są porównywalne modulo 21;

    1. Historia powstania koncepcji porównań modulo.

Teoria podzielności została w dużej mierze stworzona przez Eulera. Definicja porównania została sformułowana w książce K.F. 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”. To Gauss zaproponował symbolikę porównań modulo, która utrwaliła się w matematyce.

    1. Właściwości porównań.

Jeśli

Dowód:

  1. Jeśli dodamy drugą do pierwszej równości, otrzymamy

jest sumą dwóch liczb całkowitych, zatem jest liczbą całkowitą, zatem.

    Jeśli odejmiemy drugą od pierwszej równości, otrzymamy

jest to różnica dwóch liczb całkowitych, co oznacza, że ​​jest to liczba całkowita.

    Rozważ wyrażenie:

Jest to różnica iloczynów liczb całkowitych, co oznacza, że ​​jest to liczba całkowita.

    Jest to konsekwencja trzeciej właściwości porównań.

co było do okazania

5) Jeśli.

Dowód: Znajdźmy sumę tych dwóch wyrażeń:

jest sumą dwóch liczb całkowitych, zatem jest liczbą całkowitą, zatem .

co było do okazania

6) Jeśli jest liczbą całkowitą, to

Dowód: , gdzieP– liczba całkowita, pomnóż tę równość przez, otrzymamy: . Ponieważ jest to iloczyn liczb całkowitych, właśnie to należało udowodnić.

7) Jeśli

Dowód: rozumowanie jest podobne do dowodu własności 6.

8) Jeśli - następnie liczby względnie pierwsze

Dowód: , podziel to wyrażenie przez, otrzymamy: - liczby stosunkowo pierwsze, co oznacza, że ​​są podzielne przez liczbę całkowitą, tj. =. A to oznacza, że ​​trzeba było to udowodnić.

II . Stosowanie porównań do rozwiązywania problemów.

2.1. Najprostszym zastosowaniem porównań modulo jest określenie podzielności liczb.

Przykład. Znajdź resztę 2 2009 w 7.

Rozwiązanie: Rozważmy potęgi liczby 2:

podnosząc porównanie do potęgi 668 i mnożąc przez, otrzymujemy: .

Odpowiedź: 4.

Przykład. Udowodnić, że 7+7 2 +7 3 +…+7 4 N jest podzielna przez 100 dla dowolnegoNze zbioru liczb całkowitych.

Rozwiązanie: rozważ porównania

itp. Cykliczny charakter reszt wyjaśniają zasady mnożenia liczb w kolumnie. Sumując pierwsze cztery porównania, otrzymujemy:

Oznacza to, że kwota ta jest dzielona przez 100 bez reszty. Podobnie, dodając poniższe porównania około czterech, otrzymujemy, że każda taka suma jest podzielna przez 100 bez reszty. Oznacza to, że cała suma składająca się z 4Nwyrazy są podzielne przez 100 bez reszty. co było do okazania

Przykład. Określ przy jakiej wartościNwyrażenie jest podzielne przez 19 bez reszty.

Rozwiązanie: .

Pomnóżmy to porównanie przez 20. Otrzymujemy.

Podsumujmy zatem porównania. . Zatem prawa strona porównania jest zawsze podzielna przez 19 dla dowolnej liczby naturalnejN, co oznacza, że ​​oryginalne wyrażenie jest podzielne przez 19 za pomocą naturalnegoN.

Odpowiedź N – dowolna liczba naturalna.

Przykład. Na jaką cyfrę kończy się liczba?

Rozwiązanie. Aby rozwiązać ten problem, będziemy monitorować tylko ostatnią cyfrę. Rozważ potęgę liczby 14:

Można zauważyć, że jeśli wykładnik jest nieparzysty, wartość stopnia kończy się na 4, a jeśli wykładnik jest parzysty, kończy się na 6. Wtedy kończy się na 6, tj. jest liczbą parzystą. Zatem zakończy się w 6.

Odpowiedź 6.

2.2. Jedno zadanie porównawcze.

Artykuł N. Vilenkina „Porównania i klasy reszt” przedstawia problem, który w latach studenckich rozwiązał słynny angielski fizyk Dirac.

Istnieje również krótkie rozwiązanie tego problemu za pomocą porównań modulo. Jednak napotkaliśmy wiele podobnych problemów. Na przykład.

Jeden z przechodniów znalazł stertę jabłek w pobliżu drzewa, na którym siedziała małpa. Po ich policzeniu zdał sobie sprawę, że jeśli małpie zostanie podane 1 jabłko, to liczba pozostałych jabłek zostanie podzielona na N bez śladu. Dawszy małpie dodatkowe jabłko, wziął 1/ N pozostałe jabłka i wyszliśmy. Później do stosu podchodził następny przechodzień, potem następny, itd. Każdy kolejny przechodzień po przeliczeniu jabłek zauważył, że ich liczba przy dzieleniu przez N daje reszcie 1, a dając małpie dodatkowe jabłko, bierze 1 dla siebie N pozostałe jabłka i ruszyliśmy dalej. Po wyjściu ostatniego, N przechodnia podzielono liczbę jabłek pozostałych na stosie N bez śladu. Ile jabłek było na początku w stosie?

Kierując się tym samym rozumowaniem co Dirac, otrzymaliśmy ogólny wzór na rozwiązanie klasy podobnych problemów: , gdzieN- Liczba naturalna.

2.3. Zastosowanie porównań modułowych w działalności zawodowej.

Teoria porównań ma zastosowanie do teorii kodowania, więc wszystkie osoby, które wybiorą zawód związany z komputerami, będą studiować i ewentualnie stosować porównania w swojej działalności zawodowej. Na przykład do opracowania algorytmów szyfrowania klucza publicznego wykorzystuje się szereg koncepcji teorii liczb, w tym porównania modulo.

Wniosek.

W pracy przedstawiono podstawowe pojęcia i właściwości porównań modulo oraz zilustrowano przykłady zastosowania porównań modulo. Materiał można wykorzystać w przygotowaniu do olimpiad z matematyki i do egzaminu państwowego Unified State Exam.

Podana lista literatury pozwala, jeśli to konieczne, rozważyć bardziej złożone aspekty teorii porównań modulo i jej zastosowań.

Wykaz używanej literatury.

    Alfutova N.B. Algebra i teoria liczb./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 s.

    Bukhshtab A.A. Teoria liczb. /A.A.Bukhshtab. M.: Edukacja, 1960.

    Vilenkin N. Porównania i klasy reszt./N. Vilenkin.//Quantum. – 1978.- 10.

    Fedorova N.E. Studium algebry i analizy matematycznej. klasa 10.http:// www. prosv. ru/ e-booki/ Fiodorowa_ Algebra_10 kl/1/ xht

    ru. wikipedia. org/ wiki/modulo_porównania.

Rozważ porównanie formularza X 2 ≡A(mod Pα), gdzie P– prosta liczba nieparzysta. Jak pokazano w paragrafie 4 §4, rozwiązanie tego porównania można znaleźć rozwiązując porównanie X 2 ≡A(mod P). Poza tym porównanie X 2 ≡A(mod Pα) będzie miało dwa rozwiązania, jeśli A jest resztą kwadratową modulo P.

Przykład:

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

125 = 5 3, 5 to liczba pierwsza. Sprawdźmy, czy 86 jest kwadratem modulo 5.

Oryginalne porównanie ma 2 rozwiązania.

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

X 2 ≡1 (mod 5).

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

X≡±1(mod 5) lub w przeciwnym razie X=±(1+5 T 1).

Podstawmy otrzymane rozwiązanie do porównania 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, co to jest to samo, T 1 =1+5T 2 .

Zatem rozwiązaniem porównania jest modulo 25 X=±(1+5(1+5 T 2))=±(6+25 T 2). Podstawmy otrzymane rozwiązanie do porównania 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 .

Zatem rozwiązaniem porównania jest modulo 125 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(mod 2 α). 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), a takich rozwiązań będą cztery. 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α), jako rozwiązanie początkowe pełnią jedynie rozwiązania modulo 8: X≡±1(mod 8) i X≡±3 (mod 8). Należy je porównywać modulo 16, następnie modulo 32 itd. aż do modulo 2 α.

Przykład:

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

64=2 6 . Sprawdźmy, czy oryginalne porównanie ma rozwiązanie. 33≡1(mod 8), co oznacza, że ​​porównanie ma 4 rozwiązania.

Modulo 8 rozwiązaniami tymi będą: X≡±1(mod 8) i X≡±3 (mod 8), co można przedstawić jako X=±(1+4 T 1). Zastąpmy to wyrażenie porównaniem 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). Podstawmy powstałe rozwiązanie do porównania modulo 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). Podstawmy powstałe rozwiązanie do porównania 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). Zatem modulo 64, oryginalne porównanie ma cztery rozwiązania: X≡±17(mod 64)tj X≡±49 (mod 64).

A teraz spójrzmy na ogólne porównanie: X 2 ≡A(mod M), (A,M)=1, - kanoniczne rozwinięcie modułu M. Zgodnie z Twierdzeniem z paragrafu 4 §4, porównanie to jest równoważne systemowi

Jeśli każde porównanie tego systemu jest rozwiązalne, to cały system jest rozwiązalny. Po znalezieniu rozwiązania każdego porównania tego układu otrzymamy system porównań pierwszego stopnia, rozwiązując który korzystając z chińskiego twierdzenia o resztach, otrzymamy rozwiązanie pierwotnego porównania. Co więcej, liczba różnych rozwiązań pierwotnego porównania (jeśli jest rozwiązywalna) 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).

Definicja 1. Jeśli dwie liczby to 1) A I B przy dzieleniu przez P dać tę samą resztę R, wówczas takie liczby nazywane są równoresztą lub porównywalny pod względem modułu P.

Oświadczenie 1. Pozwalać P jakąś liczbę dodatnią. Potem każdy numer A zawsze i zresztą tylko w sposób daje się przedstawić w formie

Ale liczby te można uzyskać poprzez ustawienie R równe 0, 1, 2,..., P−1. Stąd sp+r=a otrzyma wszystkie możliwe wartości całkowite.

Pokażmy, że ta reprezentacja jest wyjątkowa. Udawajmy, że P można przedstawić na dwa sposoby a=sp+r I a=s 1 P+R 1. Następnie

(2)

Ponieważ R 1 akceptuje jedną z liczb 0,1, ..., P−1, następnie wartość bezwzględna R 1 −R mniej P. Ale z (2) wynika, że R 1 −R wiele P. Stąd R 1 =R I S 1 =S.

Numer R zwany minus liczby A modulo P(innymi słowy, liczba R nazywamy resztą liczby A NA P).

Oświadczenie 2. Jeśli dwie liczby A I B porównywalny pod względem modułu P, To a-b podzielony przez P.

Naprawdę. Jeśli dwie liczby A I B porównywalny pod względem modułu P, a następnie po podzieleniu przez P mają tę samą resztę P. Następnie

podzielony przez P, ponieważ prawa strona równania (3) jest dzielona przez P.

Oświadczenie 3. Jeżeli różnica dwóch liczb jest podzielna przez P, to liczby te są porównywalne pod względem modułu P.

Dowód. Oznaczmy przez R I R Pozostałość z 1 podziału A I B NA P. Następnie

Przykłady 25≡39 (mod 7), -18≡14 (mod 4).

Z pierwszego przykładu wynika, że ​​25 przy dzieleniu przez 7 daje tę samą resztę co 39. Rzeczywiście, 25 = 3,7+4 (reszta 4). 39=3,7+4 (reszta 4). Rozważając drugi przykład, należy wziąć pod uwagę, że reszta musi być liczbą nieujemną mniejszą od modułu (tj. 4). Wtedy możemy zapisać: −18=−5·4+2 (reszta 2), 14=3·4+2 (reszta 2). Dlatego -18 przy dzieleniu przez 4 pozostawia resztę 2, a 14 przy dzieleniu przez 4 daje resztę 2.

Własności porównań modulo

Nieruchomość 1. Dla kazdego A I P Zawsze

nie zawsze jest porównanie

Gdzie λ jest największym wspólnym dzielnikiem liczb M I P.

Dowód. Pozwalać λ największy wspólny dzielnik liczb M I P. Następnie

Ponieważ m(a-b) podzielony przez k, To

Stąd

I M jest jednym z dzielników liczby P, To

Gdzie h=pq.

Należy pamiętać, że możemy zezwolić na porównania w oparciu o moduły ujemne, tj. porównanie a≡b mod( P) oznacza w tym przypadku różnicę a-b podzielony przez P. Wszystkie właściwości porównań pozostają w mocy dla modułów ujemnych.

Przy n dają te same reszty.

Równoważne preparaty: a i b porównywalny pod względem modułu 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- jakaś liczba całkowita. Na przykład: 32 i -10 są porównywalne modulo 7, ponieważ

Stwierdzenie „aib są porównywalne modulo n” zapisuje się 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 porównywalny modulo 1.

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

Jeżeli liczby i są porównywalne parami pod względem modułu N, to ich sumy i , jak również produkty i są również porównywalne pod względem modułu N.

Jeśli liczby A I B porównywalny pod względem modułu N, a następnie ich stopnie naukowe A k I B k są również porównywalne pod względem modułu N pod jakimkolwiek naturalnym k.

Jeśli liczby A I B porównywalny pod względem modułu N, I N podzielony przez M, To A I B porównywalny pod względem modułu M.

W kolejności numerów A I B były porównywalne pod względem modułu N, przedstawiony w postaci jego kanonicznego rozkładu na proste czynniki P I

konieczne i wystarczające

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

Jednakże porównań nie można, ogólnie rzecz biorąc, dzielić między sobą ani innymi liczbami. Przykład: jednak zmniejszając o 2 otrzymujemy błędne porównanie: . Zasady skrótów 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

Zajęcia odliczeniowe

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

Od porównania modulo N jest relacją równoważności na zbiorze liczb całkowitych, to klasy reszt modulo N reprezentują klasy równoważności; ich liczba jest równa N. Zbiór wszystkich klas reszt modulo N oznaczone przez lub.

Operacje dodawania i mnożenia przez wywołują odpowiednie operacje na zbiorze:

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

W odniesieniu do tych operacji zbiór jest skończonym pierścieniem, a jeśli N proste - pole skończone.

Systemy odliczeń

System reszt umożliwia wykonywanie operacji arytmetycznych na skończonym zbiorze liczb bez wykraczania poza jego granice. Pełny system odliczeń modulo n jest dowolnym zbiorem n liczb całkowitych, które są nieporównywalne modulo n. Zwykle najmniejsze reszty nieujemne są brane pod uwagę jako kompletny układ reszt modulo n

0,1,...,N − 1

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

,

w przypadku nieparzystym N i liczby

w przypadku parzystego N .

Rozwiązywanie porównań

Porównania pierwszego stopnia

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

Rozwiązanie takiego porównania rozpoczyna 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 to jest to samo, D rozwiązania modulo M. W tym przypadku w wyniku zmniejszenia pierwotnego porównania o D porównanie jest następujące:

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

Praktyczne obliczanie wartości C można zrealizować na różne sposoby: wykorzystując twierdzenie Eulera, algorytm Euklidesa, teorię 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, porównywalne z tym modulo 22, a następnie zmniejszmy wszystkie 3 liczby o 2:

Ponieważ 2 jest liczbą względnie pierwszą do modulo 11, możemy zredukować lewą i prawą stronę 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 sprawdzenia, czy dana liczba jest resztą kwadratową (z wykorzystaniem prawa wzajemności kwadratowej), a następnie obliczenia pierwiastka kwadratowego.

Fabuła

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