Rješavanje poređenja prvog stepena. Poređenje po modulu prirodni broj Poređenje teorije brojeva po modulu

Poređenje prvog stepena sa jednom nepoznatom ima oblik:

f(x) 0 (mod m); f(X) = Oh + a n. (1)

Riješite poređenje znači pronaći sve vrijednosti x koje ga zadovoljavaju. Pozivaju se dva poređenja koja zadovoljavaju iste vrijednosti x ekvivalentan.

Ako poređenje (1) zadovoljava neke x = x 1, zatim (prema 49) svi brojevi uporedivi sa x 1 , modulo m: x x 1 (mod m). Cijela ova klasa brojeva se računa kao jedno rešenje. Ovim sporazumom se može izvesti sljedeći zaključak.

66.S poravnanje (1) imaće onoliko rješenja koliko ima ostataka kompletnog sistema koji ga zadovoljava.

Primjer. Poređenje

6x– 4 0 (mod 8)

među brojevima 0, 1,2, 3, 4, 5, 6, 7 kompletnog sistema ostataka po modulu 8, dva broja zadovoljavaju: X= 2 i X= 6. Dakle, ovo poređenje ima dva rješenja:

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

Poređenje prvog stepena prenošenjem slobodnog člana (sa suprotnim predznakom) na desnu stranu može se svesti na oblik

sjekira b(mod m). (2)

Razmotrimo poređenje koje zadovoljava uslov ( A, m) = 1.

Prema 66 naše poređenje ima onoliko rješenja koliko ima ostataka kompletnog sistema koji ga zadovoljava. Ali kada x prolazi kroz kompletan sistem ostataka po modulu T, To Oh prolazi kroz cijeli sistem odbitaka (od 60). Dakle, za jednu i samo jednu vrijednost X, preuzeto iz kompletnog sistema, Oh biće uporedivo sa b. dakle,

67. Za (a, m) = 1 uporedna os b(mod m)ima jedno rešenje.

pusti sada ( a, m) = d> 1. Tada je za poređenje (2) potrebno (od 55) da ima rješenja b podijeljen u d, inače je poređenje (2) nemoguće za bilo koji cijeli broj x . Pretpostavljajući dakle b višestruko d, stavimo a = a 1 d, b = b 1 d, m = m 1 d. Tada će poređenje (2) biti ekvivalentno ovome (smanjeno za d): a 1 x b 1 (mod m), u kojoj već ( A 1 , m 1) = 1, i stoga će imati jedno rješenje po modulu m 1 . Neka X 1 je najmanji nenegativni ostatak ovog rješenja po modulu m 1 , onda svi brojevi x , formiranje ovog rješenja može se naći u obliku

x x 1 (mod m 1). (3)

Po modulu, brojevi (3) ne čine jedno rješenje, već više, točno onoliko rješenja koliko ima brojeva (3) u nizu 0, 1, 2, ..., m 1 najmanji nenegativni ostatak po modulu m. Ali ovdje će pasti sljedeće brojke (3):

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

one. Ukupno d brojevi (3); stoga poređenje (2) ima d rješenja.

Dobijamo teoremu:

68. Neka (a, m) = d. poređenje ax b ( mod m) nemoguće ako b nije deljivo sa d. Kada je b višekratnik od d, poređenje ima d rješenja.

69. Metoda rješavanja poređenja prvog stepena, zasnovana na teoriji kontinuiranih razlomaka:

Proširivanje u kontinuirani razlomak omjera m:a,

i uzimajući u obzir posljednja dva konvergenta:

prema svojstvima kontinuiranih razlomaka (prema 30 ) imamo

Dakle, poređenje ima rješenje

za pretragu, što je dovoljno za izračunavanje P n- 1 prema metodi navedenoj u 30.

Primjer. Hajde da rešimo poređenje

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

Ovdje (111, 321) = 3, a 75 je višekratnik od 3. Prema tome, poređenje ima tri rješenja.

Podjelom oba dijela poređenja i modula sa 3, dobijamo poređenje

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

o čemu prvo treba da odlučimo. Imamo

q
P 3

Dakle, u ovom slučaju n = 4, P n - 1 = 26, b= 25, a rješenje poređenja (5) imamo u obliku

x–26 ∙ 25 99 (mod 107).

Dakle, rješenja poređenja (4) su predstavljena na sljedeći način:

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

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

Izračunavanje inverznog elementa po modulu a

70.Ako cijeli brojevi a I n koprost, onda postoji broj a′, zadovoljavajući poređenje a ∙ a′ ≡ 1 (mod n). Broj a′ pozvao multiplikativni inverz od modula n a za to se koristi notacija a- 1 (mod n).

Izračunavanje recipročnih vrednosti po modulu nekih može se izvršiti rešenjem poređenja prvog stepena sa jednom nepoznatom, u kojoj x prihvaćen broj a′.

Da nađem rešenje za poređenje

sjekira≡ 1 (mod m),

Gdje ( a,m)= 1,

može se koristiti Euklid algoritam (69) ili Fermat-Eulerova teorema, koja kaže da ako ( a,m) = 1, onda

a φ( m) ≡ 1(mod m).

x ≡ a φ( m)–1 (mod m).

Grupe i njihova svojstva

Grupe su jedna od taksonomskih klasa koje se koriste u klasifikaciji matematičkih struktura sa zajedničkim karakterističnim svojstvima. Grupe imaju dvije komponente: gomila (G) I operacije() definisano na ovom skupu.

Koncepti skupa, elementa i pripadnosti su osnovni nedefinisani koncepti moderne matematike. Bilo koji skup je definiran elementima koji su u njemu uključeni (koji zauzvrat također mogu biti skupovi). Dakle, kažemo da je skup definiran ili zadan ako za bilo koji element možemo reći da li pripada ovom skupu ili ne.

Za dva seta A, B evidencije B A, B A, B∩ A, B A, B \ A, A × B znači, respektivno, to B je podskup skupa A(tj. bilo koji element iz B je takođe sadržan u A, na primjer, skup prirodnih brojeva je sadržan u skupu realnih brojeva; osim toga, uvek A A), B je ispravan podskup skupa A(oni. B A I B ≠ A), raskrsnica mnogih B I A(tj. svi takvi elementi koji leže istovremeno i u A, i u B, na primjer, presjek cijelih brojeva i pozitivnih realnih brojeva je skup prirodnih brojeva), unija skupova B I A(tj. skup koji se sastoji od elemenata koji leže bilo u A, bilo u B), postavite razliku B I A(tj. skup elemenata koji leže u B, ali nemojte lagati A), kartezijanski proizvod skupova A I B(tj. skup parova oblika ( a, b), Gdje a A, b B). Kroz | A| kardinalnost skupa je uvijek označena A, tj. broj elemenata u setu A.

Operacija je pravilo prema kojem bilo koja dva elementa skupa G(a I b) je povezan s trećim elementom iz G: a b.

Puno elemenata G sa operacijom pod nazivom grupa ako su ispunjeni sledeći uslovi.

Sadržaj.

Uvod

§1. Poređenje modula

§2. Svojstva poređenja

1. Svojstva poređenja nezavisnih od modula
2. Svojstva poređenja specifičnih za modul

§3. Sistem odbitka

1. Kompletan sistem odbitaka
2. Redukovani sistem odbitaka

§4. Ojlerova teorema i Fermat

1. Eulerova funkcija
2. Ojlerova teorema i Fermat

Poglavlje 2. Teorija poređenja sa varijablom

§1. Osnovni koncepti vezani za odluku o poređenja

1. Korijeni poređenja
2. Ekvivalencija poređenja
3. Wilsonova teorema

§2. Poređenja prvog stepena i njihova rješenja

1. Metoda odabira
2. Ojlerove metode
3. Metoda Euklidovog algoritma
4. Metoda kontinuiranog razlomka

§3. Sistemi poređenja 1. stepena sa jednom nepoznatom

§4. Podjela poređenja viših sila

§5. Primitivni korijeni i indeksi

1. Redoslijed klase odbitka
2. Primitivni korijeni po modulu prosti
3. Indeksi po modulu prosti

Poglavlje 3 Primjena teorije poređenja

§1. Znakovi djeljivosti

§2. Provjera rezultata aritmetičkih operacija

§3. Pretvaranje običnog razlomka u konačni

decimalni razlomak

Zaključak

Književnost

Uvod

U našem životu često se moramo suočiti s cijelim brojevima i zadacima u vezi s njima. U ovoj tezi razmatram teoriju poređenja cijelih brojeva.

Dva cijela broja čija je razlika višekratnik datog prirodnog broja m nazivaju se uporedivim modulom m.

Reč "modul" potiče od latinskog modula, što na ruskom znači "mera", "vrednost".

Izjava "a je kongruentna sa b po modulu m" obično se piše kao ab (mod m) i naziva se poređenje.

Definicija poređenja formulisana je u knjizi K. Gaussa "Aritmetička istraživanja". Ovo djelo, napisano latinicom, počelo je da se štampa 1797. godine, ali je knjiga objavljena tek 1801. godine zbog činjenice da je proces štampanja u to vrijeme bio izuzetno naporan i dugotrajan. Prvi dio Gaussove knjige zove se "O poređenju brojeva općenito".

Poređenja su vrlo zgodna za korištenje u onim slučajevima kada je u bilo kojem istraživanju dovoljno znati brojeve do višekratnike određenog broja.

Na primjer, ako nas zanima kojom cifrom završava kocka cijelog broja a, onda nam je dovoljno da znamo samo a do višekratnika 10 i možemo koristiti poređenja po modulu 10.

Svrha ovog rada je razmatranje teorije poređenja i proučavanje glavnih metoda za rješavanje poređenja sa nepoznatim, kao i proučavanje primjene teorije poređenja na školsku matematiku.

Rad se sastoji od tri poglavlja, a svako poglavlje je podijeljeno na paragrafe, a paragrafi na paragrafe.

Prvo poglavlje bavi se općim pitanjima teorije poređenja. Ovdje razmatramo koncept poređenja po modulu, svojstva poređenja, kompletan i redukovani sistem rezidua, Ojlerovu funkciju, Ojlerovu i Fermaovu teoremu.

Drugo poglavlje je posvećeno teoriji poređenja sa nepoznatim. Iznosi osnovne pojmove vezane za rješavanje poređenja, razmatra metode rješavanja poređenja prvog stepena (metoda izbora, Ojlerova metoda, metoda Euklidovog algoritma, metoda kontinuiranih razlomaka, korištenjem indeksa), sisteme poređenja prvog stepena sa jedna nepoznata, poređenja viših stepena itd.

Treće poglavlje sadrži neke primjene teorije brojeva na školsku matematiku. Razmatraju se znaci djeljivosti, provjera rezultata radnji, pretvaranje običnih razlomaka u sistematske decimalne razlomke.

Izlaganje teorijskog materijala praćeno je velikim brojem primjera koji otkrivaju suštinu uvedenih pojmova i definicija.

Poglavlje 1. Opća pitanja teorije poređenja

§1. Poređenje modula

Neka z-prsten cijelih brojeva, m-fiksni cijeli broj i m z-skup svih cijelih brojeva djeljivih sa m.

Definicija 1. Za dva cijela broja a i b se kaže da su kongruentni po modulu m ako m dijeli a-b.

Ako su brojevi a i b uporedivi po modulu m, onda napišite a b (mod m).

Stanje a b (mod m) znači da je a-b deljivo sa m.

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

Definiramo da se relacija uporedivosti po modulu m poklapa sa relacijom uporedivosti po modulu (-m) (djeljivost sa m je ekvivalentna djeljivosti sa –m). Stoga, bez gubitka općenitosti, možemo pretpostaviti da je m>0.

Primjeri.

Teorema. (znak uporedivosti duhovnih brojeva po modulu m): Dva cijela broja a i b su uporediva po modulu m ako i samo ako a i b imaju isti ostatak kada se podijele sa m.

Dokaz.

Neka su ostaci pri dijeljenju a i b sa m jednaki, tj. a=mq₁+r,(1)

B=mq₂+r, (2)

Gdje je 0≤r≥m.

Oduzmite (2) od (1), dobijamo a-b= m(q₁- q₂), tj. a-b m ili a b (mod m).

Obrnuto, neka a b (mod m). To znači a-b m ili a-b=mt, t z (3)

Podijeliti b sa m; dobijamo b=mq+r u (3), imaćemo a=m(q+t)+r, to jest, deljenjem a sa m dobija se isti ostatak kao i deljenjem b sa m.

Primjeri.

5=4 (-2)+3

23=4 5+3

24=3 8+0

10=3 3+1

Definicija 2. Dva ili više brojeva koji daju isti ostatak kada se podijele sa m nazivaju se jednako udaljeni ili uporedivi po modulu m.

Primjeri.

Imamo: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) je deljivo sa m => naše poređenje je tačno.

1. Dokažite da su sljedeća poređenja lažna:

Ako su brojevi uporedivi po modulu m, onda imaju isti gcd sa njim.

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

gcd(4,10) = 2, gcd(25,10) = 5, tako da je naše poređenje pogrešno.

§2. Svojstva poređenja

1. Svojstva poređenja nezavisne od modula.

Mnoga svojstva poređenja su slična osobinama jednakosti.

a) refleksivnost: aa (mod m) (bilo koji cijeli broj a je uporediv sa samim sobom po modulu m);

C) simetrija: ako a b (mod m), zatim b a (mod m);

C) tranzitivnost: ako a b (mod m), i b sa (mod m), zatim a sa (mod m).

Dokaz.

Po uslovu m/(a-b) i m/ (c-d). Dakle, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b + d (mod m).

Primjeri.

Pronađite ostatak prilikom dijeljenja u 13.

Rješenje: -1 (mod 13) i 1 (mod 13), zatim (-1)+1 0 (mod 13), odnosno ostatak dijeljenja sa 13 je 0.

a-c b-d (mod m).

Dokaz.

Po uslovu m/(a-b) i m/(c-d). Dakle, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (posledica svojstava 1, 2, 3). Možete dodati isti cijeli broj u oba dijela poređenja.

Dokaz.

Neka a b (mod m) i k je bilo koji cijeli broj. Svojstvom refleksivnosti

k=k (mod m), a prema osobinama 2 i 3 imamo a+k b + k (mod m).

a c d (mod m).

Dokaz.

Po uslovu, a-b ê mz, c-d ê mz. Otuda 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).

Posljedica. Oba dijela poređenja mogu se podići na isti cijeli broj nenegativan stepen: ako ab (mod m) i s je nenegativan cijeli broj, tada a s b s (mod m).

Primjeri.

Rješenje: očigledno 13 1 (mod 3)

2-1 (mod 3)

5 -1 (mod 3), onda

- 1-1 0 (mod 13)

odgovor: željeni ostatak je nula, a A je djeljiv sa 3.

Rješenje:

Dokažimo da je 1+ 0(mod13) ili 1+ 0(mod 13)

1+ =1+ 1+ =

Kako je 27 1 (mod 13), slijedi da je 1+ 1+1 3+1 9 (mod 13).

h.t.d.

3. Pronađite ostatak kada dijelite s ostatkom broja u 24.

Imamo: 1 (mod 24), dakle

1 (mod 24)

Dodajući 55 oba dijela poređenja, dobivamo:

(mod 24).

Imamo: (mod 24), dakle

(mod 24) za bilo koji k ê N.

Dakle (mod 24). Od (-8)16 (mod 24), željeni ostatak je 16.

1. Oba dijela poređenja mogu se pomnožiti istim cijelim brojem.

2.Svojstva poređenja u zavisnosti od modula.

Dokaz.

Pošto je a b (mod t), onda (a - b) t. A pošto je t n , zatim zbog tranzitivnosti relacije djeljivosti(a - b n) , odnosno a b (mod n).

Primjer.

Pronađite ostatak nakon dijeljenja 196 sa 7.

Rješenje:

Znajući da je 196= , možemo napisati 196(mod 14). Koristimo prethodno svojstvo, 14 7, dobijamo 196 (mod 7), odnosno 196 7.

1. Oba dijela poređenja i modul mogu se pomnožiti istim pozitivnim cijelim brojem.

Dokaz.

Neka je a b (mod m ) i c je pozitivan cijeli broj. Tada je a-b = mt i ac-bc=mtc, ili ac bc (mod mc).

Primjer.

Provjerite je li vrijednost izraza cijeli broj.

Rješenje:

Razlomke predstavimo u obliku poređenja: 4(mod 3)

1 (mod 9)

31 (mod 27)

Dodamo ova poređenja pojam po član (svojstvo 2), dobićemo 124(mod 27) Vidimo da 124 nije cijeli broj djeljiv sa 27, otuda i vrijednost izrazatakođer nije cijeli broj.

1. Oba dijela poređenja mogu se podijeliti njihovim zajedničkim faktorom ako je relativno prost prema modulu.

Dokaz.

Ako ca cb (mod m), tj. m/c(a-b) i broj With koprostor sa m, (c,m)=1, tada m deli a-b. dakle, a b (mod t).

Primjer.

60 9 (mod 17), nakon dijeljenja oba dijela poređenja sa 3 dobijamo:

20 (mod 17).

Uopšteno govoreći, nemoguće je podijeliti oba dijela poređenja brojem koji nije koprost sa modulom, jer se nakon dijeljenja mogu dobiti brojevi koji su neuporedivi u ovom modulu.

Primjer.

8 (mod 4) ali 2 (mod 4).

1. Oba dijela poređenja i modul mogu se podijeliti svojim zajedničkim djeliteljem.

Dokaz.

Ako ka kb (mod km), tada je k (a-b) djeljivo sa km. Dakle, a-b je deljivo sa m, tj a b (mod t).

Dokaz.

Neka je P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n . Po uslovu a b (mod t), onda

a k b k (mod m) za k = 0, 1, 2, …,n. Množenjem oba dijela svakog od rezultirajućih n + 1 poređenja sa c n-k , dobijamo:

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

Zbrajanjem zadnjih poređenja dobijamo: P (a) P(b) (mod m). Ako su a (mod m) i c i d i (mod m), 0 ≤ i ≤ n, tada

(mod m). Dakle, u kongruenciji po modulu m, pojedinačni termini i faktori mogu biti zamijenjeni brojevima kongruentnim po modulu m.

Pri tome treba obratiti pažnju na činjenicu da se eksponenti koji se susreću u poređenjima ne mogu zamijeniti na ovaj način: od

a n c(mod m) i n k(mod m) ne implicira da a k sa (mod m).

Svojstvo 11 ima niz važnih primjena. Konkretno, može se koristiti za davanje teorijske potpore znakovima djeljivosti. Za ilustraciju, kao primjer, dat ćemo izvođenje testa djeljivosti sa 3.

Primjer.

Bilo koji prirodni broj N može se predstaviti kao sistematski broj: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

Razmotrimo polinom f (x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Jer

10 1 (mod 3), zatim svojstvom 10 f (10) f(1) (mod 3) ili

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a n (mod 3), tj. da bi N bilo djeljivo sa 3, potrebno je i dovoljno da zbir cifara ovog broja bude djeljiv sa 3.

§3. Sistemi odbitka

1. Kompletan sistem naplate.

Ekvidistantni brojevi ili, što je isto, uporedivi po modulu m, čine klasu brojeva po modulu m.

Iz ove definicije slijedi da isti ostatak r odgovara svim brojevima klase, a sve brojeve klase dobijamo ako natjeramo q da prolazi kroz sve cijele brojeve u obliku mq + r.

Prema tome, sa m različitih vrijednosti r, imamo m klasa brojeva po modulu m.

Bilo koji broj klase naziva se ostatak po modulu m u odnosu na sve brojeve iste klase. Ostatak dobijen pri q=0, jednak ostatku r, naziva se najmanjim nenegativnim ostatkom.

Ostatak ρ, najmanji po apsolutnoj vrijednosti, naziva se apsolutno najmanjim ostatkom.

Očigledno, za r imamo ρ=r; kada je r> imamo ρ=r-m; konačno, ako je m paran i r=, tada se za ρ može uzeti bilo koji od dva broja i -m= - .

Mi biramo iz svake klase ostataka po modulu T jednim brojem. Get m cijelih brojeva: x 1 ,…, x m . Skup (x 1, ..., x t) se zove kompletan sistem ostataka po modulu m.

Pošto svaka klasa sadrži nebrojiv skup ostataka, moguće je sastaviti nebrojiv skup različitih kompletnih sistema ostataka po modulu m, od kojih svaki sadrži t odbitaka.

Primjer.

Sastaviti nekoliko kompletnih sistema ostataka po modulu T = 5. Imamo klase: 0, 1, 2, 3, 4.

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

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

Napravimo nekoliko kompletnih sistema odbitaka, uzimajući po jedan odbitak iz svake klase:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

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

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

itd.

Najčešće korišteni:

1. Kompletan sistem najmanje nenegativnih ostataka: 0, 1, t -1 U gornjem primjeru: 0, 1, 2, 3, 4. Takav sistem ostataka je jednostavan: trebate zapisati sve nenegativne ostatke koji nastaju dijeljenjem sa m.
2. Kompletan sistem najmanje pozitivnih ostataka(najmanji pozitivni odbitak se uzima iz svakog razreda):

1, 2, …,m. U našem primjeru: 1, 2, 3, 4, 5.

1. Kompletan sistem sa apsolutno najmanje rezidua.U slučaju neparnog m, apsolutno najmanji ostaci se pojavljuju jedan pored drugog.

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

a u slučaju parnog m, jedan od dva reda

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

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

U datom primjeru: -2, -1, 0, 1, 2.

Razmotrimo sada glavna svojstva kompletnog sistema ostataka.

Teorema 1 . Bilo koji skup od m cijelih brojeva:

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

parno neuporediv po modulu m, formira kompletan sistem ostataka po modulu m.

Dokaz.

1. Svaki od brojeva u skupu (1) pripada nekoj klasi.
2. Bilo koja dva broja x i i x j iz (1) su međusobno neuporedivi, tj. pripadaju različitim klasama.
3. Ukupno ima m brojeva u (1), tj. onoliko koliko ima klasa po modulu T.

x 1, x 2,…, x t je kompletan sistem ostataka po modulu m.

Teorema 2. Neka (a, m) = 1, b - proizvoljan cijeli broj; onda ako x 1, x 2,…, x t -kompletan sistem ostataka po modulu m, zatim skup brojeva ax 1 + b, ax 2 + b,…, ax m + b je također kompletan sistem ostataka po modulu m.

Dokaz.

Razmislite

Ax 1 + b, ax 2 + b, ..., ax m + b (2)

1. Svaki od brojeva u skupu (2) pripada nekoj klasi.
2. Bilo koja dva broja ax i +b i ax j + b iz (2) su međusobno neuporedivi, odnosno pripadaju različitim klasama.

Zaista, ako postoje dva broja u (2) takva da

ax i + b ax j + b (mod m), (i = j), onda bismo dobili ax i ax j (mod m). Pošto (a, t) = 1, tada svojstvo poređenja može smanjiti oba dijela poređenja za A . Dobijamo x i x j (mod m).

Po uslovu, x i x j (mod m) za (i = j) , budući da je x 1 ,x 2 , ..., x m - puni sistem odbitaka.

1. Skup brojeva (2) sadrži T brojeva, odnosno onoliko koliko ima klasa po modulu m.

Dakle, ax 1 + b, ax 2 + b, ..., ax m + b je kompletan sistem ostataka po modulu m.

Primjer.

Neka je m = 10, a = 3, b = 4.

Uzmimo neki kompletan sistem ostataka po modulu 10, na primjer: 0, 1, 2, ..., 9. Sastavimo brojeve oblika sjekira + b. Dobijamo: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Dobijeni skup brojeva je kompletan sistem ostataka po modulu 10.

1. Dati sistem odbitaka.

Dokažimo sljedeću teoremu.

Teorema 1.

Brojevi iste klase ostataka po modulu m imaju isti najveći zajednički djelitelj sa m: ako a b (mod m), tada (a, m) = (b, m).

Dokaz.

Neka je a b (mod m). Tada je a = b + mt, gdje je t z. Iz ove jednakosti slijedi da (a, m) = (b, m).

Zaista, neka je δ-zajednički djelitelj a i m, onda je aδ, m δ. Kako je a = b + mt, onda je b=a-mt, dakle bδ. Stoga je svaki zajednički djelitelj a i m zajednički djelitelj m i b.

Obrnuto, ako je m δ i b δ, onda je a = b + mt je djeljiv sa δ, i stoga je svaki zajednički djelitelj m i b zajednički djelitelj a i m. Teorema je dokazana.

Definicija 1. Najveći zajednički djelitelj modula t i bilo koji broj a iz ove klase odbitaka za T zove najveći zajednički djelitelj T i ovu klasu ostataka.

Definicija 2. Klasa ostatka a po modulu m naziva se koprimenom sa modulom m ako je najveći zajednički djelitelj a i t jednako 1 (to jest, ako m i bilo koji broj iz a su međusobno prosti).

Primjer.

Neka t = 6. Klasa ostatka 2 sastoji se od brojeva (..., -10, -4, 2, 8, 14, ...). Najveći zajednički djelitelj bilo kojeg od ovih brojeva i modula 6 je 2. Dakle, (2, 6) = 2. Najveći zajednički djelitelj bilo kojeg broja iz klase 5 i modula 6 je 1. Dakle, klasa 5 je relativno prosta modulu 6.

Izaberemo iz svake klase ostataka koji su koprosti po modulu m jedan broj. Dobijamo sistem odbitaka, koji je dio kompletnog sistema odbitaka. Zovu jesmanjeni sistem ostataka po modulu m.

Definicija 3. Skup ostataka po modulu m, uzetih jedan po jedan iz svakog koprostog s T klasa ostataka po modulu ovaj modul se naziva redukovani sistem ostataka.

Definicija 3 implicira metodu za dobijanje redukovanog sistema ostataka po modulu T: potrebno je ispisati neki kompletan sistem ostataka i iz njega ukloniti sve ostatke koji nisu koprimarni sa m. Preostali skup odbitaka je redukovani sistem odbitaka. Očigledno postoji beskonačan broj reduciranih sistema ostataka po modulu m.

Ako kao početni uzmemo kompletan sistem najmanje nenegativnih ili apsolutno najmanjih ostataka, onda se na navedeni način dobija redom redukovani sistem najmanje nenegativnih ili apsolutno najmanjih ostataka po modulu m.

Primjer.

Ako je T = 8, zatim 1, 3, 5, 7 - redukovani sistem najmanjih nenegativnih ostataka, 1, 3, -3, -1- smanjen sistem apsolutno najmanjeg ostataka.

Teorema 2.

Neka broj klasa relativno prostih sa m jednak je k.Zatim bilo koja kolekcija od k cijelih brojeva

parno neuporediv po modulu m i relativno prost sa m, je redukovani sistem ostataka po modulu m.

Dokaz

A) Svaki broj u skupu (1) pripada nekoj klasi.

1. Svi brojevi iz (1) su parno neuporedivi po modulu T, odnosno pripadaju različitim klasama po modulu m.
2. Svaki broj iz (1) je koprost sa T, to jest, svi ovi brojevi pripadaju različitim klasama koje su međusobno prosti sa modulom m.
3. Ukupno, (1) ima k brojeva, odnosno onoliko koliko redukovani sistem ostataka po modulu m treba da sadrži.

Dakle, skup brojeva(1) - smanjeni sistem ostataka po modulu T.

§4. Eulerova funkcija.

Ojlerove i Fermaove teoreme.

1. Eulerova funkcija.

Označiti sa φ(T) broj klasa ostataka po modulu m koprost sa m, odnosno broj elemenata redukovanog sistema ostataka po modulu t. Funkcija φ (t) je numerički. Zovu jeEulerova funkcija.

Mi biramo kao predstavnike klasa ostataka po modulu t brojevi 1, ... , t - 1, t. Tada φ (t) je broj takvih brojeva sa jednostavnim t. Drugim riječima, φ (t) - broj pozitivnih brojeva koji ne prelazi m i relativno prosti sa m.

Primjeri.

1. Neka t = 9. Kompletan sistem ostataka po modulu 9 sastoji se od brojeva 1, 2, 3, 4, 5, 6, 7, 8, 9. Od njih su brojevi 1, 2, 4, 5, 7, 8 međusobno prosti od 9. Dakle, pošto je broj ovih brojeva 6, onda je φ (9) = 6.
2. Neka je t = 12. Kompletan sistem ostataka sastoji se od brojeva 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Od njih su brojevi 1, 5, 7, 11 međusobno prosti iz 12. Dakle,

φ(12) = 4.

Na t = 1, kompletan sistem ostataka se sastoji od jedne klase 1. Zajednički prirodni djelitelj brojeva 1 i 1 je 1, (1, 1) = 1. Na osnovu toga stavljamo φ(1) = 1.

Pređimo na izračunavanje Eulerove funkcije.

1) Ako je m = p je prost broj, onda je φ(p) = p-1.

Dokaz.

Ostaci 1, 2, ... , p-1 i samo su oni koprosti sa prostim brojem R. Stoga je φ (p) = p - 1.

2) Ako je m = p k - snaga prostog broja p, onda

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

Dokaz.

Kompletan sistem ostataka po modulu t = p k sastoji se od brojeva 1,..., p k - 1, p k prirodni djelitelji T su stepeni R. Stoga broj Amože imati zajednički djelitelj sa m koji nije 1, samo kadaApodijeljenaR.Ali među brojevima 1, ... , strk -1 onRdijeljenje samo brojevap, 2p, ... , str2 , ... RTo, čiji je brojRTo: p = pk-1. Dakle, koprimeran sat = pToodmorRTo- Rk-1=pkl(p-1)brojevi. Dakle, dokazano je da

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

Teorema1.

Ojlerova funkcija je multiplikativna, odnosno za koproste brojeve m i n imamo φ (mn) = φ(m) φ (n).

Dokaz.

Prvi zahtjev u definiciji multiplikativne funkcije ispunjen je na trivijalan način: Eulerova funkcija je definirana za sve prirodne brojeve, a φ (1) = 1. To samo trebamo pokazati akotiponda relativno prosti brojevi

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

Kompletan sistem ostataka rasporediti po modulutpasPXT -matrice

1 2 T

t+1 t+2 2t

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

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

ZbogTIPkoprost, zatim brojXobostrano jednostavno satpako i samo akoXobostrano jednostavno saTIXobostrano jednostavno saP. Ali brojkm + tobostrano jednostavno saTako i samo akotobostrano jednostavno saT.Stoga se brojevi relativno prosti sa m nalaze u onim stupcima za kojetprolazi kroz redukovani sistem ostataka po moduluT.Broj takvih stupaca je φ(T).Svaka kolona predstavlja kompletan sistem ostataka po moduluP.Iz ovih ostataka φ(P)coprime withP.Dakle, ukupan broj brojeva zajedno prostih i saTi sa n, jednako φ(T)φ(n)

(φ (T)kolone, od kojih svaka uzima φ(P)brojevi). Ovi brojevi, i samo oni, su prostiitd.Dakle, dokazano je da

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

Primjeri.

№1 . Dokažite sljedeće jednakosti

φ(4n) =

Dokaz.

№2 . riješiti jednačinu

Rješenje:jer(m)=, To= , to je=600, =75, =3, tada x-1=1, x=2,

y-1=2, y=3

Odgovor: x=2, y=3

Možemo izračunati vrijednost Eulerove funkcije(m), znajući kanonski prikaz broja m:

m=.

Zbog množitelja(m) imamo:

(m)=.

Ali prema formuli (1) dobijamo to

-1), i stoga

(3)

Jednakost (3) se može prepisati kao:

Zbog=m, onda(4)

Formula (3) ili, što je isto, (4) je željena.

Primjeri.

№1 . Koliki je iznos

Rješenje:,

, =18 (1- ) (1- =18 , Onda= 1+1+2+2+6+6=18.

№2 . Na osnovu svojstava Eulerove funkcije broja dokazati da postoji beskonačan skup prostih brojeva u nizu prirodnih brojeva.

Rješenje:Pretpostavimo da je ravnanje broja prostih brojeva konačnim skupomje najveći prost broj i neka je a=je proizvod svih prostih brojeva, zasnovan na jednom od svojstava funkcije Eulerovog broja

Pošto a≥, tada je a složeni broj, ali pošto njegova kanonska reprezentacija sadrži sve proste brojeve, onda=1. Imamo:

=1 ,

što je nemoguće, pa je tako dokazano da je skup prostih brojeva beskonačan.

№3 .Riješi jednačinu, gdje je x=I=2.

Rješenje:Koristimo svojstvo Eulerove numeričke funkcije,

,

i po stanju=2.

Express from=2 , dobijamo, zamenimo unutra

:

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

Tada je x=, x=11 13=143.

odgovor:x= 143

2. Ojlerova teorema i Fermat.

U teoriji poređenja Ojlerova teorema igra važnu ulogu.

Ojlerova teorema.

Ako je cijeli broj a relativno prost sa m, onda

(1)

Dokaz.Neka

(2)

je reduciran sistem ostataka po modulu m.

Akoaonda je cijeli broj relativno prost sa m

(3)

Razmotrite poređenje forme x 2 ≡a(mod strα), gdje str je jednostavan neparan broj. Kao što je prikazano u Odjeljku 4 §4, rješenje ove podudarnosti može se naći rješavanjem podudarnosti x 2 ≡a(mod str). I poređenje x 2 ≡a(mod strα) će imati dva rješenja ako a je kvadratni ostatak po modulu str.

primjer:

Riješite kvadratno poređenje x 2 ≡86 (mod 125).

125 = 5 3 , 5 je prost broj. Provjerimo da li je 86 kvadrat po modulu 5.

Originalno poređenje ima 2 rješenja.

Hajde da nađemo rešenje za poređenje x 2 ≡86 (mod 5).

x 2 ≡1(mod 5).

Ovo poređenje bi se moglo riješiti na način naveden u prethodnom pasusu, ali ćemo koristiti činjenicu da je kvadratni korijen od 1 po modulu ±1, a poređenje ima tačno dva rješenja. Dakle, rješenje kongruencije po modulu 5 je

x≡±1(mod 5) ili, inače, x=±(1+5 t 1).

Zamijenite rezultirajuće rješenje u poređenje po modulu 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), ili ekvivalentno, t 1 =1+5t 2 .

Tada je rješenje kongruencije po modulu 25 x=±(1+5(1+5 t 2))=±(6+25 t 2). Zamijenite rezultirajuće rješenje u poređenje po modulu 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), ili t 2 =1+5t 3 .

Tada je rješenje poređenja po modulu 125 x=±(6+25(1+5 t 3))=±(31+125 t 3).

odgovor: x≡±31 (mod 125).

Razmotrite sada poređenje forme x 2 ≡a(mod2α). Takvo poređenje nema uvijek dva rješenja. Za takav modul mogući su sljedeći slučajevi:

1) α=1. Tada poređenje ima rješenje samo kada a≡1(mod 2), a rješenje je x≡1(mod 2) (jedno rješenje).

2) α=2. Poređenje ima rješenja samo kada a≡1(mod 4), a rješenje je x≡±1(mod 4) (dva rješenja).

3) α≥3. Poređenje ima rješenja samo kada a≡1(mod 8), a takva rješenja će biti četiri. Poređenje x 2 ≡a(mod 2 α) za α≥3 rješava se na isti način kao i poređenja oblika x 2 ≡a(mod strα), samo rješenja po modulu 8 djeluju kao početno rješenje: x≡±1(mod 8) i x≡±3(mod 8). Treba ih uporediti po modulu 16, zatim po modulu 32 i tako dalje do modula 2 α.

primjer:

Riješite poređenje x 2 ≡33 (mod 64)

64=26. Provjerimo da li originalno poređenje ima rješenje. 33≡1(mod 8), pa poređenje ima 4 rješenja.

Modulo 8 ova rješenja će biti: x≡±1(mod 8) i x≡±3(mod 8), što se može predstaviti kao x=±(1+4 t 1). Zamijenite ovaj izraz u poređenje po modulu 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)

Tada će rješenje poprimiti oblik x=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Zamijenite rezultirajuće rješenje u kongruenciju po modulu 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)

Tada će rješenje poprimiti oblik x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Zamijenite rezultirajuće rješenje u poređenje po modulu 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)

Tada će rješenje poprimiti oblik x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t 4). Dakle, po modulu 64, originalno poređenje ima četiri rješenja: x≡±17(mod 64)i x≡±49 (mod 64).

Sada razmotrite generalno poređenje: x 2 ≡a(mod m), (a,m)=1, - kanonska dekompozicija modula m. Prema teoremi iz 4. tačke §4, ovo poređenje je ekvivalentno sistemu

Ako je svako poređenje ovog sistema odlučivo, onda je cijeli sistem odlučiv. Nakon što smo pronašli rješenje svakog poređenja ovog sistema, dobijamo sistem poređenja prvog stepena, rješavanjem kojeg, koristeći kinesku teoremu o ostatku, dobijamo rješenje originalnog poređenja. Štaviše, broj različitih rješenja originalnog poređenja (ako je rješivo) je 2 k, ako je α=1, 2 k+1 ako je α=2, 2 k+2 ako je α≥3.

primjer:

Riješite poređenje x 2 ≡4 (mod 21).

Poređenje sa jednom nepoznatom x ima oblik

Gdje . Ako a n nije djeljivo sa m, onda se zove stepen poređenja.

Odluka poređenje je bilo koji cijeli broj x 0 , za koji

Ako X 0 zadovoljava poređenje, onda će, prema svojstvu 9 poređenja, ovo poređenje zadovoljiti sve cijele brojeve uporedive sa x 0 modulo m. Dakle, sva rješenja poređenja pripadaju istoj klasi modulo ostataka T, razmatraćemo kao jedno rešenje. Dakle, poređenje ima onoliko rješenja koliko ima elemenata kompletnog sistema ostataka koji ga zadovoljavaju.

Pozivaju se poređenja čiji su skupovi rješenja isti ekvivalentno.

2.2.1 Poređenja prvog stepena

Poređenje prvog stepena sa jednom nepoznatom X ima oblik

(2.2)

Teorema 2.4. Da bi poređenje imalo barem jedno rješenje, potrebno je i dovoljno da broj b podijeljeno sa GCD( a, m).

Dokaz. Prvo dokazujemo neophodnost. Neka d = GCD( a, m) I X 0 - rešenje za poređenje. Onda , odnosno razlika Oh 0 − b podijeljena T. Dakle, postoji cijeli broj q, Šta Oh 0 − b = qm. Odavde b= ah 0 − qm. I od tada d, kao zajednički djelitelj, dijeli brojeve A I T, tada su minuend i subtrahend podijeljeni sa d, i stoga b podijeljena d.

Sada dokažemo dovoljnost. Neka d- najveći zajednički djelitelj brojeva A I T, I b podijeljena d. Zatim, prema definiciji djeljivosti, postoje cijeli brojevi a 1 , b 1 ,T 1 , Šta .

Koristeći prošireni Euklid algoritam, nalazimo linearni prikaz broja 1 = gcd( a 1 , m 1 ):

za neke x 0 , y 0 . Oba dijela posljednje jednakosti množimo sa b 1 d:

ili, što je isto,

,

odnosno , i je rješenje poređenja. □

Primjer 2.10. Poređenje 9 X= 6 (mod 12) ima rješenje jer je gcd(9, 12) = 3 i 6 je deljivo sa 3. □

Primjer 2.11. Poređenje 6x= 9 (mod 12) nema rješenja jer gcd(6, 12) = 6 i 9 nije djeljivo sa 6. □

Teorema 2.5. Neka je kongruencija (2.2) odlučiva i d = GCD( a, m). Tada se skup rješenja poređenja (2.2) sastoji od d modulo klasa ostataka T, naime, ako X 0 je jedno od rješenja, onda su sva ostala rješenja

Dokaz. Neka X 0 je rješenje poređenja (2.2), tj. I , . Dakle, postoji takav q, Šta Oh 0 − b = qm. Zamjena sada u posljednju jednakost umjesto X 0 proizvoljno rješenje oblika, gdje, dobijamo izraz

, djeljivo sa m. □

Primjer 2.12. Poređenje 9 X=6 (mod 12) ima tačno tri rješenja pošto je gcd(9, 12)=3. Ova rješenja su: X 0 \u003d 2, x 0 + 4 \u003d 6, X 0 + 2∙4=10.□

Primjer 2.13. Poređenje 11 X=2 (mod 15) ima jedinstveno rješenje X 0 = 7 pošto gcd(11,15)=1.□

Hajde da pokažemo kako riješiti poređenje prvog stepena. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje kongruencije (2.2) može tražiti, na primjer, korištenjem Euklidovog algoritma. Zaista, koristeći prošireni Euklidski algoritam, broj 1 predstavljamo kao linearnu kombinaciju brojeva a I T:

Pomnožite obje strane ove jednačine sa b, dobijamo: b = abq + mrb, gdje abq - b = - mrb, to je a ∙ (bq) = b(mod m) I bq je rješenje poređenja (2.2).

Drugi način rješavanja je korištenje Ojlerove teoreme. Opet, pretpostavljamo da je GCD(a, T)= 1. Primjenjujemo Ojlerovu teoremu: . Pomnožite obje strane poređenja sa b: . Prepisivanje posljednjeg izraza kao , dobijamo da je to rješenje kongruencije (2.2).

Neka sada GCD( a, m) = d>1. Onda a = atd, m = mtd, gdje je gcd( A 1 , m 1) = 1. Osim toga, neophodno je b = b 1 d, da bi poređenje bilo razrješivo. Ako X 0 - rešenje za poređenje A 1 x = b 1 (mod m 1), i jedini, jer GCD( A 1 , m 1) = 1, dakle X 0 biće odluka i poređenje A 1 xd = db 1 (mod m 1), odnosno originalno poređenje (2.2). Odmori se d- 1 rješenje je pronađeno po teoremi 2.5.