Poređenje po modulu prirodnog broja. Rješavanje poređenja i njihova primjena Rješavanje poređenja

Poređenje sa jednom nepoznatom x izgleda kao

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

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

Ako X 0 zadovoljava poređenje, onda su, prema svojstvu 9 poređenja, svi cijeli brojevi uporedivi sa x 0 modulo m. Dakle, sva rješenja poređenja koja pripadaju istoj klasi ostatka po modulu T, mi ćemo to smatrati kao jedno rješenje. Dakle, poređenje ima onoliko rješenja koliko ima elemenata kompletnog sistema ostataka koji ga zadovoljavaju.

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

2.2.1 Poređenja prvog stepena

Poređenje prvog stepena sa jednom nepoznatom X izgleda kao

(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 takav 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 se minuend i subtrahend dijele sa d, i zbog toga b podijeljena d.

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

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

za neke x 0 , y 0 . Pomnožimo obje strane posljednje jednakosti sa b 1 d:

ili, šta je isto,

,

odnosno i predstavlja rešenje za poređenje. □

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 je gcd(6, 12) = 6, a 9 nije djeljivo sa 6. □

Teorema 2.5. Neka je poređenje (2.2) rješivo 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 - jedno od rješenja, onda su sva ostala rješenja

Dokaz. Neka X 0 - rješenje poređenja (2.2), tj I , . Dakle, postoji takva stvar q, Šta Oh 0 − b = qm. Sada zamijenite 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: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Primjer 2.13. Poređenje 11 X=2 (mod 15) ima jedinstveno rješenje X 0 = 7, budući da je GCD(11,15)=1.□

Pokazat ćemo vam kako riješiti poređenja prvog stepena. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje za poređenje (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žimo obje strane ove jednakosti sa b, dobijamo: b = abq + mrb, gdje abq - b = - mrb, to je a ∙ (bq) = b(mod m) I bq- rješenje poređenja (2.2).

Drugo rješenje je korištenje Ojlerove teoreme. Opet vjerujemo da 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 za poređenje (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, kako bi poređenje bilo razrješivo. Ako X 0 - rešenje za poređenje A 1 x = b 1 (mod m 1), i jedini, od GCD( A 1 , m 1) = 1, dakle X 0 biće rešenje 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.

Sadržaj.

Uvod

§1. Poređenje modula

§2. Svojstva poređenja

1. Svojstva poređenja nezavisnih od modula
2. Svojstva poređenja zavisna od modula

§3. Sistem odbitka

1. Potpuni sistem odbitaka
2. Smanjeni sistem odbitaka

§4. Ojlerova teorema i Fermat

1. Eulerova funkcija
2. Ojlerova teorema i Fermat

Poglavlje 2. Teorija poređenja sa varijablom

§1. Osnovni pojmovi vezani za rješavanje 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 stupnjeva

§5. Antiderivativni 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 razlomak

decimalni sistematski razlomak

Zaključak

Književnost

Uvod

U našim životima često se suočavamo s cijelim brojevima i problemima 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 po modulu m.

Reč "modul" dolazi od latinskog modula, što na ruskom znači "mera", "veličina".

Izjava “a je uporediva 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. Gausa “Aritmetičke studije”. 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 slučajevima kada je dovoljno u bilo kojem istraživanju znati brojeve tačne na višekratnike određenog broja.

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

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

Teza se sastoji od tri poglavlja, pri čemu je svako poglavlje podijeljeno na paragrafe, a paragrafi na paragrafe.

Prvo poglavlje iznosi opća pitanja 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 koncepte 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 jednom nepoznatom, poređenja viših stepena itd.

Treće poglavlje sadrži neke primjene teorije brojeva na školsku matematiku. Razmatraju se znaci djeljivosti, provjeravanje rezultata radnji i 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 je z prsten cijelih brojeva, m fiksni cijeli broj, a m·z skup svih cijelih brojeva koji su višekratnici m.

Definicija 1. Kaže se da su dva cijela broja a i b uporediva 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 djeljiv sa m.

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

Definirajmo 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 iste ostatke 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₂), odnosno a-b m ili a b (mod m).

Obrnuto, neka a b (mod m). To znači da 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, odnosno, kada se a podeli sa m, dobije se isti ostatak kao i kada se b podeli 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 identične ostatke kada se podijele s m nazivaju se jednaki ostaci ili uporedivi po modulu m.

Primjeri.

Imamo: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) je podijeljeno 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, stoga je naše poređenje netačno.

§2. Svojstva poređenja

1. Svojstva poređenja nezavisna od modula.

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

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

B) 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 na obje strane 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. Stoga a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) ê mz, odnosno a·c·d (mod m).

Posljedica. Obje strane poređenja mogu se podići na isti nenegativni cijeli broj: ako je 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: traženi 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+ =

Pošto je 27 1 (mod 13), onda 1+ 1+1·3+1·9 (mod 13).

itd.

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

Imamo: 1 (mod 24), dakle

1 (mod 24)

Dodajući 55 na obje strane poređenja, dobivamo:

(mod 24).

Imamo: (mod 24), dakle

(mod 24) za bilo koji k ê N.

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

1. Obje strane 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 kada se 196 podijeli 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. Obje strane poređenja i modul mogu se pomnožiti sa istim pozitivnim cijelim brojem.

Dokaz.

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

Primjer.

Odredite da li je vrijednost izraza cijeli broj.

Rješenje:

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

1 (mod 9)

31 (mod 27)

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

1. Obje strane poređenja mogu se podijeliti njihovim zajedničkim faktorom ako je kopriman modulu.

Dokaz.

Ako ca cb (mod m), odnosno 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 obje strane poređenja sa 3 dobijamo:

20 (mod 17).

Uopšteno govoreći, nemoguće je podijeliti obje strane poređenja brojem koji nije koprost sa modulom, jer se nakon dijeljenja mogu dobiti brojevi koji su neuporedivi s obzirom na dati modul.

Primjer.

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

1. Obje strane poređenja i modul mogu se podijeliti svojim zajedničkim djeliteljem.

Dokaz.

Ako ka kb (mod km), tada je k (a-b) podijeljeno 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 obje strane 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 poređenju po modulu m, pojedinačni pojmovi i faktori mogu biti zamijenjeni brojevima uporedivim po modulu m.

Istovremeno, treba napomenuti da se eksponenti pronađeni u poređenjima ne mogu zamijeniti na ovaj način: od

a n c(mod m) i n k(mod m) ne slijedi da a k s (mod m).

Svojstvo 11 ima niz važnih primjena. Konkretno, uz njegovu pomoć moguće je dati teorijsko opravdanje za znakove djeljivosti. Za ilustraciju, kao primjer, dat ćemo derivaciju testa djeljivosti sa 3.

Primjer.

Svaki 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. Potpuni sistem odbitaka.

Brojevi jednakih ostataka, ili, što je isto, uporedivi po modulu m, čine klasu brojeva po modulu m.

Iz ove definicije slijedi da svi brojevi u klasi odgovaraju istom ostatku r, a sve brojeve u klasi dobijamo ako, u obliku mq+r, učinimo da q prolazi kroz sve cijele brojeve.

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; na r> imamo ρ=r-m; konačno, ako je m paran i r=, tada se bilo koji od dva broja može uzeti kao ρ i -m= - .

Odaberemo iz svake klase ostataka po modulu T jedan po jedan broj. Dobijamo t cijeli brojevi: x 1,…, x m. Skup (x 1,…, x t) se zove kompletan sistem odbitaka po modulu m.

Pošto svaka klasa sadrži beskonačan broj ostataka, moguće je sastaviti beskonačan broj različitih kompletnih sistema ostataka za dati modul m, od kojih svaki sadrži t odbitaka.

Primjer.

Sastaviti nekoliko kompletnih sistema modulo dedukcija 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šći:

1. Kompletan sistem najmanje nenegativnih ostataka: 0, 1, t -1 U gornjem primjeru: 0, 1, 2, 3, 4. Ovaj sistem ostataka je jednostavan za kreiranje: potrebno je da zapišete sve nenegativne ostatke dobijene 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 apsolutno minimalnih odbitaka.U slučaju neparnog m, apsolutno najmanji ostaci su predstavljeni 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 osnovna svojstva kompletnog sistema ostataka.

Teorema 1 . Bilo koja kolekcija od m cijelih brojeva:

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

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

Dokaz.

1. Svaki od brojeva u kolekciji (1) pripada određenoj klasi.
2. Bilo koja dva broja x i i x j iz (1) su međusobno neuporedivi, tj. pripadaju različitim klasama.
3. U (1) ima m brojeva, tj. isti broj kao i modulo klase T.

x 1, x 2,…, x t - kompletan sistem odbitaka po modulu m.

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

Dokaz.

Hajde da razmotrimo

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

1. Svaki od brojeva u kolekciji (2) pripada određenoj 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 u (2) postoje dva broja takva da

ax i +b ax j + b (mod m), (i = j), onda bismo dobili ax i ax j (mod t). 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 uvjetu x i x j (mod t) na (i = j) , budući da je x 1, x 2, ..., x m - kompletan 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 - 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 u obliku 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, t) = (b, t).

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

Obrnuto, ako je m δ i b δ, tada 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 po T zove najveći zajednički djelitelj T i ova klasa odbitaka.

Definicija 2. Klasa ostatka a po modulu t naziva se koprimenom modulu 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 koprosta s modulom 6 .

Odaberimo po jedan broj iz svake klase ostataka koji je koprost sa modulom m. Dobijamo sistem odbitaka koji je dio kompletnog sistema odbitaka. Zovu jesmanjeni sistem ostataka po modulu m.

Definicija 3. Skup ostataka po modulu m, uzet po jedan iz svakog kojednog broja sa T klasa ostataka za ovaj modul naziva se redukovani sistem ostataka.

Iz definicije 3 slijedi metoda za dobivanje reduciranog sistema modulo ostataka T: potrebno je zapisati neki kompletan sistem ostataka i iz njega ukloniti sve ostatke koji nisu koprimarni sa m. Preostali skup odbitaka je redukovani sistem odbitaka. Očigledno se može sastaviti beskonačan broj sistema ostataka po modulu m.

Ako kao početni sistem uzmemo kompletan sistem najmanjih nenegativnih ili apsolutno najmanjih ostataka, tada se pomoću navedene metode dobija redukovani sistem najmanje nenegativnih ili apsolutno najmanjih ostataka po modulu m.

Primjer.

Ako je T = 8, tada je 1, 3, 5, 7 redukovani sistem najmanjih nenegativnih ostataka, 1, 3, -3, -1- redukovani sistem apsolutno najmanjih odbitaka.

Teorema 2.

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

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

Dokaz

A) Svaki broj u populaciji (1) pripada određenoj 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 koprostim po modulu m.
3. Ukupno (1) dostupno k brojeva, odnosno onoliko koliko redukovani sistem ostataka po modulu m treba da sadrži.

Dakle, skup brojeva(1) - smanjeni sistem modulo odbitaka T.

§4. Eulerova funkcija.

Ojlerove i Fermaove teoreme.

1. Eulerova funkcija.

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

Odaberimo kao predstavnike klasa modulo ostataka t brojevi 1, ..., t - 1, t. Tada je φ (t) - broj takvih brojeva koprostih sa 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 do 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 sa 12 . Ovo znači

φ(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 pretpostavljamo da je φ(1) = 1.

Pređimo na izračunavanje Eulerove funkcije.

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

Dokaz.

Odbici 1, 2, ..., p- 1 i samo su oni relativno prosti sa prostim brojem R. Stoga je φ (r) = r - 1.

2) Ako je t = p k - primarna snaga p, dakle

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

Dokaz.

Kompletan sistem modulo odbitaka 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 u slučaju kadaApodijeljenaR.Ali među brojevima 1, ... , strk -1 onRsamo brojevi su djeljivip, 2p, ... , str2 , ... RTo, čiji je broj jednakRTo: p = pk-1. To znači da su koprimarni sat = pToodmorRTo- Rk-1= strk-l(p-1)brojevi. Ovo dokazuje to

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

Teorema1.

Ojlerova funkcija je multiplikativna, odnosno za relativno proste 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 koprosti brojevi

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

Uredimo kompletan sistem odbitaka po modulutpasPXT -matrice

1 2 T

t +1 t +2 2t

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

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

ZbogTIPsu relativno prosti, onda brojXrecipročno samo satptada i samo kadaXrecipročno samo saTIXrecipročno samo saP. Ali brojkm+trecipročno samo saTako i samo akotrecipročno samo saT.Prema tome, brojevi koji su prosti sa m nalaze se u onim kolonama za kojetprolazi kroz redukovani sistem modulo ostatakaT.Broj takvih kolona je jednak φ(T).Svaka kolona predstavlja kompletan sistem odbitaka po moduluP.Iz ovih odbitaka φ(P)coprime withP.To znači da je ukupan broj brojeva koji su relativno prosti i saTi sa n, jednako φ(T)φ(n)

(φ (T)kolone, u svakoj od kojih se uzima φ(P)brojevi). Ovi brojevi, i samo oni, su jednakiitd.Ovo dokazuje to

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

Primjeri.

№1 . Dokažite valjanost sljedećih jednakosti

φ(4n) =

Dokaz.

№2 . Riješite 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 multiplikativnosti(m) imamo:

(m)=.

Ali prema formuli (1) nalazimo to

-1), i stoga

(3)

Jednakost (3) se može prepisati kao:

Zbog=m, onda(4)

Formula (3) ili, što je isto, (4) je ono što tražimo.

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 u nizu prirodnih brojeva postoji beskonačan skup prostih brojeva.

Rješenje:Uz pretpostavku da je broj prostih brojeva konačan skup, pretpostavljamo da je to- 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.

Hajde da izrazimo iz=2 , dobijamo, zamjena u

:

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

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

odgovor:x= 143

2. Ojlerova teorema i Fermat.

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

Ojlerova teorema.

Ako je cijeli broj a koprost sa m, onda

(1)

Dokaz.Neka

(2)

postoji redukovani sistem ostataka po modulu m.

Akoaonda je cijeli broj koprost sa m

(3)

Poređenje prvog stepena sa jednom nepoznatom ima oblik:

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

Riješite poređenje- znači pronalaženje svih vrijednosti x koje ga zadovoljavaju. Pozivaju se dva poređenja koja zadovoljavaju iste vrijednosti x ekvivalentan.

Ako je poređenje (1) bilo zadovoljno x = x 1, zatim (prema 49) svi brojevi uporedivi sa x 1, modulo m: x x 1 (mod m). Cijela ova klasa brojeva se smatra jedno rešenje. Takvim sporazumom može se izvući sljedeći zaključak.

66.C poravnanje (1) će imati onoliko rješenja koliko je ostataka kompletnog sistema koji ga zadovoljavaju.

Primjer. Poređenje

6x– 4 0 (mod 8)

Među brojevima 0, 1, 2, 3, 4, 5, 6, 7, dva broja zadovoljavaju kompletan sistem ostataka po modulu 8: 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 pomeranjem 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 zadovoljavaju. Ali kada x prolazi kroz kompletan sistem modulo ostataka T, To Oh prolazi kroz kompletan sistem odbitaka (od 60). Dakle, za jednu i samo jednu vrijednost X, preuzeto iz kompletnog sistema, Oh biće uporedivo sa b. dakle,

67. Kada je (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 podijeljena d, inače je poređenje (2) nemoguće za bilo koji cijeli broj x . Pretpostavljajući dakle b višestruki d, stavimo a = a 1 d, b = b 1 d, m = m 1 d. Tada će poređenje (2) biti ekvivalentno ovom (skraćeno sa 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 – najmanji nenegativni ostatak ovog rješenja po modulu m 1 , tada su svi brojevi x , formiranje ovog rješenja nalaze se u obliku

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

Po modulu m 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 modulo ostaci 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 odluke.

Dobijamo teoremu:

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

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

Proširivanje relacije u kontinuirani razlomak m:a,

i gledajući posljednja dva podudarna razlomka:

prema svojstvima kontinuiranih razlomaka (prema 30 ) imamo

Dakle, poređenje ima rješenje

pronaći, š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.

Podijelivši obje strane poređenja i modul sa 3, dobijamo poređenje

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

koje prvo moramo da rešimo. Imamo

q
P 3

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

x–26 ∙ 25 99 (mod 107).

Dakle, rješenja za poređenje (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 datom modulu

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

Proračun recipročnih veličina po modulu određene vrijednosti može se izvršiti rješavanjem poređenja prvog stepena sa jednom nepoznatom, u kojoj x broj prihvaćen a′.

Da nađem rešenje za poređenje

a∙x≡ 1 (mod m),

Gdje ( a,m)= 1,

možete koristiti Euclid algoritam (69) ili Fermat-Eulerovu teoremu, 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 dat 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 odnosno znači 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 istovremeno leže 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), Dekartov proizvod skupova A I B(tj. skup parova oblika ( a, b), Gdje a A, b B). Preko | A| snaga 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) se podudara s trećim elementom iz G: a b.

Puno elemenata G sa operacijom se zove grupa, ako su ispunjeni sljedeći uslovi.

Razmotrimo sistem poređenja

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

Teorema 1. Neka je M = najmanji zajednički višekratnik brojeva m1,m2,…,ms. Ako a zadovoljava sistem (2), tada bilo koji broj iz klase a po modulu M zadovoljava ovaj sistem.

Dokaz. Neka je b€ klasa a. Pošto je a ≡ b(mod M), onda je a ≡b(mod m), i= 1,2,...,s (svojstvo poređenja 16). Prema tome, b, kao i a, zadovoljava svako poređenje sistema, što dokazuje teoremu. Stoga je prirodno smatrati da je rješenje sistema (2) klasa po modulu M.

Definicija. Rješenje sistema poređenja(2) je klasa brojeva po modulu M = koji zadovoljavaju svako poređenje sistema.

12. Odmah primijetimo da neparni brojevi ne zadovoljavaju drugo poređenje. Uzimajući parne brojeve iz kompletnog sistema ostataka po modulu 12, direktnom verifikacijom smo uvereni da brojevi 2, -2, 6 zadovoljavaju 2. poređenje, a sistem ima dva rešenja: x ≡ 2(mod l2), x ≡ - 2 (mod 12).

Razmotrimo sistem poređenja 1. stepena (3)

Teorema 2. Neka je d=(m1,m2), M = .

Ako c1 - c2 nije deljivo sa d, onda sistem (3) nema rešenja.

Ako je (c1 -c2):d, onda sistem (3) ima jedno rješenje - klasu po modulu M.

Dokaz. Iz prvog poređenja x = c1+m1t, t€Z. Zamijenite u 2. poređenje: s1+ m1t ≡ c2(mod m2) ili

m1t ≡ c2-cl (mod m2). Ovo poređenje ima rješenje samo ako (c2 – c1): d.

A rješenje je klasa po modulu (teorema 4 iz §2).

Neka je rješenje , odnosno gdje je k€Z.

M== , odnosno x≡c1+m1t0(mod M) je rješenje

Primjeri.

1. :2, sistem ima jednu klasu rješenja po modulu 24. Iz 1. poređenja x =2+6t. Zamjenom x u 2. poređenje, imamo: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, odnosno x≡-4(mod 24).

2. 7-3 nije deljivo sa 3, sistem nema rešenja.

Zaključak 1. Sistem poređenja (4)

Ili nema rješenja, ili ima jedno rješenje - klasu po modulu M=.

Dokaz. Ako sistem prva dva poređenja nema rješenja, onda (4) nema rješenja. Ako ima rješenje x ≡ a(mod), onda dodavanjem trećeg poređenja sistema ovom poređenju, opet dobijamo sistem oblika (3), koji ili ima jedno rješenje ili nema rješenja. Ako ima rješenje, nastavit ćemo ovim putem dok ne iscrpimo sva poređenja sistema (4). Ako postoji rješenje, onda je to klasa po modulu M.

Komentar. Ovdje se koristi LCM svojstvo: =.

Zaključak 2. Ako su m1,m2,…,ms parno prosti, onda sistem (4) ima jedno rješenje - modulo klasa M=m1m2…ms.

primjer:

Pošto su moduli u paru relativno jednostavni, sistem ima jedno rešenje - modulo klasa 105 = 5*3*7. Od prvog poređenja

Zamjenjujemo u drugo poređenje: 2 +5t≡ 0(mod 3) ili 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Zamenimo u trećem poređenju:

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

Hajde da se upoznamo drugi metoda rješavanja ovog sistema, (koristimo činjenicu da sistem ima jedno rješenje.) Pomnožimo oba dijela i modul prvog poređenja sa 21, drugog sa 35, a trećeg sa 15: iz zbira prvo i treće oduzimamo drugi:

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

Razmotrimo sada sistem poređenja prvog stepena opšteg oblika

Ako neko poređenje ovog sistema nema rješenja, onda sistem nema rješenja. Ako je svako poređenje sistema (5) rješivo, tada ga rješavamo za x i dobijamo ekvivalentni sistem oblika (4):

Gdje (teorema 4, §2).

Prema rezultatu 1, sistem ili nema rješenja ili ima jedno rješenje.

primjer:

Nakon što smo riješili svako poređenje sistema, dobijamo ekvivalentni sistem

Ovaj sistem ima jedno rešenje - klasu modulo 105. Pomnožimo prvo poređenje i modul sa 3, a drugo sa 35, dobijamo

Oduzimanjem prvog poređenja pomnoženog sa 11 od drugog poređenja, dobijamo 2x ≡-62(modl05), od čega je x ≡ -31(modl05).

Problemi koji se svode na razmatranje sistema poređenja 1. stepena razmatrani su u aritmetici kineskog matematičara Sun Tzua, koji je živio oko početka naše ere. Njegovo pitanje je bilo postavljeno u sljedećem obliku: nađi broj koji daje date ostatke kada se podijeli datim brojevima. Također daje rješenje ekvivalentno sljedećoj teoremi.

Teorema (kineska teorema o ostatku). Neka su m1,m2,…,ms parno prosti brojevi, M = mlm2...ms, β1, β2,…, β izabrani tako da

Zatim rješenje sistema

Izgledaće kao x≡x0(mod M).

Dokaz. Pošto dobijamo x0≡

Na sličan način provjeravamo da x0≡c2(mod m2),..., x0≡cs(mod ms), odnosno da x0 zadovoljava sve

poređenja sistema.

10. Poređenja 1. stepena. Nesigurne jednačine

§ 2. Poređenja 1. stepena. Nesigurne jednačine

Poređenje 1. stepena može se svesti na oblik ax≡b(mod m).

Teorema 4. Ako je (a,m) = 1, tada poređenje ax ≡b(mod m) (2) ima jedinstveno rješenje.

Dokaz. Uzmimo 0,1,2,...,m-1 - kompletan sistem ostataka po modulu m. Pošto je (a,m) = 1, onda je 0,a,2a,...,(m-1)a takođe kompletan sistem ostataka (Teorema 3, §2, Poglavlje 2.). Sadrži jedan i samo jedan broj uporediv sa b po modulu m (koji pripada istoj klasi kao b). Neka je ovo ax 0, odnosno ax 0 € klasa b ili ax 0 ≡b(mod m). x ≡x 0 (mod m) je jedino rješenje za (2). Teorema je dokazana.

Teorema 5. Ako je (a, m)= 1, onda je rješenje za poređenje ax≡b(mod m) klasa x 0 ≡a φ (m)-1 b(mod m).

Dokaz. Pošto je (a,m) = 1, onda je po Eulerovom principu a φ(m) ≡1(mod m). Lako je vidjeti da je x 0 ≡a φ (m)-1 b (mod m) rješenje za poređenje (2). Zaista, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Iz teoreme 4 slijedi da je ovo rješenje jedinstveno.

Hajde da razmotrimo metode poređenja rješenja ax ≡b(mod m).

1. Metoda odabira. Uzimajući kompletan sistem ostataka po modulu m, biramo brojeve koji zadovoljavaju poređenje.

2. Korištenje Ojlerove teoreme (Teorema 5).

3. Metoda konverzije koeficijenata. Moramo pokušati transformirati koeficijente tako da se desna strana može podijeliti sa koeficijentom od x. Transformacije o kojima je riječ su sljedeće: zamjena koeficijenata s apsolutno najmanjim ostacima, zamjena broja b brojem uporedivim po apsolutnoj vrijednosti (dodavanje broja koji je višekratnik apsolutne vrijednosti) tako da je potonji djeljiv sa a, pomicanje od a i b do drugih brojeva uporedivih s njima, koji bi imali zajednički djelitelj, itd. U ovom slučaju koristimo svojstva poređenja i teoreme o ekvivalentnim poređenjima na osnovu njih.

1) 223x ≡ 115 (mod ll).

Prvo zamjenjujemo koeficijente sa najmanjim odbicima apsolutne vrijednosti: 3h ≡ 5(mod 11). Ako koristimo teoremu

Euler, dakle

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

Međutim, lakše je pretvoriti koeficijente. Zamijenimo poređenje s ekvivalentnim dodavanjem na desnu stranu broja koji je višekratnik modula:

3x ≡ 5 + 22 (mod 11). Deljenjem obe strane brojem 3, koprostornim sa modulom, dobijamo x ≡ 9(mod l1).

2) 111x≡ 8 (mod 34).

Koristimo metodu konverzije koeficijenata.

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

Teorema 6. Ako (a, m) = d i b nije deljivo sa d, onda poređenje (1) nema rešenja.

Dokaz (kontradikcijom). Neka je klasa x 0 rješenje, odnosno ax 0 ≡b (mod m) ili (ax 0 -b):m, i, prema tome, (ax 0 -b):d. Ali a:d, zatim b:d je kontradikcija. Stoga poređenje nema rješenja.

Teorema 7. Ako je (a,m)= d, d>1, b:d, onda poređenje(1) ima d

rješenja koja čine jednu klasu modulo ostataka i nalaze se po formulama

Gdje With zadovoljava pomoćno poređenje

Komentar. Prema teoremi, poređenje (1) se rješava na sljedeći način.

1) Uvjerili smo se da je (a,m) = d, d> 1 i b:d, oba dijela u poređenjima (2) podijelimo sa d i dobijemo pomoćno poređenje a 1 x≡b 1 (mod m 1) , gdje . Poređenje ima samo jedno rešenje. Neka je klasa c rješenje.

2) Napišite odgovor x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1) m 1 (mod m).

Dokaz. Pomoćno poređenje prema teoremi 2(3) je ekvivalentno originalnom poređenju (2). Budući da ( 1, onda pomoćno poređenje ima jedinstveno rješenje - klasu modulo m 1 = . Neka je x≡c(mod m 1) rješenje. Klasa brojeva c po modulu m 1 dijeli se na d klase po modulu m: .

Zaista, bilo koji broj iz klase x0 po modulu m 1 ima oblik x 0 +m 1 t. Podijelite t sa ostatkom sa d: t = dq +r, gdje je 0≤r

Dakle, poređenje (1) ima d rješenja po modulu m: x0, x0+m1,..., x0 +(d-1)m1 (horizontalne linije na vrhu)

Primjeri.

1) 20x≡ 15 (mod 108). Pošto (20,108) = 4 i 15 nije deljivo sa 4, nema rešenja.

2) 20x≡ 44 (mod 108). (20,108) = 4 i 44:4, dakle poređenje ima četiri rješenja. Podijeleći oba dijela i modul sa 4, dobijamo:

5h≡11(mod 27); 5 x≡11-81 ≡ -70 (mod27), x ≡ -14 ≡ 13 (mod 27). Tada je x≡13 + 27r(mod 108), gdje je r = 0,1,2,3. I jj

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

Primjena teorije poređenja na rješavanje nesigurnih jednačina

Razmotrimo neodređenu ili, kako se drugačije naziva, Diofantovu jednačinu prvog stepena sa dvije nepoznate ax + by = c, gdje je a, b, c € Z. Ovu jednačinu trebate riješiti u cijelim brojevima. Ako (a,b)=d i c nije deljivo sa d, onda je očigledno da poređenje nema rešenja u celim brojevima. Ako je c deljivo sa d, onda podelite obe strane jednačine sa d. Stoga je dovoljno razmotriti slučaj kada je (a, b) =1.

Pošto se ax razlikuje od c za višekratnik od b, onda je ax ≡ c(mod b) (bez gubitka opštosti možemo pretpostaviti da je b > 0). Rješavajući ovo poređenje, dobijamo x ≡x1 (mod b) ili x=x1+bt, gdje je t€Z. Za određivanje odgovarajućih vrijednosti y imamo jednadžbu a(x1 + bt) + by = c, iz koje

Štaviše, - je cijeli broj, to je parcijalna vrijednost nepoznate y, koja odgovara x1 (ispada, kao i x1, pri t = 0). A opšte rješenje jednačine će imati oblik sistema jednačina x=x1+bt, y=y1-at, gdje je t bilo koji cijeli broj.

Bilješka da 1) jednačina ax + by = c može biti riješena počevši od poređenja sa ≡ c(mod a), pošto se by razlikuje od c za višekratnik a;

2) pogodnije je odabrati kao modul najmanji modul a i b.

Primjer, 50x – 42y= 34.

Podijelite obje strane jednačine sa 2.

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

x ≡ -1 (mod 21), odnosno x=-1+21t, t€Z. Zamenimo pronađeni x u jednačinu. 25(-1 + 21t)- 21y= 17; 21u =-42 + 25* 21t i u =-2 + 25t.