Federalna agencija za obrazovanje

Državna obrazovna ustanova visokog stručnog obrazovanja

Državno humanitarno sveučilište Vyatka

Matematički fakultet

Zavod za matematičku analizu i metode
nastava matematike

Završni kvalifikacijski rad

na temu: Gaussov prsten cijelih brojeva.

Završeno:

Student 5. godine

Matematički fakultet

Gnusov V.V.

___________________________

Znanstveni savjetnik:

viši predavač katedre

algebre i geometrije

Semenov A.N.

___________________________

Recenzent:

Kandidat fizike i matematike znanosti, izvanredni profesor

Zavod za algebru i geometriju

Kovyazina E.M.

___________________________

Prihvaćen obrani na Državnom povjerenstvu za ovjeru

glava Odjel________________ Vechtomov E.M.

« »________________

Dekan Fakulteta ___________________ Varankina V.I.

Uvod.

Prsten kompleksnih cijelih brojeva

otkrio ga je Carl Gauss i njemu u čast nazvan Gaussian.

K. Gauss je došao na ideju o mogućnosti i potrebi proširenja pojma cijelog broja u vezi s traženjem algoritama za rješavanje usporedbi drugog stupnja. Prenio je pojam cijelog broja na brojeve oblika

, gdje su proizvoljni cijeli brojevi, a je korijen jednadžbe Na zadanom skupu K. Gauss je prvi izgradio teoriju djeljivosti, sličnu teoriji djeljivosti cijelih brojeva. Potkrijepio je valjanost osnovnih svojstava djeljivosti; pokazao je da u prstenu kompleksnih brojeva postoje samo četiri invertibilna elementa: ; dokazali valjanost teorema o dijeljenju s ostatkom, teorema o jedinstvenosti faktorizacije; pokazao koji će prosti prirodni brojevi ostati prosti u prstenu; otkrio prirodu jednostavnih cijelih i složenih brojeva.

Teorija koju je razvio K. Gauss, opisana u njegovom djelu Aritmetičke studije, bila je temeljno otkriće za teoriju brojeva i algebre.

U završnom radu postavljeni su sljedeći ciljevi:

1. Razviti teoriju djeljivosti u prstenu Gaussovih brojeva.

2. Saznajte prirodu prostih Gaussovih brojeva.

3. Pokažite korištenje Gaussovih brojeva u rješavanju običnih Diofantovih problema.

POGLAVLJE 1. DIJELJENJE U PRSTENU GAUSSOVIH BROJEVA.

Razmotrimo skup kompleksnih brojeva. Po analogiji sa skupom realnih brojeva, u njemu se može izdvojiti određeni podskup cijelih brojeva. Skup brojeva obrasca

, Gdje Nazovimo ih kompleksnim cijelim brojevima ili Gaussovim brojevima. Lako je provjeriti da aksiomi prstena vrijede za ovaj skup. Dakle, ovaj skup kompleksnih brojeva je prsten i zove se prsten Gaussovih cijelih brojeva . Označimo ga kao , budući da je proširenje prstena elementom: .

Budući da je prsten Gaussovih brojeva podskup kompleksnih brojeva, za njega vrijede neke definicije i svojstva kompleksnih brojeva. Tako npr. za svaki Gaussov broj

odgovara vektoru s početkom u točki i krajem u . Stoga, modul postoje Gaussovi brojevi. Imajte na umu da je u skupu koji razmatramo submodularni izraz uvijek nenegativan cijeli broj. Stoga je u nekim slučajevima prikladnije koristiti pravilo , odnosno kvadrat modula. Tako . Mogu se razlikovati sljedeća svojstva norme. Za sve Gaussove brojeve vrijedi sljedeće: (1) (2) (3) (4) (5) - skup prirodnih brojeva, odnosno pozitivnih cijelih brojeva.

Valjanost ovih svojstava trivijalno se provjerava korištenjem modula. Usput, napomenimo da (2), (3), (5) također vrijede za sve kompleksne brojeve.

Prsten Gaussovih brojeva je komutativni prsten bez djelitelja 0, jer je podprsten polja kompleksnih brojeva. To implicira multiplikativnu kontraktilnost prstena

, odnosno (6)

1.1 REVERZIBILNI I SRODNI ELEMENTI.

Da vidimo koji će Gaussovi brojevi biti invertibilni. Množenje neutralno je

. Ako je Gaussov broj reverzibilan , onda, po definiciji, postoji takav da . Prijelazeći na norme, prema svojstvu 3, dobivamo . Ali te su norme, dakle, prirodne. To znači, prema svojstvu 4, . Obrnuto, svi elementi ovog skupa su invertibilni, jer . Posljedično, brojevi s normom jednakom jedan bit će invertibilni, tj. , .

Kao što vidite, neće svi Gaussovi brojevi biti invertibilni. Stoga je zanimljivo razmotriti pitanje djeljivosti. Kao i obično, to kažemo

dionice na , ako postoji takav da . Za sve Gaussove brojeve, kao i one invertibilne, vrijede svojstva. (7) (8) (9) (10) , gdje je (11) (12)

Lako provjerljivo (8), (9), (11), (12). Pravda (7) proizlazi iz (2), a (10) proizlazi iz (6). Zbog svojstva (9) elementi skupa

Iz tečaja programiranja znamo da cijeli broj može biti predstavljen u računalnoj memoriji na različite načine, posebice, ovaj prikaz ovisi o tome kako je opisan: kao vrijednost tipa integer, ili real, ili niz. Štoviše, u većini programskih jezika, cijeli brojevi se shvaćaju kao brojevi iz vrlo ograničenog raspona: tipičan slučaj je od -2 15 = -32768 do 2 15 - 1 = 32767. Sustavi računalna algebra raditi s velikim cijelim brojevima, posebno svaki takav sustav može izračunati i prikazati brojeve oblika 1000 u decimalnom zapisu! (više od tisuću znakova).

U ovom tečaju razmotrit ćemo prikaz cijelih brojeva u simboličkom obliku i nećemo ići u detalje o tome koja je memorija dodijeljena za zapis jednog znaka (bit, bajt ili drugo). Najčešći je predstavljanje cijelih brojeva u položajni brojevni sustavi. Takav sustav određen je izborom brojčane baze, na primjer, 10. Skup cijelih decimalnih brojeva obično se opisuje na sljedeći način:

Pisana definicija cijelih brojeva daje nedvosmislen prikaz svakog takvog broja, a slična definicija (samo, možda, s drugačijom osnovom) koristi se u većini sustava računalna algebra. Pomoću ovog prikaza prikladno je implementirati aritmetičke operacije na cijelim brojevima. Štoviše, zbrajanje i oduzimanje su relativno “jeftine” operacije, dok su množenje i dijeljenje “skupi”. Pri ocjeni složenosti aritmetičkih operacija treba uzeti u obzir i cijenu elementarne operacije (jednoznamenkaste) i broj jednoznamenkastih operacija za izvođenje bilo koje operacije nad višeznamenkastim brojevima. Složenost množenja i dijeljenja posljedica je, prije svega, činjenice da se s povećanjem duljine broja (njegovo snimanje u bilo kojem brojevnom sustavu) broj elementarnih operacija povećava prema kvadratnom zakonu, za razliku od linearnog. zakon za zbrajanje i oduzimanje. Osim toga, ono što obično nazivamo algoritmom za dijeljenje višeznamenkastih brojeva zapravo se temelji na traženju (često vrlo značajnom) moguće sljedeće znamenke količnika, te nije dovoljno samo koristiti pravila dijeljenja jednoznamenkastih brojeva. brojevima. Ako je baza brojevnog sustava velika (često može biti reda veličine 2 30), ova metoda je neučinkovita.

Neka je prirodni broj (zapisan u decimalnom sustavu). Da dobijem njegov rekord u -arnom brojevnom sustavu možete koristiti sljedeći algoritam (označava cjelobrojni dio broja):

Zadano: A-prirodni broj u decimalnom brojevnom sustavu k > 1-prirodni broj Potrebno: A-zapis broja A u k-arnom brojevnom sustavu Započnite i:= 0 ciklus dok A > 0 bi:= A (mod k ) A:= i:= i + 1 kraj ciklusa dA:= i - 1 kraj

Za vraćanje decimalnog broja iz niza njegove k-arne notacije koristi se sljedeći algoritam:

Zadano je: k > 1-prirodni brojevni niz znamenki koji predstavlja broj A u k-arnom sustavu Potrebno: A-zapis broja A u decimalnom brojevnom sustavu Start A:= 0 ciklus do kraja niza b:= sljedeći element niza A:= A * k + b kraj petlje Kraj

1.2. VJEŽBA. Objasnite zašto se dijeljenje koristi za pretvorbu broja iz decimalnog sustava u k-arni sustav, a množenje za pretvorbu iz k-arnog sustava u decimalni sustav.

Množenjem “stupcem” dvaju dvoznamenkastih brojeva u decimalnom brojevnom sustavu izvodimo sljedeće operacije:

(10a + b)(10c + d) = 100ac + 10(ad + bc) + bd,

tj. 4 operacije množenja jednoznamenkastih brojeva, 3 operacije zbrajanja i 2 operacije množenja na potenciju radiksa, koje se svode na pomak. Pri procjeni složenosti možete uzeti u obzir sve elementarne operacije bez dijeljenja po težinama (u ovom primjeru imamo 9 elementarnih operacija). Ovim pristupom problem optimizacije algoritma svodi se na minimiziranje ukupnog broja elementarnih operacija. Može se, međutim, smatrati da je množenje "skuplja" operacija od zbrajanja, koje je pak "skuplje" od posmaka. Uzimajući u obzir samo najskuplje operacije, dobivamo to multiplikativni Težina množenja dvoznamenkastih brojeva u stupcu je 4.

Odjeljak 5 raspravlja o algoritmima za izračunavanje najvećih zajedničkih djelitelja i ocjenjuje njihovu složenost.

Razmatrani prikaz nije jedini kanonski prikaz cijelih brojeva. Kao što je već navedeno, za odabir kanonskog prikaza možete koristiti jedinstvenost dekompozicije prirodnog broja na proste faktore. Ovakav prikaz cijelog broja može se koristiti u onim zadacima gdje se koriste samo operacije množenja i dijeljenja, jer one postaju vrlo “jeftine”, ali se trošak operacija zbrajanja i oduzimanja nerazmjerno povećava, što onemogućuje korištenje takvog prikaza. U nekim problemima, napuštanje kanonske reprezentacije daje značajan dobitak u izvedbi; posebice se može koristiti djelomična faktorizacija broja. Slična metoda je posebno korisna kada se ne radi s brojevima, već s polinomima.

Ako je poznato da su tijekom rada programa svi cijeli brojevi koji se susreću u izračunima ograničeni u apsolutnoj vrijednosti nekom zadanom konstantom, tada se za definiranje takvih brojeva može koristiti njihov sustav ostataka modulo nekih međusobno prostih brojeva, čiji umnožak premašuje spomenuta konstanta. Izračuni s klasama ostataka općenito su brži od aritmetike višestruke preciznosti. A s ovim pristupom, aritmetika višestruke preciznosti trebala bi se koristiti samo prilikom unosa ili ispisa informacija.

Imajte na umu da, zajedno s kanonskim prikazima u sustavima računalna algebra Koriste se i drugi prikazi. Konkretno, poželjno je da prisutnost ili odsutnost znaka "+" ispred cijelog broja ne utječe na njegovu percepciju računala. Tako se za pozitivne brojeve dobiva višeznačan prikaz, iako je oblik negativnih brojeva jednoznačno određen.

Drugi zahtjev je da na percepciju broja ne smije utjecati prisutnost nula prije prve značajne znamenke.

1.3. VJEŽBE.

1. Procijenite broj jednoznamenkastih množenja korištenih pri množenju m-znamenkastog broja s n-znamenkastim stupcem.
2. Pokažite da se dva dvoznamenkasta broja mogu pomnožiti koristeći samo 3 jednoznamenkasta množenja i povećavajući broj zbrajanja.
3. Pronađite algoritam za dijeljenje dugih brojeva koji ne zahtijeva puno traženja pri pronalaženju prve znamenke količnika.
4. Opišite algoritam za pretvorbu prirodnih brojeva iz m-arnog brojevnog sustava u n-arni brojevni sustav.
5. U rimsko numeriranje Za pisanje brojeva koriste se sljedeći simboli: I - jedan, V - pet, X - deset, L - pedeset, C - sto, D - petsto, M - tisuća. Simbol se smatra negativnim ako se desno od njega nalazi simbol većeg broja, a pozitivnim u suprotnom. Na primjer, broj 1948 u ovom sustavu bit će napisan ovako: MCMXLVIII. Formulirajte algoritam za pretvorbu broja iz rimskog u decimalni i natrag. Implementirajte dobiveni algoritam u jednom od algoritamskih jezika (na primjer, C). Ograničenja izvornih podataka: 1<= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
6. Formulirajte algoritam i napišite program za zbrajanje prirodnih brojeva rimskim brojevima.
7. Reći ćemo da imamo posla s brojevnim sustavom s mješovita ili vektorska osnova, ako nam je zadan vektor od n prirodnih brojeva M = (m 1 , . . . , m n) (radix) i oznaka K = (k 0 , k 1 , . . . , k n) označava broj k = k 0 +m 1 (k 1 +m 2 (k 2 +· · ·+m n ·k n)...)). Napišite program koji na temelju podataka (dan u tjednu, sati, minute, sekunde) utvrđuje koliko je sekundi prošlo od početka tjedna (ponedjeljak, 0, 0, 0) = 0, i izvodi obrnutu transformaciju.

Prirodni brojevi nisu prsten, jer 0 nije prirodan broj, a također za prirodne brojeve nema prirodnih suprotnosti. Struktura koju čine prirodni brojevi naziva se poluprsten. Točnije,

Poluprsten naziva se komutativna poluskupina s obzirom na zbrajanje i poluskupina s obzirom na množenje, u kojoj su operacije zbrajanja i množenja povezane zakonima distribucije.

Uvedimo sada stroge definicije cijelih brojeva i dokažimo njihovu ekvivalentnost. Na temelju ideja o algebarskim strukturama i činjenice da je skup prirodnih brojeva poluprsten, ali nije prsten, možemo uvesti sljedeću definiciju:

Definicija 1. Prsten cijelih brojeva je minimalni prsten koji sadrži poluprsten prirodnih brojeva.

Ova definicija ne govori ništa o pojavi takvih brojeva. U školskom tečaju cijeli se brojevi definiraju kao prirodni brojevi, njihove suprotnosti i 0. Ova se definicija također može uzeti kao osnova za konstrukciju stroge definicije.

Definicija 2. Prsten cijelih brojeva je prsten čiji su elementi prirodni brojevi, njihove suprotnosti i 0 (i samo oni).

Teorem 1. Definicije 1 i 2 su ekvivalentne.

Dokaz: Označimo sa Z 1 prsten cijelih brojeva u smislu definicije 1, a sa Z 2 prsten cijelih brojeva u smislu definicije 2. Najprije ćemo dokazati da je Z 2 uključen u Z 1 . Doista, svi elementi od Z 2 su ili prirodni brojevi (oni pripadaju Z 1, jer Z 1 sadrži poluprsten prirodnih brojeva), ili njihove suprotnosti (oni također pripadaju Z 1, jer je Z 1 prsten, što znači za svaki element ovog prstena postoji suprotnost, a za svaki prirodni broj n O Z 1, –n također pripada Z 1), odnosno 0 (0 O Z 1, budući da je Z 1 prsten, au svakom prstenu postoji 0), dakle, svaki element iz Z 2 također pripada Z 1, što znači Z 2 Í Z 1. S druge strane, Z 2 sadrži poluprsten prirodnih brojeva, a Z 1 je minimalni prsten koji sadrži prirodne brojeve, tj. ne može sadržavati nijedan još prstenovi koji zadovoljavaju ovaj uvjet. No, pokazali smo da sadrži Z 2, što znači Z 1 = Z 2. Teorem je dokazan.

Definicija 3. Prsten cijelih brojeva je prsten čiji su elementi svi mogući elementi, predstavivi kao razlika b – a (sva moguća rješenja jednadžbe a + x = b), gdje su a i b proizvoljni prirodni brojevi.

Teorem 2. Definicija 3 je ekvivalentna prethodnim dvjema.

Dokaz: Označimo sa Z 3 prsten cijelih brojeva u smislu definicije 3, a sa Z 1 = Z 2, kao i prije, prsten cijelih brojeva u smislu definicija 1 i 2 (njihova jednakost je već utvrđena). Najprije dokažemo da je Z 3 uključeno u Z 2 . Doista, svi elementi od Z 3 mogu se prikazati kao neke razlike prirodnih brojeva b – a. Za bilo koja dva prirodna broja, prema teoremu o trihotomiji, moguće su tri opcije:

U ovom slučaju razlika b – i također je prirodan broj i stoga pripada Z 2 .

U ovom slučaju razliku dva jednaka elementa označavamo simbolom 0. Dokažimo da je to doista nula prstena, odnosno neutralan element u odnosu na zbrajanje. Da bismo to učinili, koristit ćemo se definicijom razlike a – a = x ó a = a + x i dokazati da je b + x = b za bilo koje prirodno b. Da bismo to dokazali, dovoljno je dodati element b desnoj i lijevoj strani jednakosti a = a + x, a zatim upotrijebiti zakon redukcije (sve ove radnje mogu se izvesti na temelju poznatih svojstava prstenova). Nula pripada Z 2 .

U ovom slučaju razlika a – b je prirodan broj, označavamo

b – a = – (a – b). Dokažimo da su elementi a – b i b – a doista suprotni, odnosno da zbrajaju nulu. Zapravo, ako označimo a – b = x, b – a = y, tada dobivamo da je a = b + x, b = y + a. Zbrajanjem dobivenih jednakosti član po član i smanjenjem b, dobivamo a = x + y + a, odnosno x + y = a – a = 0. Dakle, a – b = – (b – a) je suprotno od prirodni broj, odnosno opet pripada Z2. Dakle, Z 3 Í Z 2 .

S druge strane, Z 3 sadrži poluprsten prirodnih brojeva, budući da se svaki prirodni broj n uvijek može prikazati kao

n = n / – 1 O Z 3 ,

što znači Z 1 Í Z 3 , jer je Z 1 minimalni prsten koji sadrži prirodne brojeve. Koristeći već dokazanu činjenicu da je Z 2 = Z 1, dobivamo Z 1 = Z 2 = Z 3. Teorem je dokazan.

Iako se na prvi pogled može činiti da u navedenim definicijama cijelih brojeva nema aksioma, ove definicije su aksiomske, jer sve tri definicije kažu da je skup cijelih brojeva prsten. Stoga su aksiomi u aksiomatskoj teoriji cijelih brojeva uvjeti iz definicije prstena.

Dokažimo to aksiomatska teorija cijelih brojeva je dosljedna. Da bismo to dokazali, potrebno je konstruirati model prstena cijelih brojeva, koristeći očito konzistentnu teoriju (u našem slučaju to može biti samo aksiomatska teorija prirodnih brojeva).

Prema definiciji 3 svaki cijeli broj može se prikazati kao razlika dvaju prirodnih brojeva z = b – a. Pridružimo svakom cijelom broju z odgovarajući par . Nedostatak ove korespondencije je njena dvosmislenost. Konkretno, broj 2 odgovara paru<3, 1 >, i par<4, 2>, kao i mnogi drugi. Broj 0 odgovara paru<1, 1>, i par<2,2>, i par<3, 3>, i tako dalje. Koncept pomaže u izbjegavanju ovog problema parovi ekvivalencije. Recimo taj par ekvivalent par , ako je a +d = b + c (oznaka: @ ).

Uvedena relacija je refleksivna, simetrična i tranzitivna (dokaz prepuštamo čitatelju).

Kao i svaka relacija ekvivalencije, ova relacija generira particiju skupa svih mogućih parova prirodnih brojeva u klase ekvivalencije, koje ćemo označiti kao [ ] (svaka se klasa sastoji od svih parova ekvivalentnih paru ). Sada možemo pridružiti svaki cijeli broj dobro definiranoj klasi ekvivalentnih parova prirodnih brojeva. Skup takvih klasa parova prirodnih brojeva može se koristiti kao model cijelih brojeva. Dokažimo da su svi aksiomi prstena zadovoljeni u ovom modelu. Da bismo to učinili, potrebno je uvesti pojmove zbrajanja i množenja klasa parova. To ćemo učiniti prema sljedećim pravilima:

1) [] + [] = [];

2) [] × [ ] = [].

Pokažimo da su uvedene definicije točne, odnosno da ne ovise o izboru konkretnih predstavnika iz klasa parova. Drugim riječima, ako su parovi ekvivalentni @ I @ , tada su odgovarajući zbrojevi i umnošci ekvivalentni @ , kao i @ .

Dokaz: Primijenimo definiciju ekvivalencije parova:

@ ó a + b 1 = b + a 1 (1),

@ ó c + d 1 = d + c 1 (2).

Zbrajajući jednakosti (1) i (2) član po član, dobivamo:

a + b 1 + c + d 1 = b + a 1 + d + c 1.

Svi članovi u posljednjoj jednakosti su prirodni brojevi, pa imamo pravo primijeniti komutativni i asocijativni zakon zbrajanja, što nas dovodi do jednakosti

(a + c) + (b 1 + d 1)= (b + d) + (a 1 + c 1),

što je ekvivalentno stanju @ .

Da bismo dokazali ispravnost množenja, pomnožimo jednakost (1) sa c, dobivamo:

ac + b 1 s = bc + a 1 s.

Zatim prepisujemo jednakost (1) u obliku b + a 1 = a + b 1 i množimo s d:

bd + a 1 d = ad + b 1 d.

Zbrojimo dobivene jednakosti član po član:

ac + bd + a 1 d + b 1 c = bc + ad + b 1 d + a 1 c,

što znači da @ (drugim riječima, ovdje smo to dokazali × @ ,× ).

Zatim ćemo isti postupak napraviti s jednakošću (2), samo što ćemo je pomnožiti s a 1 i b 1. Dobivamo:

a 1 c + a 1 d 1 = a 1 d + a 1 c 1

b 1 d + b 1 c 1 = b 1 c + b 1 d 1,

a 1 c + b 1 d + b 1 c 1 + a 1 d 1 = a 1 d + b 1 d + b 1 c 1 + a 1 c 1 ó

ó @

(ovdje smo to dokazali × @ ,× ). Koristeći svojstvo tranzitivnosti relacije ekvivalencije parova, dolazimo do tražene jednakosti @ ekvivalentno stanje

× @ ,× .

Time je dokazana ispravnost uvedenih definicija.

Zatim se izravno provjeravaju sva svojstva prstenova: asocijativni zakon zbrajanja i množenja za klase parova, komutativni zakon zbrajanja i distributivni zakoni. Navedimo kao primjer dokaz asocijativnog zakona zbrajanja:

+ ( +) = + = .

Budući da su sve komponente parova brojeva prirodne

= <(a + c) +m), (b + d) +n)> =

= <(a + c), (b + d)> + = ( + ) +.

Preostali zakoni se provjeravaju na isti način (imajte na umu da odvojena transformacija lijeve i desne strane tražene jednakosti u isti oblik može biti korisna tehnika).

Također je potrebno dokazati prisutnost neutralnog elementa dodavanjem. Oni mogu poslužiti kao klasa parova oblika [<с, с>]. Stvarno,

[] + [] = [] @ [], jer

a + c + b = b + c + a (vrijedi za sve prirodne brojeve).

Štoviše, za svaku klasu parova [ ] postoji suprotnost tome. Takva bi klasa bila klasa [ ]. Stvarno,

[] + [] = [] = [] @ [].

Također se može dokazati da je uvedeni skup klasa parova komutativni prsten s identitetom (jedinica može biti klasa parova [ ]), te da su za njihove slike u ovom modelu sačuvani svi uvjeti za definicije operacija zbrajanja i množenja za prirodne brojeve. Konkretno, razumno je uvesti sljedeći element za prirodni par prema pravilu:

[] / = [].

Provjerimo ovim pravilom valjanost uvjeta C1 i C2 (iz definicije zbrajanja prirodnih brojeva). Uvjet C1 (a + 1 = a /) u ovom slučaju bit će prepisan kao:

[] + [] =[] / = []. Stvarno,

[] + [] = [] = [], jer

a + c / +b = a + b + 1 + c = b + c + a +1 = b + c + a /

(podsjećamo još jednom da su sve komponente prirodne).

Uvjet C2 će izgledati ovako:

[] + [] / = ([] + []) / .

Transformirajmo odvojeno lijevu i desnu stranu ove jednakosti:

[] + [] / = [] + [] = [] / .

([] + []) / = [] / =[<(a + c) / , b + d>] =[].

Dakle, vidimo da su lijeva i desna strana jednake, što znači da je uvjet C2 istinit. Dokaz uvjeta U1 prepuštamo čitatelju. uvjet U2 je posljedica zakona distribucije.

Dakle, konstruiran je model prstena cijelih brojeva, pa je, prema tome, aksiomatska teorija cijelih brojeva konzistentna ako je konzistentna aksiomatska teorija prirodnih brojeva.

Svojstva operacija nad cijelim brojevima:

2) a×(–b) = –a×b = –(ab)

3) – (– a) = a

4) (–a)×(–b) = ab

5) a×(–1) = – a

6) a – b = – b + a = – (b – a)

7) – a – b = – (a +b)

8) (a – b) ×c = ac – bc

9) (a – b) – c = a – (b + c)

10) a – (b – c) = a – b + c.

Dokazi svih svojstava ponavljaju dokaze odgovarajućih svojstava za prstenove.

1) a + a×0 = a×1 + a×0 = a ×(1 + 0) = a×1 = a, odnosno a×0 je neutralan element u smislu sabiranja.

2) a×(–b) + ab = a(–b + b) = a×0 = 0, odnosno element a×(–b) je suprotan elementu a×b.

3) (– a) + a = 0 (po definiciji suprotnog elementa). Slično (– a) +(– (– a)) = 0. Izjednačavanjem lijevih strana jednakosti i primjenom zakona poništavanja dobivamo – (– a) = a.

4) (–a)×(–b) = –(a×(–b)) = –(–(a×b)) = ab.

5) a×(–1) + a = a×(–1) + a×1 = a×(–1 + 1) = a×0 = 0

a×(–1) + a = 0

a×(–1) = –a.

6) Po definiciji razlika a – b je broj x takav da je a = x + b. Dodavanjem –b s lijeve strane desnoj i lijevoj strani jednakosti i korištenjem komutativnog zakona dobivamo prvu jednakost.

– b + a + b – a = –b + b + a – a = 0 + 0 = 0, čime je druga jednakost dokazana.

7) – a – b = – 1×a – 1×b = –1×(a +b) = – (a +b).

8) (a – b) ×c = (a +(–1)× b) ×c = ac +(–1)×bc = ac – bc

9) (a – b) – c = x,

a – b = x + c,

a – (b + c) = x, tj

(a – b) – c = a – (b + c).

10) a – (b – c) = a + (– 1)×(b – c) = a + (– 1×b) + (–1)× (– c) = a – 1×b + 1× c = = a – b + c.

Zadaci za samostalno rješavanje

Broj 2.1. U desnom stupcu tablice pronađite parove ekvivalentne parovima navedenim u lijevom stupcu tablice.

A)<7, 5>	1) <5, 7>
b)<2, 3>	2) <1, 10>
V)<10, 10>	3) <5, 4>
G)<6, 2>	4) <15, 5>
	5) <1, 5>
	6) <9, 9>

Za svaki par označite njegovu suprotnost.

Broj 2.2. Izračunati

A) [<1, 5>] + [ <3, 2>]; b)[<3, 8>] + [<4, 7>];

V) [<7, 4>] – [<8, 3>]; G) [<1, 5>] – [ <3, 2>];

e) [<1, 5>] × [ <2, 2>]; e) [<2, 10>]× [<10, 2>].

Broj 2.3. Za model cijelih brojeva opisan u ovom odjeljku provjerite komutativni zakon zbrajanja, asocijativne i komutativne zakone množenja i zakone distribucije.

U raznim granama matematike, kao iu primjeni matematike u tehnici, često se događa situacija da se algebarske operacije ne izvode na brojevima, već na objektima druge prirode. Na primjer, zbrajanje matrica, množenje matrica, zbrajanje vektora, operacije na polinomima, operacije na linearnim transformacijama itd.

Definicija 1. Prsten je skup matematičkih objekata u kojem su definirane dvije akcije - “zbrajanje” i “množenje”, koje povezuju uređene parove elemenata s njihovim “zbrojem” i “proizvodom”, koji su elementi istog skupa. Ove radnje zadovoljavaju sljedeće zahtjeve:

1.a+b=b+a(komutativnost zbrajanja).

2.(a+b)+c=a+(b+c)(asocijativnost zbrajanja).

3. Postoji nulti element 0 takav da a+0=a, za bilo koji a.

4. Za bilo koga a postoji suprotni element − a takav da a+(−a)=0.

5. (a+b)c=ac+bc(lijeva distributivnost).

5".c(a+b)=ca+cb(desna distributivnost).

Zahtjevi 2, 3, 4 znače da skup matematičkih objekata čini skupinu, a zajedno s točkom 1 radi se o komutativnoj (Abelovoj) grupi s obzirom na zbrajanje.

Kao što se vidi iz definicije, u općoj definiciji prstena nema ograničenja na množenje, osim distributivnosti s zbrajanjem. Međutim, u različitim situacijama postaje potrebno razmotriti prstenove s dodatnim zahtjevima.

6. (ab)c=a(bc)(asocijativnost množenja).

7.ab=ba(komutativnost množenja).

8. Postojanje jednog elementa 1, tj. takav a·1=1· a=a, za bilo koji element a.

9. Za bilo koji element stavke a postoji inverzni element a−1 takav da aa −1 =a −1 a= 1.

U raznim prstenovima 6, 7, 8, 9 mogu se izvoditi zasebno ili u raznim kombinacijama.

Prsten se naziva asocijativnim ako je zadovoljen uvjet 6, komutativnim ako je zadovoljen uvjet 7, komutativnim i asocijativnim ako su zadovoljeni uvjeti 6 i 7. Prsten se naziva prstenom s identitetom ako je zadovoljen uvjet 8.

Primjeri prstenova:

1. Skup kvadratnih matrica.

Stvarno. Ispunjenje točaka 1-5, 5" je očito. Nulti element je nulta matrica. Osim toga, točka 6 (asocijativnost množenja), ispunjena je točka 8 (jedinički element je jedinična matrica). Točke 7 i 9 nisu ispunjeni jer je u općem slučaju množenje kvadratnih matrica nekomutativno, a također ne postoji uvijek inverz kvadratne matrice.

2. Skup svih kompleksnih brojeva.

3. Skup svih realnih brojeva.

4. Skup svih racionalnih brojeva.

5. Skup svih cijelih brojeva.

Definicija 2. Svaki sustav brojeva koji sadrži zbroj, razliku i umnožak bilo koja dva njegova broja naziva se prsten s brojevima.

Primjeri 2-5 su prstenovi s brojevima. Brojevni prstenovi su također svi parni brojevi, kao i svi cijeli brojevi djeljivi bez ostatka nekim prirodnim brojem n. Imajte na umu da skup neparnih brojeva nije prsten jer zbroj dva neparna broja je paran broj.

Def. Prsten K naziva se prstenom cijelih brojeva ako je aditivna grupa prstena K aditivna grupa cijelih brojeva i množenje u prstenu K je komutativno i nastavlja množenje prirodnih brojeva (u sustavu od N prirodnih brojeva).

T1. Neka - aditivna skupina cijelih brojeva, u njoj postoji prirodno množenje i 1 je jedinica sustava od N prirodnih brojeva. Tada je algebra Z= je prsten cijelih brojeva.

O tome govori doc. Pokažimo da je algebra Z komutativni prsten. Po uvjetu, algebra - aditivna grupa prstena je Abelova grupa, kao aditivna grupa cijelih brojeva.

Neka su a, b, c proizvoljni elementi skupa Z. Oni se mogu prikazati kao radost prirodnih brojeva. Neka je (1) a=m-n, b=p-q, c=r-s (m, n, p, q, r, s N).

Prirodno množenje u Z određeno je formulom (2) a*b=(m-n)*(p-q)=(mp+nq)-(mq+np).

Prirodno množenje je komutativno, budući da je b*a= (p-q)*(m-n)=(pm+qn)-(pn+qm), a zbrajanje i množenje prirodnih brojeva su komutativno.

Prirodno množenje je asocijativno. Zapravo, na temelju (1) i (2) imamo:

a*(b*c)=(m-n)[(p-q)(r-s)]=(m-n)[(pr+qs)-(ps-qr)]=(mpr+mqs+nps+nqr)-(mps+ mqr +npr+nqs);

(a*b)*c=[(m-n)(p-q)](r-s)=[(mp+nq)-(mq+np)](r-s)=(mpr+nqr+mqs+nps)-(mps+ nqs +mqr+npr).

Dakle, zbog komutativnosti zbrajanja prirodnih brojeva, a*(b*c)= (a*b)*c.

Element 1 je neutralan u odnosu na prirodno množenje. U stvari, za bilo koji a iz 2 imamo a*1=(m-n)(1-0)=m*1-n*1=m-n=a.

Stoga algebra je komutativni monoid.

Def. Ako za cijele brojeve a i b postoji prirodan broj k takav da je a + k = b i k 0, tada kažu da je "a manje od ili b" i pišu a b ako i samo ako b

T2. Neka je Z= prsten cijelih brojeva. Tada: 1) za bilo koje cijele brojeve a i b zadovoljen je jedan i samo jedan od tri uvjeta: a

2) za svaki cijeli broj a zadovoljen je jedan i samo jedan od tri uvjeta: a<0, a=0, 0

3) stav< монотонно относительно сложения, т.е. для любых целых a, bи c

a

4) stav<монотонно относительно умножения, т.е. для любых целых a, bи с

ako a 0, zatim ac

T. o dijeljenju s ostatkom. Neka je a cijeli broj i b prirodni broj različit od nule. Dijeljenje broja a i b s ostatkom znači njegovo predstavljanje u obliku a=bq+r, gdje je 0 r

Dijeljenje s ostatkom je uvijek izvedivo, a parcijalni kvocijent i ostatak jednoznačno su određeni djeljenikom i djeliteljem.

T. Za bilo koje cijele brojeve a, b i b>0, postoji jedinstveni par cijelih brojeva q i r koji zadovoljavaju uvjete: (1) a=bq+r i 0 r

O tome govori doc. Dokažimo da postoji barem jedan par brojeva q, r koji zadovoljava uvjete (1). Prvo, razmotrimo slučaj kada je a prirodan broj. Fiksiramo b i indukcijom po a dokažemo da (2) postoji par cijelih brojeva q, r koji zadovoljava (1).

Za a=0, izjava (2) je istinita, jer je 0=b*0+0. Pretpostavimo da (2) vrijedi za a=n, tj. postoje cijeli brojevi q, r takvi da je (3) n=bq+r i 0 r

Najveći zajednički djelitelj. Cijeli broj c nazivamo zajedničkim djeliteljem cijelih brojeva a 1, ..., a n ako je c djelitelj svakog od tih brojeva.

Def. Najveći zajednički djelitelj cijelih brojeva a 1, ..., a n je njihov zajednički djelitelj koji je djeljiv bilo kojim zajedničkim djeliteljem tih brojeva.

Cijeli brojevi a 1 , …, a n nazivaju se relativno prostim ako im je najveći zajednički djelitelj jednak jedan.

Nad brojevima a 1 , …, a n označava se Nad(a 1 , …, a n), a pozitivna Nad ovih brojeva označava se nod(a 1 , …, a n).

Dalje 1. Ako je d gcd cijelih brojeva a 1, ..., a n, tada se skup svih zajedničkih djelitelja tih brojeva podudara sa skupom svih djelitelja broja d.

Sljedeće 2. Bilo koja dva gcd-a cijelih brojeva a 1 , …, a n su pridružena, tj. mogu se razlikovati samo u predznaku. Ako je d gcd brojeva a 1, …, a n, onda je broj (-d) također gcd ovih brojeva.

Euklidov algoritam. Metoda za pronalaženje gcd dvaju cijelih brojeva.

Ponuda. Neka su a i b dva cijela broja, b≠0 i (1) a=bq+r (0 r<|b|).

Tada je čvor(a,b)=nod(b,r).

O tome govori doc. Iz (1) slijedi da je svaki zajednički djelitelj brojeva a i b djelitelj broja r=a-bq i svaki zajednički djelitelj brojeva b i r djelitelj broja a. Dakle, skup svih zajedničkih djelitelja brojeva a i b podudara se sa skupom svih zajedničkih djelitelja brojeva b i r. Slijedi da se pozitivni zajednički djelitelj brojeva a i b podudara s pozitivnim zajedničkim djeliteljem brojeva b i r, tj. čvor(a,b)=čvor(b,r).

Ako je b|a, gdje je b≥1, tada je očito čvor(a,b)=b. Za pronalaženje čvorova dvaju cijelih brojeva koristi se metoda "sekvencijalnog dijeljenja", koja se naziva Euklidov algoritam. Bit ove metode je da se, zbog gore dokazane tvrdnje, problem nalaženja čvorova brojeva a i b svodi na jednostavniji zadatak nalaženja čvorova brojeva b i r, gdje je 0≤r.<|b|. Если r=0, то нод(a,b)=b. Если же r≠0, то рассуждения повторяем, отправляясь от bи r. В результате получим цепочку равенств.

Ako je a=0, tada je b=0*c=0 i teorem je točan. Ako je a≠0, tada iz (1) slijedi cd=1. Prema teoremu, iz jednakosti cd=1 slijedi da je d= 1. Osim toga, a=bd; dakle a= b. dokazano.

Najmanji zajednički višekratnik. Cijeli broj nazivamo zajedničkim višekratnikom cijelih brojeva a 1, ..., a n ako je djeljiv sa svakim od tih brojeva.

Def. Najmanji zajednički višekratnik cijelih brojeva a 1, ..., a n je njihov zajednički višekratnik koji dijeli bilo koji zajednički višekratnik ovih brojeva. Ob-i: LCM(a 1, …, a n). Pozitivni najmanji zajednički višekratnik brojeva a 1, ..., a n, različit od nule, izražava se kroz .

Sl-tj. Bilo koja dva najmanje zajednička višekratnika cijelih brojeva a 1 , …, a n pridružena su u Z, tj. mogu se razlikovati samo u predznaku. Ako je broj m LCM(a 1 , …, a n), tada je broj (-m) LCM(a 1 , …, a n).

Sl-tj. Ako je m najmanji zajednički višekratnik brojeva a 1, ..., a n, tada se skup svih zajedničkih višekratnika tih brojeva podudara sa skupom svih višekratnika broja m.