Iz kursa programiranja je poznato da se cijeli broj može predstaviti u memoriji računala na različite načine, a posebno ovaj prikaz ovisi o tome kako je opisan: kao vrijednost tipa integer, ili real, ili string. Istovremeno, u većini programskih jezika, cijeli brojevi se shvataju kao brojevi iz vrlo ograničenog raspona: tipičan slučaj je od -2 15 = -32768 do 2 15 - 1 = 32767 . Sistemi kompjuterska algebra se bavi velikim cijelim brojevima, posebno, svaki takav sistem može izračunati i prikazati brojeve kao što je 1000 u decimalnom zapisu! (više od hiljadu znakova).
U ovom kursu ćemo razmotriti predstavljanje cijelih brojeva u simboličkom obliku i nećemo ulaziti u detalje o tome koliko memorije je dodijeljeno za pisanje jednog znaka (bita, bajta ili drugog). Najčešći je prikaz cijelih brojeva u pozicioni brojevni sistemi. Takav sistem je određen izborom baze broja, na primjer, 10. Skup decimalnih cijelih brojeva obično se opisuje na sljedeći način:
Pisana definicija cijelih brojeva daje jedinstvenost reprezentacije svakog takvog broja, a slična definicija (samo, možda s drugačijom osnovom) se koristi u većini sistema. kompjuterska algebra. Koristeći ovu reprezentaciju, zgodno je implementirati aritmetičke operacije nad cijelim brojevima. Istovremeno, sabiranje i oduzimanje su relativno "jeftine" operacije, dok su množenje i dijeljenje "skupi". Prilikom procjene složenosti aritmetičkih operacija treba uzeti u obzir i cijenu elementarne operacije (jednobitne) i broj jednobitnih operacija za izvođenje bilo koje operacije nad višecifrenim brojevima. Složenost množenja i dijeljenja posljedica je, prije svega, činjenice da se s povećanjem dužine broja (njegova notacija u bilo kojem brojevnom sistemu) povećava broj elementarnih operacija prema kvadratnom zakonu, za razliku od linearni za sabiranje i oduzimanje. Osim toga, ono što obično nazivamo algoritam višecifrenog dijeljenja zapravo se temelji na nabrajanju (često vrlo značajnom) moguće sljedeće cifre količnika, i nije dovoljno samo koristiti pravila za dijeljenje jednocifrenih brojeva. Sa velikom bazom brojevnog sistema (često može biti reda veličine 2 30 ), ovaj metod je neefikasan.
Neka je prirodan broj (zapisan u decimalnom sistemu). Da dobijem njegov dosije 
u -arnom brojevnom sistemu, možete koristiti sljedeći algoritam (označava cijeli dio broja):
Dato: A-prirodni broj u decimalnom zapisu k > 1-prirodni broj Potreba: A-zapis broja A u k-decimalnom zapisu Započni i:= 0 ciklus dok je A > 0 bi:= A (mod k) A:= i := i + 1 kraj ciklusa dA:= i - 1 kraj
Sljedeći algoritam se koristi za vraćanje decimalnog broja iz niza njegove k-arne notacije:
Dato je: k > 1-prirodni broj niz cifara koji predstavlja broj A u k-arnom sistemu Potreba: A-zapis broja A u decimalnom zapisu Početak A:= 0 ciklusa 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 pretvaranje broja iz decimalnog sistema u k-broj, a množenje za pretvaranje iz k-broja u decimalni.
Množenjem sa "stupcem" dva dvocifrena broja u decimalnom brojevnom sistemu, izvodimo sljedeće operacije:
(10a + b)(10c + d) = 100ac + 10(ad + bc) + bd,
odnosno 4 operacije množenja jednocifrenih brojeva, 3 operacije sabiranja i 2 operacije množenja po stepenu brojevne baze koje se svode na pomak. Pri procjeni složenosti mogu se uzeti u obzir sve elementarne operacije bez odvajanja po težini (u ovom primjeru imamo 9 elementarnih operacija). Zadatak optimizacije algoritma se u ovom pristupu svodi na minimiziranje ukupnog broja elementarnih operacija. Može se, međutim, smatrati da je množenje "skuplja" operacija od sabiranja, koja je, pak, "skuplja" od pomaka. Uzimajući u obzir samo najskuplje operacije, dobijamo to multiplikativno složenost množenja dvocifrenih brojeva sa "kolona" je 4.
Odjeljak 5 razmatra algoritme za izračunavanje najvećih zajedničkih djelitelja i procjenjuje njihovu složenost.
Razmatrana reprezentacija nije jedina kanonska reprezentacija cijelih brojeva. Kao što je već napomenuto, da bi se izabrala kanonska reprezentacija, može se koristiti jedinstvenost faktorizacije prirodnog broja u proste faktore. Takav prikaz cijelog broja može se koristiti u onim problemima gdje se koriste samo operacije množenja i dijeljenja, budući da postaju vrlo "jeftine", međutim cijena operacija sabiranja i oduzimanja raste neproporcionalno, što onemogućuje korištenje takvog prikaza. U nekim problemima, odbacivanje kanonske reprezentacije daje značajan dobitak u brzini, posebno se može koristiti parcijalna faktorizacija broja. Slična metoda je posebno korisna kada se ne radi s brojevima, već s polinomima.
Ako je poznato da su u toku rada programa svi celi brojevi koji se susreću u proračunima ograničeni u apsolutnoj vrednosti nekom datom konstantom, onda za postavljanje takvih brojeva, njihov sistem ostataka u modulu nekih koprostih brojeva, čiji je proizvod veći od pomenuta konstanta, može se koristiti. Izračuni s klasama ostataka su općenito brži od aritmetike višestruke preciznosti. A sa ovim pristupom, aritmetiku višestruke preciznosti treba koristiti samo prilikom unosa ili izlaza informacija.
Imajte na umu da, zajedno sa kanonskim reprezentacijama u sistemima kompjuterska algebra koriste se i drugi prikazi. Posebno je poželjno da prisustvo ili odsustvo znaka "+" ispred celog broja ne utiče na percepciju računara o tome. Tako se za pozitivne brojeve dobija dvosmislen prikaz, iako je oblik negativnih brojeva jednoznačno određen.
Drugi zahtjev je da na percepciju broja ne bi trebalo utjecati prisustvo nula prije prve značajne cifre.
1.3. VJEŽBE.
- Procijenite broj jednocifrenih množenja koji se koriste pri množenju m-cifrenog broja sa n-cifrenim brojem u koloni.
- Pokažite da se dva dvocifrena broja mogu pomnožiti koristeći samo 3 jednocifrena množenja i povećanjem broja sabiranja.
- Pronađite algoritam za dijeljenje dugih brojeva koji ne zahtijeva puno nabrajanja da biste pronašli prvu cifru količnika.
- Opišite algoritam za pretvaranje prirodnih brojeva iz m-arnog sistema brojeva u n-arni.
- V Rimska numeracija za pisanje brojeva koriste se sljedeći simboli: I - jedan, V - pet, X - deset, L - pedeset, C - sto, D - petsto, M - hiljadu. Simbol se smatra negativnim ako se desno od njega nalazi simbol većeg broja, a u suprotnom pozitivnim. Na primjer, broj 1948 u ovom sistemu će biti napisan ovako: MCMXLVIII. Formulirajte algoritam za pretvaranje broja iz rimskog u decimalni i obrnuto. Implementirajte rezultirajući algoritam na jednom od algoritamskih jezika (na primjer, C). Ograničenja početnih podataka: 1<= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
- Formulirajte algoritam i napišite program za sabiranje prirodnih brojeva u rimskoj numeraciji.
- Reći ćemo da imamo posla sa brojevnim sistemom mješovite ili vektorske, ako nam je dat vektor od n prirodnih brojeva M = (m 1 , . . . ,m n) (baza) 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 osnovu podataka (dan u sedmici, sati, minute, sekunde) određuje koliko je sekundi prošlo od početka sedmice (ponedjeljak, 0, 0, 0) = 0, i vrši inverznu transformaciju.
Primjeri
a + b i (\displaystyle a+bi) gdje a (\displaystyle a) i b (\displaystyle b) racionalni brojevi, i (\displaystyle i) je imaginarna jedinica. Takvi izrazi se mogu sabirati i množiti prema uobičajenim pravilima operacija sa kompleksnim brojevima, a svaki element različit od nule ima inverzni element, što se vidi iz jednakosti (a + bi) (aa 2 + b 2 − ba 2 + b 2 i) = (a + bi) (a − bi) a 2 + b 2 = 1. (\displaystyle (a+bi)\left(( \frac (a)(a^(2)+b^(2)))-(\frac (b)(a^(2)+b^(2)))i\right)=(\frac (( a+bi)(a-bi))(a^(2)+b^(2)))=1.) Iz ovoga slijedi da racionalni Gausovi brojevi formiraju polje koje je dvodimenzionalni prostor nad (tj. kvadratno polje).- Općenito, za bilo koji cijeli broj bez kvadrata d (\displaystyle d) Q (d) (\displaystyle \mathbb (Q) ((\sqrt (d))))će biti kvadratna ekspanzija polja Q (\displaystyle \mathbb (Q) ).
- kružno polje Q (ζ n) (\displaystyle \mathbb (Q) (\zeta _(n))) dobijeno dodavanjem Q (\displaystyle \mathbb (Q) ) primitivni korijen n th moć jedinstva. Polje takođe mora sadržavati sve svoje moći (tj. sve korijene n th moć jedinstva), njegova dimenzija preko Q (\displaystyle \mathbb (Q) ) jednaka je Eulerovoj funkciji φ (n) (\displaystyle \varphi (n)).
- Realni i kompleksni brojevi imaju beskonačnu moć nad racionalnim brojevima, tako da nisu brojevna polja. Ovo proizilazi iz neprebrojivosti: svako numeričko polje je prebrojivo.
- Polje svih algebarskih brojeva A (\displaystyle \mathbb (A) ) nije brojčano. Iako ekspanzija A ⊃ Q (\displaystyle \mathbb (A) \supset \mathbb (Q) ) algebarski, nije konačan.
Prsten cijelih brojeva numeričko polje
Pošto je polje broja algebarsko proširenje polja Q (\displaystyle \mathbb (Q) ), bilo koji od njegovih elemenata je korijen nekog polinoma s racionalnim koeficijentima (odnosno, algebarski je). Štaviše, svaki element je korijen polinoma s cijelim koeficijentima, budući da je moguće pomnožiti sve racionalne koeficijente umnoškom nazivnika. Ako je dati element korijen nekog unitarnog polinoma s cijelim koeficijentima, naziva se cjelobrojnim elementom (ili algebarskim cijelim brojem). Nisu svi elementi brojevnog polja cijeli brojevi: na primjer, lako je pokazati da su jedini cjelobrojni elementi Q (\displaystyle \mathbb (Q) ) su regularni cijeli brojevi.
Može se dokazati da je zbir i proizvod dvaju algebarskih cijelih brojeva opet algebarski cijeli broj, pa cjelobrojni elementi čine podprsten brojevnog polja K (\displaystyle K) pozvao cijeli prsten polja K (\displaystyle K) i označeno sa . Polje ne sadrži djelitelje nule i ovo svojstvo se nasljeđuje pri prelasku na podprsten, tako da je prsten cijelih brojeva integralan; privatna kutija za prstenje O K (\displaystyle (\mathcal (O))_(K)) je samo polje K (\displaystyle K). Prsten cijelih brojeva bilo kojeg brojevnog polja ima sljedeća tri svojstva: integralno je zatvoren, neterovski i jednodimenzionalan. Komutativni prsten sa ovim svojstvima naziva se Dedekind, po Richardu Dedekindu.
Dekompozicija na proste brojeve i grupu klasa
U proizvoljnom Dedekindovom prstenu postoji jedinstvena dekompozicija nenultih ideala u proizvod jednostavnih. Međutim, svaki prsten cijelih brojeva ne zadovoljava faktorijalno svojstvo: već za prsten cijelih brojeva, kvadratno polje OQ (− 5) = Z [ − 5 ] (\displaystyle (\mathcal (O))_(\mathbb (Q) ((\sqrt (-5))))=\mathbb (Z) [(\sqrt ( -5))) dekompozicija nije jedinstvena:
6 = 2 ⋅ 3 = (1 + − 5) (1 − − 5) (\displaystyle 6=2\cdot 3=(1+(\sqrt (-5)))(1-(\sqrt (-5) )))Uvođenjem norme na ovaj prsten možemo pokazati da su ta proširenja zaista različita, odnosno da se jedno od drugog ne može dobiti množenjem inverzibilnim elementom.
Stepen narušavanja faktorijalne osobine se mjeri pomoću idealne grupe klasa, ova grupa za prsten cijelih brojeva je uvijek konačna i njen red se naziva broj klasa.
Brojne baze polja
cela osnova
cela osnova polje broja F stepen n- to je set
B = {b 1 , …, b n}od n elementi prstena cjelobrojnih polja F, tako da bilo koji element prstena cijelih brojeva O F polja F može se napisati samo kao Z-linearna kombinacija elemenata B; odnosno za bilo koje x od O F postoji jedinstvena dekompozicija
x = m 1 b 1 + … + m n b n,gdje m i su regularni cijeli brojevi. U ovom slučaju, bilo koji element F može se napisati kao
m 1 b 1 + … + m n b n,gdje m i su racionalni brojevi. Nakon toga cijeli elementi F odlikuju se svojstvom da su to upravo oni elementi za koje sve m i cijeli.
Koristeći alate kao što su lokalizacija i Frobeniusov endomorfizam, može se konstruirati takva osnova za bilo koje polje brojeva. Njegova konstrukcija ugrađena je u mnoge sisteme kompjuterske algebre.
Osnova snage
Neka F- polje brojčanog stepena n. Među svim mogućim bazama F(kako Q-vektorski prostor), postoje baze snage, odnosno baze forme
B x = {1, x, x 2 , …, x n−1 }za neke x ∈ F. Prema teoremi o primitivnim elementima, takva x uvek postoji, to se zove primitivni element ovo proširenje.
Norma i trag
Polje algebarskih brojeva je konačno-dimenzionalni vektorski prostor nad Q (\displaystyle \mathbb (Q) )(njegovu dimenziju označavamo kao n (\displaystyle n)), a množenje sa proizvoljnim elementom polja je linearna transformacija ovog prostora. Neka e 1 , e 2 , … e n (\displaystyle e_(1),e_(2),\ldots e_(n))- bilo koja osnova F, zatim transformacija x ↦ α x (\displaystyle x\mapsto \alpha x) odgovara matrici A = (a i j) (\displaystyle A=(a_(ij))), određen uslovom
α e i = ∑ j = 1 n a i j e j , a i j ∈ Q . (\displaystyle \alpha e_(i)=\sum _(j=1)^(n)a_(ij)e_(j),\quad a_(ij)\in \mathbf (Q) .)
Elementi ove matrice zavise od izbora baze, međutim, sve invarijante matrice, kao što su determinanta i trag, ne ovise o njoj. U kontekstu algebarskih ekstenzija, determinanta matrice množenja elemenata naziva se norma ovaj element (označen N (x) (\displaystyle N(x))); matrični trag - element u tragovima(označeno Tr (x) (\displaystyle (\text(Tr))(x))).
Trag elementa je linearni funkcional na F:
Tr (x + y) = Tr (x) + Tr (y) (\displaystyle (\text(Tr))(x+y)=(\text(Tr))(x)+(\text(Tr)) (y)) i Tr (λ x) = λ Tr (x) , λ ∈ Q (\displaystyle (\text(Tr))(\lambda x)=\lambda (\text(Tr))(x),\lambda \in \mathbb (Q) ).Norma je multiplikativna i homogena funkcija:
N (x y) = N (x) ⋅ N (y) (\displaystyle N(xy)=N(x)\cdot N(y)) i N (λ x) = λ n N (x) , λ ∈ Q (\displaystyle N(\lambda x)=\lambda ^(n)N(x),\lambda \in \mathbb (Q) ).Kao početnu osnovu, možete odabrati cjelobrojnu osnovu, množenje cjelobrojnim algebarskim brojem (tj. elementom prstena cijelih brojeva) u ovoj bazi će odgovarati matrici s cjelobrojnim elementima. Dakle, trag i norma bilo kojeg elementa prstena cijelih brojeva su cijeli brojevi.
Primjer korištenja norme
Neka d (\displaystyle d)- - cjelobrojni element, budući da je korijen redukovanog polinoma x 2 − d (\displaystyle x^(2)-d)). U ovoj osnovi, množenje sa a + b d (\displaystyle a+b(\sqrt (d))) odgovara matrici
(a d b b a) (\displaystyle (\begin(pmatrix)a&db\\b&a\end(pmatrix)))dakle, N (a + b d) = a 2 − d b 2 (\displaystyle N(a+b(\sqrt (d)))=a^(2)-db^(2)). Na elementima prstena ova norma uzima cjelobrojne vrijednosti. Norma je homomorfizam multiplikativne grupe Z [ d ] (\displaystyle \mathbb (Z) [(\sqrt (d))]) po multiplikativnoj grupi Z (\displaystyle \mathbb (Z) ), pa norma invertibilnih elemenata prstena može biti jednaka samo 1 (\displaystyle 1) ili − 1 (\displaystyle -1). Za rješavanje Pellove jednačine a 2 − d b 2 = 1 (\displaystyle a^(2)-db^(2)=1), dovoljno je pronaći sve inverzibilne elemente prstena cijelih brojeva (također tzv prstenaste jedinice) i među njima odaberite one sa normom 1 (\displaystyle 1). Prema Dirichletovoj teoremi o jedinici, svi invertibilni elementi datog prstena su potencije jednog elementa (do množenja sa − 1 (\displaystyle -1)), dakle, za pronalaženje svih rješenja Pellove jednadžbe, dovoljno je pronaći jedno fundamentalno rješenje.
vidi takođe
Književnost
- H. Koch. Algebarska teorija brojeva. - M.: VINITI, 1990. - T. 62. - 301 str. - (Rezultati nauke i tehnologije. Serija "Savremeni problemi matematike. Fundamentalni pravci".).
- Čebotarev N.G. Osnove Galoisove teorije. Dio 2. - M.: Uvodnik URSS, 2004.
- Weil G. Algebarska teorija brojeva. Per. sa engleskog - M. : Editorial URSS, 2011.
- Serge Lang, Algebarska teorija brojeva, drugo izdanje, Springer, 2000
Vidjeli smo da se operacije nad polinomima svode na operacije nad njihovim koeficijentima. Istovremeno, za sabiranje, oduzimanje i množenje polinoma dovoljne su tri aritmetičke operacije - dijeljenje brojeva nije bilo potrebno. Pošto su zbir, razlika i proizvod dva realna broja opet realni brojevi, sabiranje, oduzimanje i množenje polinoma sa realnim koeficijentima rezultiraju polinomima sa realnim koeficijentima.
Međutim, ne morate uvijek imati posla s polinomima koji imaju realne koeficijente. Postoje slučajevi kada, po samoj suštini stvari, koeficijenti treba da imaju samo celobrojne ili samo racionalne vrednosti. Ovisno o tome koje vrijednosti koeficijenata se smatraju prihvatljivim, svojstva polinoma se mijenjaju. Na primjer, ako uzmemo u obzir polinome s bilo kojim realnim koeficijentima, onda možemo faktorizirati:
Ako se ograničimo na polinome sa cjelobrojnim koeficijentima, onda proširenje (1) nema smisla i moramo smatrati da je polinom nerazložljiv na faktore.
Ovo pokazuje da teorija polinoma suštinski zavisi od toga koji se koeficijenti smatraju prihvatljivim. Daleko od toga da se bilo koji skup koeficijenata može uzeti kao prihvatljiv. Na primjer, razmotrite sve polinome čiji su koeficijenti neparni cijeli brojevi. Jasno je da zbir dva takva polinoma više neće biti polinom istog tipa: na kraju krajeva, zbir neparnih brojeva je paran broj.
Postavimo pitanje: šta su „dobri“ skupovi koeficijenata? Kada zbir, razlika, proizvod polinoma sa koeficijentima date vrste ima koeficijente istog tipa? Da bismo odgovorili na ovo pitanje, uvodimo pojam brojevnog prstena.
Definicija. Neprazan skup brojeva naziva se brojevnim prstenom ako, zajedno sa bilo koja dva broja a i , sadrži njihov zbir, razliku i proizvod. Ovo se takođe kraće izražava tako što se kaže da je brojčani prsten zatvoren operacijama sabiranja, oduzimanja i množenja.
1) Skup cijelih brojeva je numerički prsten: zbir, razlika i proizvod cijelih brojeva su cijeli brojevi. Skup prirodnih brojeva nije numerički prsten, jer razlika prirodnih brojeva može biti negativna.
2) Skup svih racionalnih brojeva je numerički prsten, jer su zbir, razlika i proizvod racionalnih brojeva racionalni.
3) Formira brojčani prsten i skup svih realnih brojeva.
4) Brojevi oblika a gdje a i cijeli brojevi čine numerički prsten. Ovo proizilazi iz odnosa:
5) Skup neparnih brojeva nije brojčani prsten, jer je zbir neparnih brojeva paran. Skup parnih brojeva je numerički prsten.
Prsten u kojem je uvedena relacija "biti veći od nule" (označen sa > 0) naziva se lociran prsten, ako su za bilo koji element ovog prstena zadovoljena dva uslova:
1) jedan jedini od uslova je tačan
a > 0 \/ –a >0 \/ a = 0
2) a > 0 /\ b > 0 => a + b > 0 /\ ab > 0.
Skup u koji se uvodi određeni odnos reda - nestriktni (refleksivno, antisimetrično i tranzitivno) ili strogi (antirefleksivno i tranzitivno) naziva se uredno. Ako je zakon trihotomije zadovoljen, tada se skup naziva linearno uredno. Ako uzmemo u obzir ne proizvoljan skup, već neki algebarski sistem, na primjer, prsten ili polje, tada se za uređenje takvog sistema uvode i zahtjevi monotonosti s obzirom na operacije uvedene u ovaj sistem (algebarska struktura). Dakle naručeni prsten/polje je prsten/polje različit od nule u kojem je uvedena relacija linearnog reda (a > b) koja zadovoljava dva uslova:
1) a > b => a + c > b + c;
2) a > b, c > 0 => a c > b c;
Teorema 1. Svaki locirani prsten je uređeni sistem (prsten).
Zaista, ako se u prsten uvede relacija „biti veći od 0“, tada je moguće uvesti i relaciju veću od dva proizvoljna elementa, ako pretpostavimo da je
a > b a - b > 0.
Takav odnos je odnos strogog, linearnog poretka.
Ova relacija „veće od“ je antirefleksivna, budući da je uslov a > a ekvivalentan uslovu a - a > 0, ovo drugo je u suprotnosti sa činjenicom da je a - a = 0 (prema prvom uslovu lociranog prstena, element ne može biti veći od 0 i jednak 0) . Dakle, izjava a > a je netačna za bilo koji element a, tako da je relacija antirefleksivna.
Dokažimo tranzitivnost: ako je a > b i b > c, onda je a > c. Po definiciji, iz uslova teoreme proizlazi da je a - b > 0 i b - c > 0. Sabiranjem ova dva elementa veća od nule, opet dobijamo element veći od nule (prema drugom uslovu lociranog prstena ):
a - b + b - c \u003d a - c\u003e 0.
Ovo poslednje znači da je a > c. Dakle, uvedena relacija je relacija strogog reda. Štaviše, ova relacija je relacija linearnog reda, odnosno za skup prirodnih brojeva, teorema o trihotomiji:
Za bilo koja dva prirodna broja, tačan je jedan i samo jedan od sljedeća tri iskaza:
Zaista (zbog prvog uslova lociranog prstena) za broj a - b je tačan jedan i samo jedan od uslova:
1) a - b > 0 => a > b
2) - (a - b) = b - a > 0 => b > a
3) a - b = 0 => a = b.
Svojstva monotonosti također vrijede za svaki locirani prsten. Zaista
1) a > b => a - b > 0 => a + c - c - b > 0 => a + c > b + c;
2) a > b / \ c > 0 => a - b > 0 => (prema drugom uslovu lociranog prstena) (a - b) c > 0 => ac - bc > 0 => ac > bc .
Tako smo dokazali da je svaki locirani prsten uređeni prsten (uređeni sistem).
Za bilo koji locirani prsten, sljedeća svojstva će također biti istinita:
a) a + c > b + c => a > b;
b) a > b /\ c > d => a + c > b + d;
c) a > b / \ c< 0=>ac< bc;
Ista svojstva vrijede i za druge znakove.<, , .
Dokažimo, na primjer, svojstvo (c). Po definiciji, iz uslova a > b sledi da je a - b > 0, a iz uslova c< 0 (0 >c) slijedi da je 0 - c > 0, a otuda i broj - c > 0, množimo dva pozitivna broja (a - b) (-c). Rezultat će biti pozitivan i po drugom uslovu lociranog prstena, tj.
(a - b) (-c) > 0 => -ac + bc > 0 => bc - ac > 0 => bc > ac => ac< bc,
Q.E.D.
d) aa = a 2 0;
Dokaz: Prema prvom uslovu lociranog prstena, ili a > 0, ili –a > 0, ili a = 0. Razmotrite ove slučajeve odvojeno:
1) a > 0 => aa > 0 (prema drugom uslovu lociranog prstena) => a 2 > 0.
2) –a > 0 => (–a)(–a) > 0, ali po svojstvu prstena (–a)(–a) = aa = a 2 > 0.
3) a \u003d 0 => aa \u003d a 2 \u003d 0.
Dakle, u sva tri slučaja, 2 je ili veće od nule ili jednako 0, što samo znači da je a 2 ≥ 0 i svojstvo je dokazano (imajte na umu da smo također dokazali da kvadrat elementa lociranog prstena je 0 ako i samo ako je sam element 0).
e) ab = 0 a = 0 \/ b = 0.
Dokaz: Pretpostavimo suprotno (ab =0, ali ni a ni b nisu jednaki nuli). Tada su moguće samo dvije opcije za a, ili a > 0 ili – a > 0 (opcija a = 0 je isključena našom pretpostavkom). Svaki od ova dva slučaja se dijeli na još dva slučaja u zavisnosti od b (ili b > 0 ili – b > 0). Tada su moguće 4 opcije:
a > 0, b > 0 => ab > 0;
– a > 0, b > 0 => ab< 0;
a > 0, – b > 0 => ab< 0;
– a > 0 – b > 0 => ab > 0.
Kao što vidimo, svaki od ovih slučajeva je u suprotnosti sa uslovom ab = 0. Svojstvo je dokazano.
Posljednje svojstvo znači da je locirani prsten područje integriteta, što je također obavezno svojstvo uređenih sistema.
Teorema 1 pokazuje da je svaki locirani prsten uređen sistem. Vrijedi i obrnuto - svaki naručeni prsten se nalazi. Zaista, ako postoji relacija a > b u prstenu i bilo koja dva elementa prstena su uporediva jedan s drugim, onda je 0 također uporediv sa bilo kojim elementom a, to jest ili a > 0 ili a< 0, либо а = 0, что почти точно совпадает с первым условием расположенного кольца, требуется только доказать, что условие а < 0 равносильно в упорядоченном кольце условию –a >0. Da bismo dokazali ovo posljednje, primjenjujemo svojstvo monotonosti uređenih sistema: na desnu i lijevu stranu nejednakosti a< 0 прибавим –а, в результате чего получим требуемое.
Drugi uslov lociranog prstena proizlazi iz svojstava monotonosti i tranzitivnosti:
a > 0, b > 0 => a + b > 0 + b = b > 0 => a + b > 0,
a > 0, b > 0 => ab > 0b = 0 => ab > 0.
Teorema 2. Prsten cijelih brojeva je uređeni prsten (uređeni sistem).
dokaz: Koristimo definiciju 2 prstena cijelih brojeva (vidi 2.1). Prema ovoj definiciji, svaki cijeli broj je ili prirodan broj (broj n je dat kao [
a > 0 a N
Tada je prvi uslov lociranog prstena automatski zadovoljen za cijele brojeve: ako je a prirodno, onda je veće od 0, ako je a suprotno prirodnom, onda je –a prirodno, odnosno također je veće od 0, moguća je i varijanta a = 0, što takođe čini pravu disjunkciju u prvom uslovu lociranog prstena. Valjanost drugog uslova lociranog prstena proizilazi iz činjenice da je zbir i proizvod dva prirodna broja (cijeli brojevi veći od nule) opet prirodan broj, a samim tim i veći od nule.
Tako se sva svojstva uređenih prstenova automatski prenose na sve cijele brojeve. Osim toga, za cijele brojeve (ali ne i za proizvoljno uređene prstenove) vrijedi teorema diskretnosti:
Teorema diskretnosti. Nijedan cijeli broj se ne može umetnuti između dva susjedna cijela broja:
( a, x Z) .
Dokaz: razmotriti sve moguće slučajeve za a i pretpostaviti suprotno, to jest da postoji x takav da
a< x < a +1.
1) ako je a prirodan broj, onda je i a + 1 prirodan broj. Zatim, prema teoremi diskretnosti za prirodne brojeve, nijedan prirodni broj x ne može biti umetnut između a i a / = a + 1, odnosno x, u svakom slučaju, ne može biti prirodan. Ako pretpostavimo da je x = 0, onda je naša pretpostavka to
a< x < a +1
će nas dovesti do stanja a< 0 < a + 1 (здесь мы просто подставили х = 0), откуда видим, что а < 0, что противоречит тому, что а – натуральное. Если х не натуральное и не 0, но х – целое, значит –х – натуральное, тогда х < 0. При этом, согласно нашему предположению, а < x, что по свойству транзитивности опять приводит к тому, что а < 0, что невозможно, так как а – натуральное. Таким образом, для натуральных а утверждение а < x < a +1 всегда ложно, и теорема справедлива.
2) a = 0. Tada je a + 1 = 1. Ako je uslov a< x < a + 1, то мы получим 0 < x < 1, то есть с одной стороны х – натуральное (целое, большее нуля), а с другой стороны х меньше 1, что невозможно для натуральных чисел. Таким образом, для нуля наша теорема справедлива.
3) a je negativan (–a > 0), tada je a + 1 0. Ako je a + 1< 0, то умножая условие а < x < a + 1 на –1 получим:
–a–1< – x < –a,
odnosno dolazimo do situacije koja se razmatra u prvom slučaju (pošto su i -a-1 i -a prirodni), odakle - x ne može biti cijeli broj, pa stoga x ne može biti cijeli broj. Situacija kada je a + 1 = 0 znači da je a = -1, tj.
–1 < x < 0.
Množenjem ove nejednakosti sa (–1) dolazimo do slučaja 2. Dakle, teorema vrijedi u svim situacijama.
Arhimedov Terem. Za bilo koji cijeli broj a i cijeli broj b > 0, postoji pozitivan cijeli broj n takav da je a< bn.
Za prirodno a, teorema je već dokazana, jer uslov b > 0 znači da je broj b prirodan. Za a 0, teorema je također očigledna, jer je desna strana bn prirodan broj, odnosno, također je veća od nule.
U prsten cijelih brojeva (kao u bilo kojem lociranom prstenu) možemo uvesti koncept modula:
|a| = 
.
Važeća svojstva modula:
1) |a + b| |a| + |b|;
2) |a – b| |a| – |b|;
3) |a b| = |a| |b|.
dokaz: 1) Imajte na umu da je iz definicije očigledno da je |a| je vrijednost koja je uvijek nenegativna (u prvom slučaju |a| = a ≥ 0, u drugom slučaju |a| = –a, ali a< 0, откуда –а >0). Nejednakosti |a| ≥ a, |a| ≥ –a (modul je jednak odgovarajućem izrazu ako je nenegativan, a veći od njega ako je negativan). Slične nejednakosti vrijede za b: |b| ≥ b, |b| ≥ -b. Sabiranjem odgovarajućih nejednakosti i primjenom svojstva (b) uređenih prstenova dobijamo
|a| + |b| ≥ a + b |a| + |b| ≥ – a – b.
Prema definiciji modula
|a+b| = 
,
ali oba izraza na desnoj strani jednakosti, kao što je gore prikazano, ne prelaze |a| + |b|, što dokazuje prvo svojstvo modula.
2) Zamenimo u prvom svojstvu a sa a - b. Dobijamo:
|a – b + b| ≤ |a – b| + |b|
|a| ≤ |a – b| + |b|
Pomjeri |b| sa desne strane na lijevu sa suprotnim predznakom
|a| – | b| ≤ |a – b| =>|a-b| |a| – |b|.
Dokaz svojstva 3 prepušta se čitaocu.
Zadatak: Riješite jednačinu u cijelim brojevima
2y 2 + 3xy - 2x 2 + x - 2y \u003d 5.
Rješenje: Faktorizirajte lijevu stranu. Da bismo to učinili, predstavljamo pojam 3xy = – xy + 4xy
2y 2 + 3xy - 2x 2 + x - 2y \u003d 2y 2 - xy + 4xy - 2x 2 + x - 2y \u003d
Y (2y - x) + 2x (2y - x) - (2y - x) \u003d (y + 2x - 1) (2y - x).
Dakle, naša jednačina se može prepisati kao
(y + 2x - 1) (2y - x) = 5.
Pošto to trebamo riješiti u cijelim brojevima, x i y moraju biti cijeli brojevi, što znači da su faktori na lijevoj strani naše jednačine također cijeli brojevi. Broj 5 na desnoj strani naše jednadžbe može se predstaviti kao proizvod cjelobrojnih faktora na samo 4 načina:
5 = 51 = 15 = –5(–1) = –1(–5). Stoga su moguće sljedeće opcije:
1)
2)
3)
4)
Među navedenim sistemima samo (4) ima cjelobrojno rješenje:
x = 1, y = -2.
Zadaci za samostalno rješavanje
br. 2.4. Za elemente a, b, c, d proizvoljno lociranog prstena dokazati svojstva:
a) a + c > b + c => a > b; b) a > b / \ c > d => a + c > b + d.
br. 2.5. Riješite jednadžbe u cijelim brojevima:
|
a) y 2 - 2xy - 2x = 6; b) 2x 2 - 11xy + 12y 2 = 17; c) 35xy + 5x - 7y = 1; d) x 2 - 3xy + 2y 2 = 3; e) |
f) xy + 3x - 5y + 3 = 0; g) 2xy - 3y 2 - 4y + 2x \u003d 2; h) xy 2 + x = 48; i) 1! +2! + 3! + … + n! = y 2 ; j) x 3 - 2y 3 - 4z 3 \u003d 0 |
;br. 2.6. Nađite četverocifreni broj koji je tačan kvadrat i takav da su mu prve dvije cifre jednake jedna drugoj, a posljednje dvije cifre jedna drugoj.
br. 2.7. Nađi dvocifreni broj jednak zbiru njegovih desetica i kvadrata njegovih jedinica.
br. 2.8. Nađite dvocifreni broj koji je jednak dvostrukom umnošku njegovih cifara.
br. 2.9. Dokažite da razlika između trocifrenog broja i broja napisanog istim znamenkama obrnutim redoslijedom ne može biti kvadrat prirodnog broja.
br. 2.10. Pronađite sve prirodne brojeve koji završavaju na 91, koji se nakon brisanja ovih znamenki smanjuju cijeli broj puta.
br. 2.11. Nađite dvocifreni broj jednak kvadratu njegovih jedinica plus kocki njegovih desetica.
br. 2.12. Pronađite šestocifreni broj koji počinje brojem 2, koji se povećava za 3 puta ako prerasporedite ovaj broj na kraj broja.
br. 2.13. Na tabli je napisano više od 40, ali manje od 48 cijelih brojeva. Aritmetička sredina svih ovih brojeva je 3, aritmetička sredina pozitivnih je 4, a aritmetička sredina negativnih je 8. Koliko je brojeva napisano na tabli? Koji je broj veći, pozitivan ili negativan? Koliki je najveći mogući broj pozitivnih brojeva?
br. 2.14. Može li količnik trocifrenog broja i zbroja njegovih cifara biti 89? Može li ovaj količnik biti jednak 86? Koja je najveća moguća vrijednost ovog količnika?
Federalna agencija za obrazovanje
Državna obrazovna ustanova visokog stručnog obrazovanja
Državni univerzitet za humanističke nauke Vjatka
Matematički fakultet
Katedra za matematičku analizu i metode
predavanje matematike
Završni kvalifikacioni rad
na temu: Gausov prsten cijelih brojeva.
Završeno:
Student 5. godine
Matematički fakultet
Gnusov V.V.
___________________________
naučni savjetnik:
viši predavač katedre
algebra i geometrija
Semenov A.N.
___________________________
Recenzent:
Kandidat fizike i matematike nauka, vanredni profesor
Odsjek za algebru i geometriju
Kovyazina E.M.
___________________________
Primljen na odbranu u VAC
Glava Katedra ________________ Vechtomov E.M.
« »________________
Dekan fakulteta ___________________ Varankina V.I.
Uvod.
Prsten cijelih kompleksnih brojeva
otkrio ga je Carl Gauss i po njemu nazvao Gaussian.K. Gauss je došao na ideju o mogućnosti i neophodnosti proširenja koncepta celog broja u vezi sa traženjem algoritama za rešavanje poređenja drugog stepena. Prenio je koncept cijelog broja na brojeve oblika
, gdje su proizvoljni cijeli brojevi, i korijen je jednadžbe Na ovom skupu, K. Gauss je prvi konstruirao teoriju djeljivosti, sličnu teoriji djeljivosti cijelih brojeva. On je potkrijepio valjanost osnovnih svojstava djeljivosti; pokazao da postoje samo četiri inverzibilna elementa u prstenu kompleksnih brojeva: ; dokazao valjanost teoreme o podjeli s ostatkom, teoreme o jedinstvenosti dekompozicije na proste faktore; pokazao koji će prosti prirodni brojevi ostati prosti u prstenu; otkrio prirodu jednostavnih cijelih kompleksnih brojeva.Teorija koju je razvio K. Gauss, opisana u njegovom djelu "Aritmetička istraživanja", bila je fundamentalno otkriće za teoriju brojeva i algebru.
Za rad su postavljeni sljedeći ciljevi:
1. Razviti teoriju djeljivosti u prstenu Gaussovih brojeva.
2. Saznajte prirodu jednostavnih Gaussovih brojeva.
3. Pokažite primjenu Gausovih brojeva u rješavanju običnih Diofantovih problema.
POGLAVLJE 1. DJELJIVOST U PRSTENU GAUSOVIH BROJEVA.
Razmotrimo skup kompleksnih brojeva. Po analogiji sa skupom realnih brojeva, u njemu se može razlikovati podskup cijelih brojeva. Skup brojeva forme
, gdje zvati će se kompleksni cijeli brojevi ili Gausovi brojevi. Lako je provjeriti da li aksiomi prstena vrijede za ovaj skup. Dakle, ovaj skup kompleksnih brojeva je prsten i zove se prsten Gausovih cijelih brojeva . Označimo ga kao , budući da je produžetak prstena elementom: .Budući da je prsten Gaussovih brojeva podskup kompleksnih brojeva, za njega vrijede neke definicije i svojstva kompleksnih brojeva. Na primjer, za svaki Gausov broj
odgovara vektoru koji počinje u tački i završava na . dakle, modul Gausovi brojevi su . Imajte na umu da je u skupu koji se razmatra izraz podmodula uvijek nenegativan cijeli broj. Stoga je u nekim slučajevima praktičnije koristiti norma , odnosno kvadrat modula. Na ovaj način . Možemo razlikovati sljedeća svojstva norme. Za sve Gausove brojeve vrijedi sljedeće: (1) (2) (3) (4) (5) - skup prirodnih brojeva, odnosno pozitivnih cijelih brojeva.Valjanost ovih svojstava se trivijalno provjerava pomoću modula. Usput, napominjemo da (2), (3), (5) također vrijede za sve kompleksne brojeve.
Prsten Gausovih brojeva je komutativni prsten bez djelitelja 0, jer je podprsten polja kompleksnih brojeva. To implicira multiplikativnu kontraktibilnost prstena
, tj. (6)1.1 REVERZIBILNI I LEGIRANI ELEMENTI.
Hajde da vidimo koji će Gausovi brojevi biti reverzibilni. Množenje je neutralno
. Ako je Gausov broj reverzibilan , onda, po definiciji, postoji takav da . Prelaskom na norme, prema svojstvu 3, dobijamo . Ali ove norme su, dakle, prirodne. Dakle, prema svojstvu 4, . Obrnuto, svi elementi ovog skupa su invertibilni, budući da . Dakle, brojevi s normom jednakom jedan će biti reverzibilni, to jest, , .Kao što vidite, neće svi Gausovi brojevi biti reverzibilni. Stoga je zanimljivo razmotriti pitanje djeljivosti. Kao i obično, to kažemo
je podijeljen na ako postoji takav da Za bilo koje Gausove brojeve, kao i invertibilne, svojstva su tačna. (7) (8) (9) (10) , gdje je (11) (12)(8), (9), (11), (12) se lako provjeravaju. Valjanost (7) proizlazi iz (2), a (10) proizlazi iz (6). Zbog svojstva (9), elementi skupa
