Rješavanje usporedbi prvog stupnja. Usporedba po modulu prirodnog broja Teorija brojeva usporedba po modulu

Usporedba prvog stupnja s jednom nepoznatom ima oblik:

f(x) 0 (mod m); f(x) = Oh + a 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 usporedba (1) zadovoljava neke x = x 1, zatim (prema 49) svi brojevi usporedivi s x 1, modulo m: x x 1 (mod m). Cijela ova klasa brojeva računa se kao jedno rješenje. Iz ovog sporazuma može se izvesti sljedeći zaključak.

66.C poravnanje (1) imat će onoliko rješenja koliko ima ostataka kompletnog sustava koji ga zadovoljava.

Primjer. Usporedba

6x– 4 0 (mod 8)

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

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

Usporedba prvog stupnja prenošenjem 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 zadovoljava. Ali kada x prolazi kroz cijeli sustav rezidua modulo 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. Za (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 podijeljen u 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 (smanjena za 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 je najmanji nenegativan ostatak ove otopine po modulu m 1 , zatim svi brojevi x , formiranje ovog rješenja može se naći u obliku

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

Modulo, 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 nenegativan ostatak po modulu 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); dakle usporedba (2) ima d rješenja.

Dobivamo teorem:

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

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

Proširivanje omjera u neprekinuti razlomak m:a,

i uzimajući u obzir posljednja dva konvergenta:

prema svojstvima nastavljenih razlomaka (prema 30 ) imamo

Dakle, usporedba ima rješenje

za pretragu, što je dovoljno za izračunavanje P n- 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 oba dijela usporedbe i modula s 3, dobivamo usporedbu

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

što prvo trebamo odlučiti. Imamo

q
P 3

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

x–26 ∙ 25 99 (mod 107).

Stoga su rješenja usporedbe (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 cijeli brojevi a I n međusobno prosti, tada postoji broj a′, zadovoljavajući usporedbu a ∙ a′ ≡ 1 (mod n). Broj a′ nazvao multiplikativni inverz modula n a za to se koristi notacija a- 1 (mod n).

Izračunavanje recipročnih vrijednosti po modulu some može se izvršiti usporedbom rješenja prvog stupnja s jednom nepoznanicom, u kojoj x prihvaćeni broj a′.

Kako bi se pronašlo rješenje za usporedbu

a x≡ 1(mod m),

Gdje ( a,m)= 1,

može se 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 da li pripada tom skupu ili ne.

Za dva kompleta A, B zapisa B A, B A, B∩ A, B A, B \ A, A × B znači, odnosno, 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 i 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 proizvod skupova A I B(tj. skup parova oblika ( a, b), Gdje a A, b B). Kroz | A| uvijek se označava kardinalnost skupa A, tj. broj elemenata u skupu A.

Operacija je pravilo prema kojem bilo koja dva elementa skupa G(a I b) pridružen je trećem elementu iz G: a b.

Puno elemenata G s operacijom tzv skupina ako su zadovoljeni sljedeći uvjeti.

Sadržaj.

Uvod

§1. Modulo usporedba

§2. Svojstva usporedbe

1. Svojstva usporedbe neovisna o modulu
2. Svojstva usporedbe specifična za modul

§3. Sustav odbitka

1. Kompletan sustav odbitaka
2. Reducirani 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 odluku 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 nastavljenih razlomaka

§3. Sustavi usporedbi 1. stupnja s jednom nepoznanicom

§4. Podjela usporedbi viših sila

§5. Primitivni 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. Pretvaranje običnog razlomka u konačni

decimalni razlomak

Zaključak

Književnost

Uvod

U našem životu često se moramo baviti cijelim brojevima i zadacima vezanim uz njih. U ovom diplomskom radu razmatram teoriju usporedbe cijelih brojeva.

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

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

Izjava "a je kongruentno 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čka istraživanja". 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 onim slučajevima kada je dovoljno znati u bilo kojem istraživanju brojeve 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 glavnih metoda za rješavanje 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 paragrafe, a paragrafi na paragrafe.

Prvo poglavlje bavi se općim pitanjima 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 jedna nepoznanica, usporedbe viših stupnjeva itd. .

Treće poglavlje sadrži neke primjene teorije brojeva na školsku matematiku. Razmatraju se znakovi djeljivosti, provjera rezultata radnji, 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 z-prsten cijelih brojeva, m-fiksni cijeli broj i m z-skup svih cijelih brojeva djeljivih s m.

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

Definiramo da se relacija usporedivosti po modulu m podudara s relacijom usporedivosti po modulu (-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 isti ostatak 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 (2) od (1), dobivamo a-b= m(q₁- q₂), tj. a-b m ili a b (mod m).

Obrnuto, neka a b (mod m). Ovo znači 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 dijeljenje a s m daje isti ostatak kao i dijeljenje 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 isti ostatak kada se dijele s m nazivaju se ekvidistantni ili usporedivi po modulu m.

Primjeri.

Imamo: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², a (- m²) je djeljivo 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 imaju isti gcd s njim.

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

gcd(4,10) = 2, gcd(25,10) = 5, tako da je naša usporedba pogrešna.

§2. Svojstva usporedbe

1. Svojstva usporedbe neovisna o modulu.

Mnoga svojstva usporedbi slična su onima jednakosti.

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

C) 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 u oba dijela 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. Stoga 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 usporedbe mogu se podići na istu cjelobrojnu nenegativnu 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: željeni 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+ =

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

h.t.d.

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

Imamo: 1 (mod 24), dakle

1 (mod 24)

Dodavanjem 55 u oba dijela usporedbe dobivamo:

(izmjena 24).

Imamo: (mod 24), dakle

(mod 24) za bilo koje k ê N.

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

1. Oba dijela 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 nakon dijeljenja 196 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. Oba dijela usporedbe i modula mogu se pomnožiti s istim cijelim brojem.

Dokaz.

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

Primjer.

Provjerite je li vrijednost izraza cijeli broj.

Riješenje:

Predstavimo razlomke u obliku usporedbi: 4(mod 3)

1 (izmjena 9)

31 (mod. 27)

Zbrajamo ove usporedbe pojam po pojam (svojstvo 2), dobivamo 124(mod 27) Vidimo da 124 nije cijeli broj djeljiv sa 27, otuda vrijednost izrazatakođer nije cijeli broj.

1. Oba dijela usporedbe mogu se podijeliti svojim zajedničkim faktorom ako je relativno prost modulu.

Dokaz.

Ako je ca cb (mod m), tj. 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 oba dijela usporedbe s 3 dobivamo:

20 (izmjena 17).

Općenito govoreći, nemoguće je oba dijela usporedbe podijeliti brojem koji nije koprost s modulom, jer se nakon dijeljenja mogu dobiti brojevi koji su neusporedivi u tom modulu.

Primjer.

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

1. Oba dijela usporedbe i modula mogu se podijeliti svojim zajedničkim djeliteljem.

Dokaz.

Ako ka kb (mod km), tada je k (a-b) djeljiv 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 oba dijela svake od dobivenih 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.

Dodavanjem zadnjih usporedbi dobivamo: P (a) P(b) (mod m). Ako je a (mod m) i c i d i (mod m), 0 ≤ i ≤ n, tada

(mod m). Dakle, u kongruenciji po modulu m, pojedinačni članovi i faktori mogu se zamijeniti brojevima koji su sukladni po modulu m.

Pritom treba obratiti pozornost na činjenicu da se eksponenti koji se susreću u usporedbama ne mogu zamijeniti na ovaj način: od

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

Svojstvo 11 ima niz važnih primjena. Konkretno, može se koristiti za teoretsko obrazloženje znakova 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. Kompletan sustav naplate.

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

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

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

Biramo iz svake klase rezidua modulo T jednim brojem. Dobiti m cijelih brojeva: x 1 ,…, x m . Skup (x 1, ..., x t) se zove potpuni sustav ostataka po modulu m.

Budući da svaka klasa sadrži neprebrojiv skup ostataka, moguće je sastaviti neprebrojiv skup različitih potpunih sustava ostataka modulo m, od kojih svaki sadrži t odbici.

Primjer.

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

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

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

Napravimo 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.

Najviše korišten:

1. Kompletan sustav najmanje nenegativnih ostataka: 0, 1, t -1 U gornjem primjeru: 0, 1, 2, 3, 4. Takav sustav ostataka je jednostavan: potrebno je zapisati sve nenegativne ostatke koji nastaju 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. Potpuni sustav apsolutno najmanje ostataka.U slučaju neparnog m, apsolutno najmanji ostaci pojavljuju se 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 glavna svojstva cjelovitog sustava ostataka.

Teorem 1 . Bilo koji skup od m cijelih brojeva:

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

u paru neusporediv po modulu m, tvori potpuni sustav 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) međusobno su neusporedivi, tj. pripadaju različitim klasama.
3. U (1) ima ukupno m brojeva, tj. onoliko koliko modulo ima klasa T.

x 1, x 2,…, x t je potpuni sustav ostataka modulo m.

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

Dokaz.

Smatrati

Sjekira 1 + b, sjekira 2 + b, ..., sjekira 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 neusporedivi, odnosno pripadaju različitim klasama.

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

ax i + b ax j + b (mod m), (i = j), tada bismo dobili sjekira i sjekira j (mod m). Budući da (a, t) = 1, tada svojstvo usporedbi može smanjiti oba dijela usporedbe za A . Dobivamo x i x j (mod m).

Prema uvjetu, x i x j (mod m) za (i = j), budući da je x 1 ,x 2 , ..., x m - puni 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 je 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 je t z. Iz ove jednakosti slijedi da je (a, m) = (b, m).

Doista, neka je δ-zajednički djelitelj od a i m, tada aδ, m δ. Kako je a = b + mt, tada je b=a-mt, dakle bδ. Prema tome, svaki zajednički djelitelj od a i m je zajednički djelitelj od 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 za T koji se zove najveći zajednički djelitelj T i ova klasa ostataka.

Definicija 2. Klasa rezidua a modulo m naziva se koprost s 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 prosti).

Primjer.

Neka t = 6. Klasa ostataka 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 u odnosu na modul 6.

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

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

Definicija 3 implicira metodu za dobivanje reduciranog sustava ostataka po modulu T: potrebno je ispisati neki cjeloviti sustav ostataka i iz njega ukloniti sve ostatke koji nisu koprimi s m. Preostali skup odbitaka je smanjeni sustav odbitaka. Očito postoji beskonačan broj reduciranih sustava ostataka po modulu m.

Ako kao početni uzmemo potpuni sustav najmanjih nenegativnih ili apsolutno najmanjih ostataka, tada na navedeni način dobivamo dotično reducirani sustav najmanjih nenegativnih ili apsolutno najmanjih ostataka po modulu m.

Primjer.

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

Teorem 2.

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

u paru neusporediv po modulu m i relativno prost prema m, reducirani je sustav ostataka po modulu m.

Dokaz

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

1. Svi brojevi iz (1) su po parovima neusporedivi modulo 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 koprostih s modulom m.
3. Ukupno (1) ima k brojeva, odnosno onoliko koliko reducirani sustav ostataka po modulu m treba sadržavati.

Prema tome, skup brojeva(1) - reducirani sustav ostataka po modulu T.

§4. Eulerova funkcija.

Eulerov i Fermatov teorem.

1. Eulerova funkcija.

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

Kao predstavnike rezidualnih klasa biramo modulo t brojevi 1, ... , t - 1, t. Tada je φ (t) je broj takvih brojeva koprostih 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. od 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 iz 12. Stoga,

φ(12) = 4.

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

Prijeđimo na izračun Eulerove funkcije.

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

Dokaz.

Ostaci 1, 2, ... , p- 1 a samo su oni suprosti s prostim brojem R. Stoga je φ (p) = p - 1.

2) Ako je m = p k - potencija prostog broja p, zatim

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

Dokaz.

Kompletan sustav ostataka po modulu 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 kadaApodjeljeno saR.Ali među brojevima 1, ... , strk -1 naRdijeljenje samo brojevap, 2p, ... , str2 , ... RDo, čiji je brojRDo: p = strk-1. Dakle, koprim st = strDoodmorRDo- Rk-1=strkl(p-1)brojevima. Dakle, dokazano je da

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

Teorema1.

Eulerova funkcija je multiplikativna, odnosno za međusobno 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 akotiprelativno prosti brojevi, dakle

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

Cjelokupni sustav ostataka rasporedi po modulutpkaoPxT -matrice

1 2 T

t+1 t+2 2t

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

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

JerTIPzajednički prosti, zatim brojxmeđusobno jednostavno satpako i samo akoxmeđusobno jednostavno saTIxmeđusobno jednostavno saP. Ali brojkm + tmeđusobno jednostavno saTako i samo akotmeđusobno jednostavno saT.Stoga se brojevi relativno prosti s m nalaze u onim stupcima za kojetprolazi reduciranim sustavom ostataka moduloT.Broj takvih stupaca je φ(T).Svaki stupac predstavlja kompletan sustav rezidua moduloP.Iz ovih ostataka φ(P)suprime saP.Dakle, ukupan broj brojeva coprime i saTa s n, jednako φ(T)φ(n)

(φ (T)stupaca, od kojih svaki uzima φ(P)brojevi). Ovi brojevi, i samo oni, su prosti s njimaitd.Dakle, dokazano je da

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

Primjeri.

№1 . Dokažite sljedeće jednakosti

φ(4n) =

Dokaz.

№2 . riješiti 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 množitelja(m) imamo:

(m)=.

Ali prema formuli (1) to dobivamo

-1), i stoga

(3)

Jednakost (3) se može prepisati kao:

Jer=m, dakle(4)

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

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:Izravnavanje broja prostih brojeva konačnim skupom, pretpostavimo toje 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.

Express od=2 , dobivamo, zamijenimo

:

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

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

Odgovor:x= 143

2. Eulerov teorem i Fermat.

U teoriji usporedbi važnu ulogu ima Eulerov teorem.

Eulerov teorem.

Ako je cijeli broj a relativno prost prema m, tada

(1)

Dokaz.Neka

(2)

je reducirani sustav ostataka po modulu m.

Akoaje cijeli broj relativno prost prema m, tada

(3)

Razmotrite usporedbu oblika 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 pronaći rješavanjem podudarnosti x 2 ≡a(mod str). I usporedba x 2 ≡a(mod strα) će imati dva rješenja ako a je kvadratni ostatak po modulu str.

Primjer:

Riješite kvadratnu usporedbu x 2 ≡86 (mod 125).

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

Izvorna usporedba ima 2 rješenja.

Pronađimo rješenje za usporedbu x 2 ≡86 (mod 5).

x 2 ≡1(mod 5).

Ova se usporedba može riješiti na način naveden u prethodnom paragrafu, ali ćemo koristiti činjenicu da je kvadratni korijen iz 1 modulo ±1, a usporedba ima točno dva rješenja. Dakle, rješenje za kongruenciju modula 5 je

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

Zamijenite dobiveno rješenje u usporedbi 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 za kongruenciju po modulu 25 x=±(1+5(1+5 t 2))=±(6+25 t 2). Zamijenite dobiveno rješenje u usporedbi 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 usporedbe po modulu 125 x=±(6+25(1+5 t 3))=±(31+125 t 3).

Odgovor: x≡±31 (mod 125).

Razmotrimo sada usporedbu oblika x 2 ≡a(mod2α). Takva usporedba nema uvijek dva rješenja. Za takav modul mogući su sljedeći slučajevi:

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

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

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

Primjer:

Riješite usporedbu x 2 ≡33 (mod 64)

64=26. Provjerimo ima li izvorna usporedba rješenje. 33≡1(mod 8), pa usporedba ima 4 rješenja.

Modulo 8 ova će rješenja 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 usporedbi 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 dobiveno rješenje u kongruenciju modula 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 dobiveno rješenje u usporedbi 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, originalna usporedba ima četiri rješenja: x≡±17 (mod 64) i x≡±49 (mod 64).

Sada razmotrite opću usporedbu: x 2 ≡a(mod m), (a,m)=1, - kanonska dekompozicija modula m. Prema teoremu iz 4. točke §4. ova je usporedba ekvivalentna sustavu

Ako je svaka usporedba ovog sustava odlučiva, onda je cijeli sustav odlučiv. Pronašavši rješenje svake usporedbe ovog sustava, dobivamo sustav usporedbi prvog stupnja, čijim rješavanjem, koristeći kineski teorem o ostatku, dobivamo rješenje izvorne usporedbe. Štoviše, broj različitih rješenja izvorne usporedbe (ako je rješiva) je 2 k, ako je α=1, 2 k+1 ako je α=2, 2 k+2 ako je α≥3.

Primjer:

Riješite usporedbu x 2 ≡4(mod 21).

Usporedba s jednom nepoznatom x ima oblik

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

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

Ako x 0 zadovoljava usporedbu, tada će, prema svojstvu 9 usporedbi, ova usporedba zadovoljiti sve cijele brojeve usporedive s x 0 modulo m. Stoga sva usporedna rješenja pripadaju istoj klasi modulo ostataka T, smatrat ćemo jednim rješenjem. Dakle, usporedba ima onoliko rješenja koliko ima elemenata cjelovitog sustava ostataka koji je zadovoljavaju.

Usporedbe čiji su skupovi rješenja isti nazivaju se ekvivalent.

2.2.1 Usporedbe prvog stupnja

Usporedba prvog stupnja s jednom nepoznatom x ima oblik

(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 ćemo dokazati nužnost. Neka d = GCD( a, m) I x 0 - rješenje usporedbe. Zatim , odnosno razlika Oh 0 − b podjeljeno sa T. Dakle, postoji 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 s d, i zbog toga b podjeljeno sa d.

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

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

za neke x 0 , g 0 . Oba dijela posljednje jednakosti množimo 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 jer je gcd(9, 12) = 3 i 6 djeljivo s 3. □

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

Teorem 2.5. Neka je kongruencija (2.2) odlučiva i d = GCD( a, m). Tada se skup rješenja usporedbe (2.2) sastoji od d modulo rezidualne klase T, naime ako x 0 je jedno od rješenja, onda su sva druga rješenja

Dokaz. Neka x 0 je rješenje usporedbe (2.2), tj. I , . Dakle, postoji takav q, Što Oh 0 − b = qm. Zamjena sada 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 budući da 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. Usporedba 11 x=2 (mod 15) ima jedinstveno rješenje x 0 = 7 budući da je gcd(11,15)=1.□

Pokažimo kako riješiti usporedbu prvog stupnja. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje podudarnosti (2.2) može tražiti npr. Euklidovim algoritmom. Doista, koristeći prošireni Euklidski algoritam, predstavljamo broj 1 kao linearnu kombinaciju brojeva a I T:

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

Drugi način rješavanja je korištenje Eulerovog teorema. Opet, pretpostavljamo da je GCD(a, T)= 1. Primjenjujemo Eulerov teorem: . Pomnožite obje strane usporedbe s b: . Prepisivanje posljednjeg izraza kao , dobivamo da je to rješenje kongruencije (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, jer GCD( A 1 , m 1) = 1, tada x 0 bit će odluka 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.