Usporedba po modulu prirodnog broja. Rješavanje usporedbi i njihova primjena Rješavanje usporedbi

Usporedba s jednom nepoznatom x izgleda kao

Gdje . Ako a n nije djeljiv sa m, tako se zove stupanj usporedbe.

Odlukom usporedba je bilo koji cijeli broj x 0 , za koji

Ako x 0 zadovoljava usporedbu, tada, prema svojstvu 9 usporedbi, svi cijeli brojevi usporedivi s x 0 modulo m. Stoga sve usporedne otopine koje pripadaju istoj klasi ostataka modulo T, smatrat ćemo ga jednim rješenjem. Dakle, usporedba ima onoliko rješenja koliko ima elemenata cjelovitog sustava ostataka koji je zadovoljavaju.

Usporedbe čiji se skupovi rješenja podudaraju nazivaju se ekvivalent.

2.2.1 Usporedbe prvog stupnja

Usporedba prvog stupnja s jednom nepoznatom x izgleda kao

(2.2)

Teorem 2.4. Da bi usporedba imala barem jedno rješenje, potrebno je i dovoljno da broj b podijeljeno s GCD( a, m).

Dokaz. Prvo dokazujemo nužnost. Neka d = GCD( a, m) I x 0 - rješenje usporedbe. Zatim , odnosno razlika Oh 0 − b podjeljeno sa T. Dakle, postoji takav cijeli broj q, Što Oh 0 − b = qm. Odavde b= ah 0 − qm. I od d, kao zajednički djelitelj, dijeli brojeve A I T, tada se minuend i subtrahend dijele sa d, i stoga b podjeljeno sa d.

Sada dokažimo dostatnost. Neka d- najveći zajednički djelitelj brojeva A I T, I b podjeljeno sa d. Tada, prema definiciji djeljivosti, postoje sljedeći cijeli brojevi a 1 , b 1 ,T 1 , Što .

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

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

ili, što je isto,

,

odnosno i rješenje je usporedbe. □

Primjer 2.10. Usporedba 9 x= 6 (mod 12) ima rješenje budući da je gcd(9, 12) = 3 i 6 djeljivo s 3. □

Primjer 2.11. Usporedba 6x= 9 (mod 12) nema rješenja, budući da je gcd(6, 12) = 6, a 9 nije djeljivo sa 6. □

Teorem 2.5. Neka je usporedba (2.2) rješiva ​​i d = GCD( a, m). Tada se skup usporednih rješenja (2.2) sastoji od d modulo rezidualne klase T, naime ako x 0 - jedno od rješenja, onda su sva ostala rješenja

Dokaz. Neka x 0 - rješenje usporedbe (2.2), tj I , . Dakle, postoji takva stvar q, Što Oh 0 − b = qm. Sada zamjenjujemo u posljednju jednakost umjesto x 0 proizvoljno rješenje oblika, gdje, dobivamo izraz

, djeljiv sa m. □

Primjer 2.12. Usporedba 9 x=6 (mod 12) ima točno tri rješenja, jer gcd(9, 12)=3. Ova rješenja: x 0 = 2, x 0 + 4 = 6, x 0 + 2∙4=10.□

Primjer 2.13. Usporedba 11 x=2 (mod 15) ima jedinstveno rješenje x 0 = 7, jer GCD(11,15)=1.□

Pokazat ćemo vam kako riješiti usporedbe prvog stupnja. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje usporedbe (2.2) može tražiti, na primjer, pomoću Euklidovog algoritma. Doista, koristeći prošireni Euklidski algoritam, predstavljamo broj 1 kao linearnu kombinaciju brojeva a I T:

Pomnožimo obje strane ove jednakosti s b, dobivamo: b = abq + mrb, gdje abq - b = - mrb, to je a ∙ (bq) = b(mod m) I bq- rješenje usporedbe (2.2).

Drugo rješenje je korištenje Eulerovog teorema. Opet vjerujemo da GCD(a, T)= 1. Primjenjujemo Eulerov teorem: . Pomnožite obje strane usporedbe s b: . Prepisivanje posljednjeg izraza kao , dobivamo da je to rješenje usporedbe (2.2).

Neka sada GCD( a, m) = d>1. Zatim a = atd, m = mtd, gdje je GCD( A 1 , m 1) = 1. Osim toga potrebno je b = b 1 d, kako bi usporedba bila razrješiva. Ako x 0 - rješenje usporedbe A 1 x = b 1 (mod m 1), i jedini, od GCD( A 1 , m 1) = 1, tada x 0 bit će rješenje i usporedba A 1 xd = db 1 (mod m 1), odnosno izvorna usporedba (2.2). Odmor d- 1 rješenja se nalaze prema teoremu 2.5.

Sadržaj.

Uvod

§1. Modulo usporedba

§2. Svojstva usporedbe

1. Svojstva usporedbe neovisna o modulu
2. Svojstva usporedbi ovisna o modulu

§3. Sustav odbitka

1. Potpuni sustav odbitaka
2. Smanjeni sustav odbitaka

§4. Eulerov teorem i Fermat

1. Eulerova funkcija
2. Eulerov teorem i Fermat

2. Poglavlje. Teorija usporedbi s varijablom

§1. Osnovni pojmovi vezani uz rješavanje usporedbi

1. Korijeni usporedbi
2. Ekvivalencija usporedbi
3. Wilsonov teorem

§2. Usporedbe prvog stupnja i njihova rješenja

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

§3. Sustavi usporedbi 1. stupnja s jednom nepoznanicom

§4. Podjela usporedbi viših stupnjeva

§5. Antiderivacijski korijeni i indeksi

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

Poglavlje 3. Primjena teorije usporedbi

§1. Znakovi djeljivosti

§2. Provjera rezultata računskih operacija

§3. Pretvorba običnog razlomka u konačni razlomak

decimalni sustavni razlomak

Zaključak

Književnost

Uvod

U životu se često suočavamo s cijelim brojevima i problemima vezanim uz njih. U ovom radu razmatram teoriju usporedbe cijelih brojeva.

Dva cijela broja čija je razlika višekratnik zadanog prirodnog broja m nazivaju se usporedivim po modulu m.

Riječ "modul" dolazi od latinske riječi modulus, što na ruskom znači "mjera", "veličina".

Izjava "a je usporedivo s b po modulu m" obično se piše kao ab (mod m) i naziva se usporedbom.

Definicija usporedbe formulirana je u knjizi K. Gaussa “Aritmetičke studije”. Ovo djelo, napisano na latinskom jeziku, počelo se tiskati 1797. godine, ali je knjiga objavljena tek 1801. godine zbog činjenice da je tiskarski proces u to vrijeme bio izuzetno naporan i dugotrajan. Prvi dio Gaussove knjige zove se: “O usporedbi brojeva općenito”.

Usporedbe su vrlo prikladne za korištenje u slučajevima kada je dovoljno znati u bilo kojem istraživanju brojeve točne do višekratnika određenog broja.

Na primjer, ako nas zanima kojom znamenkom završava kub cijelog broja a, tada je dovoljno da znamo a samo do višekratnika broja 10 i možemo koristiti usporedbe modulo 10.

Svrha ovog rada je razmatranje teorije usporedbi i proučavanje osnovnih metoda rješavanja usporedbi s nepoznanicama, kao i proučavanje primjene teorije usporedbi na školsku matematiku.

Diplomski rad sastoji se od tri poglavlja, pri čemu je svako poglavlje podijeljeno na odlomke, a odlomci na odlomke.

Prvo poglavlje ocrtava opća pitanja teorije usporedbi. Ovdje razmatramo koncept modulo usporedbe, svojstva usporedbi, potpuni i reducirani sustav ostataka, Eulerovu funkciju, Eulerov i Fermatov teorem.

Drugo poglavlje posvećeno je teoriji usporedbi s nepoznatim. Ocrtava osnovne pojmove vezane uz rješavanje usporedbi, razmatra metode za rješavanje usporedbi prvog stupnja (metoda odabira, Eulerova metoda, metoda Euklidovog algoritma, metoda upornih razlomaka, korištenje indeksa), sustave usporedbi prvog stupnja. s jednom nepoznatom, usporedbe viših stupnjeva itd. .

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

Izlaganje teorijskog gradiva popraćeno je velikim brojem primjera koji otkrivaju bit uvedenih pojmova i definicija.

Poglavlje 1. Opća pitanja teorije usporedbi

§1. Modulo usporedba

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 usporediva po modulu m ako m dijeli a-b.

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

Uvjet a b (mod m) znači da je a-b djeljivo s m.

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

Definirajmo da se relacija usporedivosti modulo m podudara s relacijom usporedivosti modulo (-m) (djeljivost s m je ekvivalentna djeljivosti s –m). Stoga, bez gubitka općenitosti, možemo pretpostaviti da je m>0.

Primjeri.

Teorema. (znak usporedivosti duhovnih brojeva po modulu m): Dva cijela broja a i b su usporedivi po modulu m ako i samo ako a i b imaju iste ostatke kada se dijele s m.

Dokaz.

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

B=mq₂+r, (2)

Gdje je 0≤r≥m.

Oduzmemo li (2) od (1), dobivamo 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)

Podijelite b s m; dobijemo b=mq+r u (3), imat ćemo a=m(q+t)+r, odnosno kod dijeljenja a s m dobiva se isti ostatak kao i kod dijeljenja b s 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 dijele s m nazivaju se jednaki ostaci ili usporedivi modulo m.

Primjeri.

Imamo: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) je podijeljeno s m => naša je usporedba točna.

1. Dokažite da su sljedeće usporedbe netočne:

Ako su brojevi usporedivi po modulu m, onda oni imaju isti gcd s njim.

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

GCD(4,10) = 2, GCD(25,10) = 5, stoga je naša usporedba netočna.

§2. Svojstva usporedbe

1. Svojstva usporedbi neovisna o modulu.

Mnoga svojstva usporedbi slična su svojstvima jednakosti.

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

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

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

Dokaz.

Po uvjetu m/(a-b) i m/ (c-d). Prema tome, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Primjeri.

Nađi ostatak pri dijeljenju u 13.

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

a-c b-d (mod m).

Dokaz.

Po uvjetu m/(a-b) i m/(c-d). Prema tome, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (posljedica svojstava 1, 2, 3). Možete dodati isti cijeli broj na obje strane usporedbe.

Dokaz.

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

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

a·c·d (mod m).

Dokaz.

Po uvjetu, a-b ê mz, c-d ê mz. Prema tome 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 usporedbe mogu se podići na istu nenegativnu cjelobrojnu potenciju: ako je ab (mod m) i s je nenegativan cijeli broj, tada je a s b s (mod m).

Primjeri.

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

2 -1 (mod 3)

5 -1 (mod 3), zatim

- · 1-1 0 (mod 13)

Odgovor: traženi ostatak je nula, a A je djeljiv s 3.

Riješenje:

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

1+ =1+ 1+ =

Budući da je 27 1 (mod 13), onda je 1+ 1+1·3+1·9 (mod 13).

itd.

3. Odredi ostatak kod dijeljenja s ostatkom broja u 24.

Imamo: 1 (mod 24), dakle

1 (mod 24)

Dodavanjem 55 na obje strane usporedbe, dobivamo:

(izmjena 24).

Imamo: (mod 24), dakle

(mod 24) za bilo koje k ê N.

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

1. Obje strane usporedbe mogu se pomnožiti istim cijelim brojem.

2.Svojstva usporedbi ovisno o modulu.

Dokaz.

Budući da je a b (mod t), tada (a - b) t. A budući da je t n , zatim zbog tranzitivnosti relacije djeljivosti(a - b n), odnosno a b (mod n).

Primjer.

Pronađite ostatak kada je 196 podijeljeno sa 7.

Riješenje:

Znajući da 196= , možemo napisati 196(izmjena 14). Iskoristimo prethodno svojstvo, 14 7, dobivamo 196 (mod 7), odnosno 196 7.

1. Obje strane usporedbe i modul mogu se pomnožiti 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, odnosno ac bc (mod mc).

Primjer.

Odredite je li vrijednost izraza cijeli broj.

Riješenje:

Predstavimo razlomke u obliku usporedbi: 4(mod 3)

1 (izmjena 9)

31 (mod. 27)

Zbrojimo ove usporedbe termin po termin (svojstvo 2), dobit ćemo 124(mod 27) Vidimo da 124 nije cijeli broj djeljiv sa 27, otuda značenje izrazatakođer nije cijeli broj.

1. Obje strane usporedbe mogu se podijeliti svojim zajedničkim faktorom ako je isti prost s modulom.

Dokaz.

Ako je ca cb (mod m), odnosno m/c(a-b) i broj S međusobno prosti s m, (c,m)=1, tada m dijeli a-b. Stoga, a b (mod t).

Primjer.

60 9 (mod 17), nakon dijeljenja obje strane usporedbe s 3 dobivamo:

20 (izmjena 17).

Općenito govoreći, nemoguće je obje strane usporedbe podijeliti brojem koji nije istoprost s modulom, jer se nakon dijeljenja mogu dobiti brojevi koji su neusporedivi s obzirom na dati modul.

Primjer.

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

1. Obje strane usporedbe i modula mogu se podijeliti svojim zajedničkim djeliteljem.

Dokaz.

Ako ka kb (mod km), tada je k (a-b) podijeljeno s km. Dakle, a-b je djeljivo s 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. Prema uvjetu a b (mod t), dakle

a k b k (mod m) za k = 0, 1, 2, …,n. Množenje obje strane svake od rezultirajućih n+1 usporedbi s c n-k, dobivamo:

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

Zbrajanjem zadnjih usporedbi dobivamo: 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 usporedbi po modulu m, pojedinačni članovi i faktori mogu se zamijeniti brojevima usporedivim po modulu m.

Istodobno, treba napomenuti da se eksponenti koji se nalaze u usporedbama ne mogu zamijeniti na ovaj način: od

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

Svojstvo 11 ima niz važnih primjena. Konkretno, uz njegovu pomoć moguće je dati teoretsko opravdanje za znakove djeljivosti. Za ilustraciju, kao primjer, navest ćemo izvođenje testa djeljivosti s 3.

Primjer.

Svaki prirodni broj N može se prikazati kao sustavni broj: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

Promotrimo 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 bio djeljiv s 3, potrebno je i dovoljno da je zbroj znamenki tog broja djeljiv s 3.

§3. Sustavi odbitka

1. Potpuni sustav odbitaka.

Jednaki preostali brojevi, ili, što je isto, usporedivi po modulu m, tvore klasu brojeva po modulu m.

Iz ove definicije slijedi da svim brojevima u klasi odgovara isti ostatak r, a sve brojeve u klasi dobivamo ako u obliku mq+r natjeramo q da prođe kroz sve cijele brojeve.

Prema tome, s 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. Dobiveni ostatak pri q=0, jednak ostatku r, naziva se najmanji nenegativni ostatak.

Ostatak ρ, najmanji po apsolutnoj vrijednosti, naziva se apsolutno najmanji ostatak.

Očito, 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= - .

Izaberimo iz svake klase ostataka modulo T jedan po jedan broj. Dobivamo t cijelih brojeva: x 1,…, x m. Skup (x 1,…, x t) se zove potpuni sustav odbitaka po modulu m.

Budući da svaka klasa sadrži beskonačan broj ostataka, moguće je sastaviti beskonačan broj različitih potpunih sustava ostataka za dati modul m, od kojih svaki sadrži t odbici.

Primjer.

Sastavite nekoliko cjelovitih sustava modulo odbitaka T = 5. Imamo klase: 0, 1, 2, 3, 4.

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

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

Kreirajmo nekoliko cjelovitih sustava 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 sustav najmanje nenegativnih ostataka: 0, 1, t -1 U gornjem primjeru: 0, 1, 2, 3, 4. Ovaj sustav ostataka je jednostavan za kreiranje: trebate zapisati sve nenegativne ostatke dobivene dijeljenjem s m.
2. Kompletan sustav najmanje pozitivnih ostataka(od svake klase uzima se najmanji pozitivni odbitak):

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

1. Kompletan sustav apsolutno minimalnih odbitaka.U slučaju neparnog m, apsolutno najmanji ostaci prikazani su jedan pored drugog.

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

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

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

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

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

Razmotrimo sada osnovna svojstva cjelovitog sustava ostataka.

Teorem 1 . Bilo koja zbirka od m cijelih brojeva:

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

u paru neusporediv po modulu m, tvori potpuni sustav ostataka po modulu m.

Dokaz.

1. Svaki od brojeva u zbirci (1) pripada određenoj klasi.
2. Bilo koja dva broja x i i x j iz (1) međusobno su neusporedivi, tj. pripadaju različitim klasama.
3. U (1) ima m brojeva, tj. onoliko koliko ima modulo klasa T.

x 1, x 2,…, x t - potpuni sustav odbitaka po modulu m.

Teorem 2. Neka je (a, m) = 1, b - proizvoljni cijeli broj; onda ako x 1, x 2,…, x t je potpuni sustav ostataka po modulu m, tada je zbirka brojeva ax 1 + b, sjekira 2 + b,…, sjekira m + b je također potpuni sustav ostataka po modulu m.

Dokaz.

Razmotrimo

Sjekira 1 + b, sjekira 2 + b,…, sjekira m + b (2)

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

Doista, ako su u (2) bila dva broja takva da

ax i +b ax j + b (mod m), (i = j), tada bismo dobili ax i ax j (mod t). Budući da (a, t) = 1, tada svojstvo usporedbi može smanjiti oba dijela usporedbe za A . Dobivamo 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 - cjelovit sustav odbitaka.

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

Dakle, sjekira 1 + b, sjekira 2 + b,…, sjekira m + b - potpuni sustav ostataka po modulu m.

Primjer.

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

Uzmimo neki potpuni sustav ostataka modulo 10, na primjer: 0, 1, 2,…, 9. Sastavimo brojeve oblika sjekira + b. Dobivamo: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Rezultirajući skup brojeva je potpuni sustav ostataka modulo 10.

1. Zadani sustav odbitaka.

Dokažimo sljedeći teorem.

Teorem 1.

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

Dokaz.

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

Doista, neka je δ zajednički djelitelj a i m, tada je aδ, m δ. Budući da je a = b + mt, tada je b=a-mt, dakle bδ. Dakle, svaki zajednički djelitelj brojeva a i m je zajednički djelitelj brojeva m i b.

Obrnuto, ako je m δ i b δ, tada je a = b +mt je djeljiv sa δ, pa je stoga svaki zajednički djelitelj od m i b zajednički djelitelj od a i m. Teorem je dokazan.

Definicija 1. Najveći zajednički djelitelj modula t i bilo koji broj a iz ove klase odbitaka po T koji se zove najveći zajednički djelitelj T i ova klasa odbitaka.

Definicija 2. Klasa rezidua a modulo t koji se naziva koprost 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 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 istoprosta s modulom 6 .

Odaberimo jedan broj iz svake klase ostataka koji je jednakoprost s modulom m. Dobivamo sustav odbitaka koji je dio cjelovitog sustava odbitaka. Zovu jereducirani sustav ostataka po modulu m.

Definicija 3. Skup ostataka po modulu m, uzet po jedan iz svakog koprosta s T klasa ostataka za ovaj modul naziva se reducirani sustav ostataka.

Iz definicije 3 slijedi metoda za dobivanje reduciranog sustava modulo ostataka T: potrebno je zapisati neki cjeloviti sustav ostataka i iz njega ukloniti sve ostatke koji nisu koprimi s m. Preostali skup odbitaka je smanjeni sustav odbitaka. Očito se može sastaviti beskonačno mnogo sustava ostataka po modulu m.

Ako kao početni sustav uzmemo potpuni sustav najmanje nenegativnih ili apsolutno najmanjih ostataka, tada ćemo navedenom metodom dobiti reducirani sustav najmanje nenegativnih ili apsolutno najmanjih ostataka po modulu m.

Primjer.

Ako je T = 8, tada je 1, 3, 5, 7 reducirani sustav najmanje nenegativnih ostataka, 1, 3, -3, -1- reducirani sustav apsolutno najmanjih odbitaka.

Teorem 2.

Neka broj klasa koprostih s m jednak je k.Tada bilo koja zbirka od k cijelih brojeva

u paru neusporediv po modulu m i koprost s m, reducirani je sustav ostataka po modulu m.

Dokaz

A) Svaki broj u populaciji (1) pripada određenoj klasi.

1. Svi brojevi iz (1) su po paru neusporedivi po modulu T, odnosno pripadaju različitim klasama po modulu m.
2. Svaki broj iz (1) je koprost s T, to jest, svi ti brojevi pripadaju različitim klasama koprosti s modulom m.
3. Ukupno (1) dostupno k brojeva, odnosno onoliko koliko reducirani sustav ostataka po modulu m treba sadržavati.

Prema tome, skup brojeva(1) - smanjeni sustav modulo odbitaka T.

§4. Eulerova funkcija.

Eulerov i Fermatov teorem.

1. Eulerova funkcija.

Označimo sa φ(T) broj klasa ostataka po modulu m jednakoprostih s m, odnosno broj elemenata reduciranog sustava ostataka po modulu t. Funkcija φ (t) je numerički. Zovu jeEulerova funkcija.

Izaberimo kao predstavnike razreda modulo ostataka t brojevi 1, ..., t - 1, t. Tada je φ (t) - broj takvih brojeva koprost s t. Drugim riječima, φ (t) - broj pozitivnih brojeva koji ne prelaze m i relativno su prosti prema m.

Primjeri.

1. Neka t = 9. Potpuni sustav 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, budući da je broj ovih brojeva 6, tada je φ (9) = 6.
2. Neka je t = 12. Potpuni sustav 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 s 12 . To znači

φ(12) = 4.

Na t = 1, kompletan sustav ostataka sastoji se od jedne klase 1. Zajednički prirodni djelitelj brojeva 1 i 1 je 1, (1, 1) = 1. Na temelju toga pretpostavljamo da je φ(1) = 1.

Prijeđimo na izračun Eulerove funkcije.

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

Dokaz.

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

2) Ako je t = p k - glavna snaga p, zatim

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

Dokaz.

Cjeloviti sustav modulo odbitaka t = p k sastoji se od brojeva 1,..., p k - 1, p k Prirodni djelitelji T su stupnjevi R. Stoga broj Amože imati zajednički djelitelj s m koji nije 1, samo u slučaju kadaApodjeljeno saR.Ali među brojevima 1, ... , strk -1 naRsamo su brojevi djeljivip, 2p, ... , str2 , ... RDo, čiji je broj jednakRDo: p = strk-1. To znači da su koprime st = strDoodmorRDo- Rk-1= strk-l(p-1)brojevima. Ovo to dokazuje

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

Teorema1.

Eulerova funkcija je multiplikativna, odnosno za relativno proste brojeve m i n vrijedi φ (mn) = φ(m) φ (n).

Dokaz.

Prvi zahtjev u definiciji multiplikativne funkcije ispunjen je na trivijalan način: Eulerova funkcija definirana je za sve prirodne brojeve, a φ (1) = 1. Trebamo samo pokazati da akotipmeđusobno prosti brojevi, dakle

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

Uredimo kompletan sustav odbitaka modulotpkaoPxT -matrice

1 2 T

t +1 t +2 2t

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

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

JerTIPsu relativno prosti, zatim 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.Stoga se brojevi koprosti s m nalaze u onim stupcima za kojetprolazi kroz reducirani sustav modulo ostatakaT.Broj takvih stupaca jednak je φ(T).Svaki stupac predstavlja kompletan sustav odbitaka moduloP.Iz ovih odbitaka φ(P)suprime saP.To znači da ukupan broj brojeva koji su relativno prosti i saTi s n, jednakim φ(T)φ(n)

(φ (T)stupaca, od kojih je svaki uzet φ(P)brojevi). Ovi brojevi, i samo oni, su prosti sitd.Ovo to dokazuje

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

Primjeri.

№1 . Dokažite valjanost sljedećih jednakosti

φ(4n) =

Dokaz.

№2 . Riješite jednadžbu

Riješ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 kanonsku reprezentaciju broja m:

m=.

Zbog multiplikativnosti(m) imamo:

(m)=.

Ali prema formuli (1) nalazimo da

-1), i stoga

(3)

Jednakost (3) se može prepisati kao:

Jer=m, dakle(4)

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

Primjeri.

№1 . Koliki je iznos?

Riješenje:,

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

№2 . Na temelju svojstava Eulerove funkcije brojeva dokažite da u nizu prirodnih brojeva postoji beskonačan skup prostih brojeva.

Riješenje:Uz pretpostavku da je broj prostih brojeva konačan skup, pretpostavljamo da- najveći prosti broj i neka je a=je umnožak svih prostih brojeva, temeljen na jednom od svojstava funkcije Eulerovog broja

Budući da je a≥, tada je a složeni broj, ali budući da njegova kanonska reprezentacija sadrži sve proste brojeve, tada=1. Imamo:

=1 ,

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

№3 .Riješi jednadžbu, gdje je x=I=2.

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

,

i po stanju=2.

Izrazimo iz=2 , dobivamo, zamjena u

:

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

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

Odgovor:x= 143

2. Eulerov teorem i Fermat.

Eulerov teorem ima važnu ulogu u teoriji usporedbi.

Eulerov teorem.

Ako je cijeli broj a međusobno prost s m, tada

(1)

Dokaz.Neka

(2)

postoji reducirani sustav ostataka po modulu m.

Akoaje cijeli broj međusobno prost s m, tada

(3)

Usporedba prvog stupnja s jednom nepoznatom ima oblik:

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

Riješite usporedbu- znači pronaći sve vrijednosti x koje ga zadovoljavaju. Pozivaju se dvije usporedbe koje zadovoljavaju iste vrijednosti x ekvivalent.

Ako je usporedba (1) zadovoljena bilo kojom x = x 1, zatim (prema 49) svi brojevi usporedivi s x 1, modulo m: x x 1 (mod m). Cijela ova klasa brojeva smatra se jedno rješenje. S takvim sporazumom može se izvesti sljedeći zaključak.

66.C poravnanje (1) imat će onoliko rješenja koliki je broj ostataka kompletnog sustava koji ga zadovoljavaju.

Primjer. Usporedba

6x– 4 0 (mod 8)

Među brojevima 0, 1, 2, 3, 4, 5, 6, 7 dva broja zadovoljavaju potpuni sustav ostataka po modulu 8: x= 2 i x= 6. Stoga ova usporedba ima dva rješenja:

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

Usporedba prvog stupnja pomicanjem slobodnog člana (sa suprotnim predznakom) na desnu stranu može se svesti na oblik

sjekira b(mod m). (2)

Razmotrimo usporedbu koja zadovoljava uvjet ( A, m) = 1.

Prema 66, naša usporedba ima onoliko rješenja koliko ima ostataka kompletnog sustava koji je zadovoljavaju. Ali kada x prolazi kroz cijeli sustav modulo ostataka T, Da Oh prolazi kroz cijeli sustav odbitaka (od 60). Dakle, za jednu i samo jednu vrijednost X, preuzeto iz kompletnog sustava, Oh bit će usporedivo s b. Tako,

67. Kada je (a, m) = 1 usporedna sjekira b(mod m)ima jedno rješenje.

Neka sada ( a, m) = d> 1. Zatim, za usporedbu (2) da bi postojala rješenja potrebno je (od 55) da b podjeljeno sa d, inače je usporedba (2) nemoguća 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 usporedba (2) biti ekvivalentna ovoj (skraćeno od d): a 1 x b 1 (mod m), u kojem već ( A 1 , m 1) = 1, i stoga će imati jedno rješenje modulo m 1 . Neka x 1 – najmanji nenegativni ostatak ove otopine po modulu m 1 , tada su svi brojevi x , tvoreći ovu otopinu nalaze se u obliku

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

Modulo 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 ostataka m. Ali ovdje će pasti sljedeći brojevi (3):

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

oni. Ukupno d brojevi (3); stoga usporedba (2) ima d odluke.

Dobivamo teorem:

68. Neka je (a, m) = d. Usporedba ax b ( mod m) nije moguće ako b nije djeljivo s d. Kada je b višekratnik d, usporedba ima d rješenja.

69. Metoda rješavanja usporedbi prvog stupnja, temeljena na teoriji ukočenih razlomaka:

Proširivanje relacije u nastavljeni razlomak m:a,

i gledajući zadnja dva podudarna razlomka:

prema svojstvima nastavljenih razlomaka (prema 30 ) imamo

Dakle, usporedba ima rješenje

pronaći, što je dovoljno za izračunavanje Pn– 1 prema metodi navedenoj u 30.

Primjer. Riješimo usporedbu

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

Ovdje (111, 321) = 3, a 75 je višekratnik broja 3. Stoga usporedba ima tri rješenja.

Podijelimo obje strane usporedbe i modul s 3, dobivamo usporedbu

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

koje prvo moramo riješiti. Imamo

q
P 3

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

x–26 ∙ 25 99 (mod 107).

Stoga su rješenja za usporedbu (4) prikazana 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 zadanom modulu

70.Ako su brojevi cijeli brojevi a I n su prosti, tada postoji broj a′, zadovoljavajući usporedbu a ∙ a′ ≡ 1 (mod n). Broj a′ nazvao multiplikativni inverz modula n a oznaka koja se za to koristi je a- 1 (mod n).

Izračun recipročnih veličina modulo određene vrijednosti može se izvesti rješavanjem usporedbe prvog stupnja s jednom nepoznanicom, u kojoj x broj prihvaćen a′.

Kako bi se pronašlo rješenje za usporedbu

a∙x≡ 1(mod m),

Gdje ( a,m)= 1,

možete koristiti Euklidov algoritam (69) ili Fermat-Eulerov teorem, koji kaže da ako ( a,m) = 1, dakle

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

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

Grupe i njihova svojstva

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

Pojmovi skupa, elementa i pripadnosti osnovni su nedefinirani pojmovi moderne matematike. Bilo koji skup definiran je elementima koji su u njega uključeni (koji pak također mogu biti skupovi). Dakle, kažemo da je skup definiran ili zadan ako za bilo koji element možemo reći pripada li tom skupu ili ne.

Za dva kompleta A, B zapisa B A, B A, B∩ A, B A, B \ A, A × B odnosno znače da B je podskup skupa A(tj. bilo koji element iz B također je sadržano u A, na primjer, skup prirodnih brojeva sadržan je u skupu realnih brojeva; osim toga, uvijek A A), B je pravi podskup skupa A(oni. B A I B ≠ A), sjecište mnogih B I A(tj. svi takvi elementi koji leže istovremeno u A, i u B, na primjer, presjek cijelih i pozitivnih realnih brojeva je skup prirodnih brojeva), unija skupova B I A(tj. skup koji se sastoji od elemenata koji leže ili u A, bilo u B), postavite razliku B I A(tj. skup elemenata koji leže u B, ali nemojte ležati A), Kartezijev produkt skupova A I B(tj. skup parova oblika ( a, b), Gdje a A, b B). Preko | A| uvijek se označava snaga skupa A, tj. broj elemenata u skupu A.

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

Puno elemenata G s operacijom se zove skupina, ako su zadovoljeni sljedeći uvjeti.

Razmotrimo sustav usporedbi

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

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

Dokaz. Neka b€ pripada klasi a. Kako je a ≡ b(mod M), onda je a ≡b(mod m), i= 1,2,...,s (usporedno svojstvo 16). Prema tome, b, kao i a, zadovoljava svaku usporedbu sustava, što dokazuje teorem. Stoga je prirodno rješenje sustava (2) smatrati klasom po modulu M.

Definicija. Rješenje sustava usporedbi(2) je klasa brojeva po modulu M = koji zadovoljavaju svaku usporedbu sustava.

12. Odmah napomenimo da neparni brojevi ne zadovoljavaju drugu usporedbu. Uzimajući parne brojeve iz kompletnog sustava ostataka po modulu 12, izravnom provjerom uvjeravamo se da brojevi 2, -2, 6 zadovoljavaju 2. usporedbu, a sustav ima dva rješenja: x ≡ 2(mod l2), x ≡ - 2 (mod 12).

Razmotrimo sustav usporedbi 1. stupnja (3)

Teorem2. Neka je d=(m1,m2), M = .

Ako c1 - c2 nije djeljiv s d, tada sustav (3) nema rješenja.

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

Dokaz. Iz 1. usporedbe x = c1+m1t, t€Z. Zamjena u 2. usporedbu: s1+ m1t ≡ c2(mod m2) odn.

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

A rješenje je klasa modulo (teorem 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, sustav ima jednu klasu rješenja modulo 24. Iz 1. usporedbe x =2+6t. Zamjenom x u 2. usporedbu, 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, to je x≡-4(mod 24).

2. 7-3 nije djeljivo s 3, sustav nema rješenja.

Korolar 1. Sustav usporedbe (4)

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

Dokaz. Ako sustav prve dvije usporedbe nema rješenja, tada (4) nema rješenja. Ako ima rješenje x ≡ a(mod), onda dodavanjem treće usporedbe sustava ovoj usporedbi opet dobivamo sustav oblika (3) koji ili ima jedno rješenje ili nema rješenja. Ako ima rješenje, nastavit ćemo tako dok ne iscrpimo sve usporedbe sustava (4). Ako postoji rješenje, onda je to klasa po modulu M.

Komentar. Ovdje se koristi svojstvo LCM: =.

Korolar 2. Ako su m1,m2,…,ms upareno prosti, tada sustav (4) ima jedno rješenje - modulo klasa M=m1m2…ms.

Primjer:

Budući da su moduli u paru relativno jednostavni, sustav ima jedno rješenje - modulo klasa 105 = 5*3*7. Iz prve usporedbe

Zamjenjujemo u drugu usporedbu: 2 +5t≡ 0(mod 3) ili 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Zamijenimo u trećoj usporedbi:

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

Idemo se upoznati drugi metoda rješavanja ovog sustava, (Koristimo se činjenicom da sustav ima jedno rješenje.) Pomnožimo oba dijela i modul prve usporedbe s 21, druge s 35, a treće s 15: iz zbroja prvi i treći oduzimamo drugi:

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

Razmotrimo sada sustav usporedbi prvog stupnja općeg oblika

Ako neka usporedba ovog sustava nema rješenja, onda sustav nema rješenja. Ako je svaka usporedba sustava (5) rješiva, tada je rješavamo za x i dobivamo ekvivalentni sustav oblika (4):

Gdje je (teorem 4, §2).

Prema korolariji 1, sustav ili nema rješenja ili ima jedno rješenje.

Primjer:

Nakon rješavanja svake usporedbe sustava dobivamo ekvivalentni sustav

Ovaj sustav ima jedno rješenje - klasu po modulu 105. Množenjem prve usporedbe i modula s 3, a druge s 35, dobivamo

Oduzimajući prvu usporedbu pomnoženu s 11 od druge usporedbe, dobivamo 2x ≡-62(modl05), iz čega je x ≡ -31(modl05).

Problemi koji se svode na razmatranje sustava usporedbi 1. stupnja razmatrani su u aritmetici kineskog matematičara Sun Tzua, koji je živio početkom naše ere. Njegovo je pitanje bilo postavljeno u sljedećem obliku: nađite broj koji daje zadane ostatke kada se dijeli zadanim brojevima. Također daje rješenje ekvivalentno sljedećem teoremu.

Teorem (kineski teorem o ostatku). Neka su m1,m2,…,ms upareni međusobno prosti brojevi, M = mlm2...ms, β1, β2,…, βs odabrani tako da

Zatim rješenje sustava

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

Dokaz. Pošto smo dobili x0≡

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

usporedbe sustava.

10. Usporedbe I. stupnja. Nesigurne jednadžbe

§ 2. Usporedbe 1. stupnja. Nesigurne jednadžbe

Usporedba 1. stupnja može se svesti na oblik ax≡b(mod m).

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

Dokaz. Uzmimo 0,1,2,...,m-1 - potpuni sustav ostataka modulo m. Budući da je (a,m) = 1, tada je 0,a,2a,...,(m-1)a također potpuni sustav ostataka (Teorem 3, §2, Poglavlje 2.). Sadrži jedan i samo jedan broj usporediv s b po modulu m (koji pripada istoj klasi kao i b). Neka to bude ax 0, tj. ax 0 € klasa b ili ax 0 ≡b(mod m). x ≡x 0 (mod m) je jedino rješenje (2). Teorem je dokazan.

Teorem 5. Ako je (a, m)= 1, tada je rješenje za usporedbu ax≡b(mod m) klasa x 0 ≡a φ (m)-1 b(mod m).

Dokaz. Kako 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 usporedbu (2). Doista, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Iz teorema 4 slijedi da je ovo rješenje jedinstveno.

Razmotrimo metode usporedbe rješenja ax ≡b(mod m).

1. Metoda odabira. Uzimajući cijeli sustav ostataka modulo m, odabiremo brojeve koji zadovoljavaju usporedbu.

2. Korištenje Eulerovog teorema (teorem 5).

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

1) 223x ≡ 115(mod ll).

Prvo zamjenjujemo koeficijente s najmanjim odbicima apsolutne vrijednosti: 3h ≡ 5(mod 11). Ako se poslužimo teoremom

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 usporedbu ekvivalentnom tako da na desnu stranu dodamo broj koji je višekratnik modula:

3x ≡ 5 + 22 (mod 11). Podijelimo li obje strane s brojem 3, istoprostim s modulom, dobivamo x ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Koristimo metodu pretvorbe 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 (izmjena 34).

Teorem 6. Ako je (a, m) = d i b nije djeljiv s d, tada usporedba (1) nema rješenja.

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

Teorem 7. Ako je (a,m)= d, d>1, b:d, tada usporedba(1) ima d

rješenja koja čine jednu klasu modulo ostataka i nalaze se pomoću formula

Gdje S zadovoljava pomoćnu usporedbu

Komentar. Prema teoremu, usporedba (1) se rješava na sljedeći način.

1) Uvjerivši se da je (a,m) = d, d> 1 i b:d, oba dijela u usporedbama (2) podijelimo s d i dobijemo pomoćnu usporedbu a 1 x≡b 1 (mod m 1) , gdje . Usporedba ima samo jedno rješ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ćna usporedba prema teoremu 2(3) ekvivalentna je izvornoj usporedbi (2). Budući da je ( 1, tada pomoćna usporedba ima jedinstveno rješenje - klasu po modulu m 1 = . Neka je x≡c(mod m 1) rješenje. Klasa brojeva c po modulu m 1 dijeli se na d klasa po modulu m: .

Doista, bilo koji broj iz klase x0 modulo m 1 ima oblik x 0 +m 1 t. Podijelite t s ostatkom s d: t = dq +r, gdje je 0≤r

Dakle, usporedba (1) ima d rješenja po modulu m: x0, x0+m1,..., x0 +(d-1)m1. (horizontalne crte na vrhu)

Primjeri.

1) 20x≡ 15(mod 108). Kako (20,108) = 4 i 15 nije djeljivo s 4, nema rješenja.

2) 20x≡ 44 (mod 108). (20,108) = 4 i 44:4, stoga usporedba ima četiri rješenja. Podijelimo oba dijela i modul sa 4, dobivamo:

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. ja jj

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

Primjena teorije usporedbi na rješavanje nesigurnih jednadžbi

Promotrimo neodređenu ili, kako se inače zove, Diofantovu jednadžbu prvog stupnja s dvije nepoznanice ax + by = c, gdje su a, b, c € Z. Ovu jednadžbu morate riješiti u cijelim brojevima. Ako (a,b)=d i c nije djeljiv s d, onda je očito da usporedba nema rješenja u cijelim brojevima. Ako je c djeljiv s d, tada obje strane jednadžbe podijelite s d. Stoga je dovoljno razmotriti slučaj kada je (a, b) =1.

Budući da se ax razlikuje od c višekratnikom b, tada je ax ≡ c(mod b) (bez gubitka općenitosti možemo pretpostaviti da je b > 0). Rješavanjem ove usporedbe dobivamo 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

Štoviše, - je cijeli broj, to je djelomična vrijednost nepoznate y, koja odgovara x1 (ispada, kao i x1, pri t = 0). A opće rješenje jednadžbe će imati oblik sustava jednadžbi x=x1+bt, y=y1-at, gdje je t bilo koji cijeli broj.

Bilješka da se 1) jednadžba ax + by = c može riješiti počevši s usporedbom by ≡ c(mod a), budući da se by razlikuje od c višekratnikom a;

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

Primjer, 50x – 42y= 34.

Podijelite obje strane jednadžbe s 2.

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

x ≡ -1 (mod 21), odnosno x=-1+21t, t€Z. Zamijenimo pronađeni x u jednadžbu. 25(-1 + 21t)- 21y= 17; 21u =-42 + 25* 21t i u =-2 + 25t.