Prsteň celých čísel. Krúžok p-adických celých čísel. na tému: Gaussov celočíselný kruh
Def. Kruh K sa nazýva kruh celých čísel, ak aditívna grupa kruhu K je aditívna grupa celých čísel a násobenie v kruhu K je komutatívne a pokračuje v násobení prirodzených čísel (v sústave N prirodzených čísel).
T1. Nechaj
Docentom sa stal doc. Ukážme, že algebra Z je komutatívny okruh. Podľa podmienok, algebry
Nech a, b, c sú ľubovoľné prvky množiny Z. Možno ich znázorniť ako radosť z prirodzených čísel. Nech (1) a=m-n, b=p-q, c=r-s (m, n, p, q, r, s N).
Prirodzené násobenie v Z je určené vzorcom (2) a*b=(m-n)*(p-q)=(mp+nq)-(mq+np).
Prirodzené násobenie je komutatívne, keďže b*a= (p-q)*(m-n)=(pm+qn)-(pn+qm) a sčítanie a násobenie prirodzených čísel sú komutatívne.
Prirodzené množenie je asociatívne. V skutočnosti na základe (1) a (2) máme:
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).
Preto v dôsledku komutatívnosti sčítania prirodzených čísel a*(b*c)= (a*b)*c.
Prvok 1 je neutrálny vzhľadom na prirodzené množenie. V skutočnosti pre akékoľvek a od 2 máme a*1=(m-n)(1-0)=m*1-n*1=m-n=a.
Preto algebra
Def. Ak pre celé čísla a a b existuje prirodzené číslo k také, že a + k = b a k 0, potom povedia, že „a je menšie ako alebo b“ a napíšu a T2. Nech Z= 2) pre akékoľvek celé číslo a je splnená iba jedna z troch podmienok: a<0, a=0, 0 3) postoj< монотонно относительно сложения, т.е. для любых целых a, bи c a 4) postoj<монотонно относительно умножения, т.е. для любых целых a, bи с Ak T. o rozdelení so zvyškom. Nech a je celé číslo a b prirodzené číslo iné ako nula. Delenie čísla a a b zvyškom znamená jeho vyjadrenie v tvare a=bq+r, kde 0 r Delenie so zvyškom je vždy možné a čiastočný kvocient a zvyšok sú jednoznačne určené dividendou a deliteľom. T. Pre všetky celé čísla a, b a b>0 existuje jedinečný pár celých čísel q a r, ktoré spĺňajú podmienky: (1) a=bq+r a 0 r Docentom sa stal doc. Dokážme, že existuje aspoň jedna dvojica čísel q, r, ktorá spĺňa podmienky (1). Najprv si predstavme prípad, keď a je prirodzené číslo. Zafixujeme b a dokážeme indukciou na a, že (2) existuje dvojica celých čísel q, r, ktoré spĺňajú (1). Pre a=0 je tvrdenie (2) pravdivé, pretože 0=b*0+0. Predpokladajme, že (2) platí pre a=n, t.j. existujú celé čísla q, r také, že (3) n=bq+r a 0 r Najväčší spoločný deliteľ. Celé číslo c sa nazýva spoločný deliteľ celých čísel a 1, ..., a n, ak c je deliteľ každého z týchto čísel. Def. Najväčší spoločný deliteľ celých čísel a 1, ..., a n je ich spoločný deliteľ, ktorý je deliteľný akýmkoľvek spoločným deliteľom týchto čísel. Celé čísla a 1 , …, a n sa nazývajú relatívne prvočísla, ak sa ich najväčší spoločný deliteľ rovná jednej. Gcd čísel a 1 , …, a n označujeme gcd(a 1 , …, a n), kladné gcd týchto čísel označujeme nod(a 1 , …, a n). Ďalej 1. Ak d je gcd celých čísel a 1, ..., a n, potom množina všetkých spoločných deliteľov týchto čísel sa zhoduje s množinou všetkých deliteľov čísla d. Ďalej 2. Akékoľvek dve gcd celých čísel a 1 , …, a n sú spojené, t.j. sa môže líšiť iba znakom. Ak d je gcd čísel a 1, …, a n, potom číslo (-d) je tiež gcd týchto čísel. Euklidov algoritmus. Metóda na nájdenie gcd dvoch celých čísel. Ponuka. Nech a a b sú dve celé čísla, b≠0 a (1) a=bq+r (0 r<|b|). Potom node(a,b)=nod(b,r). Docentom sa stal doc. Z (1) vyplýva, že ľubovoľný spoločný deliteľ čísel a a b je deliteľom čísla r=a-bq a ľubovoľný spoločný deliteľ čísel b a r je deliteľom čísla a. Preto sa množina všetkých spoločných deliteľov čísel a a b zhoduje s množinou všetkých spoločných deliteľov čísel b a r. Z toho vyplýva, že kladný spoločný deliteľ čísel a a b sa zhoduje s kladným spoločným deliteľom čísel b a r, t.j. node(a,b)=nod(b,r). Ak b|a, kde b≥1, potom zrejme uzol(a,b)=b. Na nájdenie uzlov dvoch celých čísel sa používa metóda „sekvenčného delenia“, ktorá sa nazýva euklidovský algoritmus. Podstata tejto metódy spočíva v tom, že vďaka vyššie dokázanému tvrdeniu sa problém nájdenia uzlov čísel a a b zredukuje na jednoduchšiu úlohu nájsť uzly čísel b a r, kde 0≤r<|b|. Если r=0, то нод(a,b)=b. Если же r≠0, то рассуждения повторяем, отправляясь от bи r. В результате получим цепочку равенств. Ak a=0, potom b=0*c=0 a veta je pravdivá. Ak a≠0, potom z (1) vyplýva cd=1. Podľa vety z rovnosti cd=1 vyplýva, že d= 1. Okrem toho a=bd; preto a= b. Osvedčené. Najmenší spoločný násobok. Celé číslo sa nazýva spoločný násobok celých čísel a 1, ..., a n, ak je deliteľné každým z týchto čísel. Def. Najmenší spoločný násobok celých čísel a 1, ..., a n je ich spoločný násobok, ktorý delí ľubovoľný spoločný násobok týchto čísel. Ob-i: LCM(a 1, ..., an). Kladný najmenší spoločný násobok čísel a 1, ..., a n, odlišný od nuly, je vyjadrený pomocou . Sl-ie. Akékoľvek dva najmenšie spoločné násobky celých čísel a 1 , …, a n sú spojené v Z, t.j. sa môže líšiť iba znakom. Ak číslo m je LCM(a 1 , ..., a n), potom číslo (-m) je LCM(a 1 , ..., an). Sl-ie. Ak je m najmenší spoločný násobok čísel a 1, ..., a n, potom sa množina všetkých spoločných násobkov týchto čísel zhoduje s množinou všetkých násobkov m.
Keďže číselné pole je algebraickým rozšírením poľa Q (\displaystyle \mathbb (Q) ), ktorýkoľvek z jeho prvkov je koreňom nejakého polynómu s racionálnymi koeficientmi (to znamená, že je algebraický). Okrem toho je každý prvok koreňom polynómu s celočíselnými koeficientmi, pretože všetky racionálne koeficienty možno vynásobiť súčinom menovateľov. Ak je daný prvok koreňom nejakého unitárneho polynómu s celočíselnými koeficientmi, nazýva sa celočíselný prvok (alebo algebraické celé číslo). Nie všetky prvky číselného poľa sú celé čísla: napríklad je ľahké ukázať, že jediné celočíselné prvky Q (\displaystyle \mathbb (Q) ) sú obyčajné celé čísla. Dá sa dokázať, že súčet a súčin dvoch algebraických celých čísel je opäť algebraické celé číslo, takže prvky celého čísla tvoria podkruh číselného poľa K (\displaystyle K), volal prsteň celku poliach K (\displaystyle K) a označené . Pole neobsahuje nulových deliteľov a táto vlastnosť sa pri prechode do podkruhu dedí, takže kruh celých čísel je integrálny; súkromné kruhové pole O K (\displaystyle (\mathcal (O))_(K))- toto je samotné pole K (\displaystyle K). Kruh celých čísel ľubovoľného číselného poľa má tieto tri vlastnosti: je integrálne uzavretý, noetherovský a jednorozmerný. Komutatívny prsteň s takýmito vlastnosťami sa nazýva Dedekindov prsteň podľa Richarda Dedekinda. V ľubovoľnom Dedekindovom kruhu dochádza k jedinečnému rozkladu nenulových ideálov na súčin prvočísel. Nie každý kruh celých čísel však spĺňa vlastnosť faktoriálnosti: už pre kruh celých čísel kvadratického poľa O Q (− 5) = Z [ − 5 ] (\displaystyle (\mathcal (O))_(\mathbb (Q) ((\sqrt (-5))))=\mathbb (Z) [(\sqrt ( -5))]) rozklad nie je jedinečný: Zavedením normy na tento prstenec môžeme ukázať, že tieto expanzie sú skutočne odlišné, to znamená, že jednu nemožno získať od druhej vynásobením invertovateľným prvkom. Miera porušenia faktoriálovej vlastnosti sa meria pomocou skupiny ideálnych tried, táto skupina pre kruh celých čísel je vždy konečná a jej poradie sa nazýva počet tried. Celý základčíselné pole F stupňa n- toto je veľa od n prvky kruhu celočíselných polí F, takže ľubovoľný prvok kruhu celých čísel O F poliach F Jediný spôsob, ako to napísať, je ako Z- lineárna kombinácia prvkov B; teda pre kohokoľvek X od O F existuje len jeden rozklad Kde m i- obyčajné celé čísla. V tomto prípade akýkoľvek prvok F možno napísať ako Kde m i- racionálne čísla. Po tomto sú celé prvky F sa vyznačujú vlastnosťou, že sú to práve tie prvky, pre ktoré všetko m i celý. Pomocou nástrojov, ako je lokalizácia a Frobenius endomorfizmus, je možné vytvoriť takýto základ pre ľubovoľné číselné pole. Jeho konštrukcia je súčasťou mnohých systémov počítačovej algebry. Nechaj F- číselné pole stupňa n. Medzi všetkými možnými základmi F(Ako Q-vektorový priestor), existujú mocninné základy, teda základy tvaru pre niektoré X ∈ F. Podľa vety o primitívnom prvku, napr X vždy existuje, je to tzv primitívny prvok tohto rozšírenia. Algebraické číselné pole je vektorový priestor konečnej dimenzie Q (\displaystyle \mathbb (Q) )(jeho rozmer označujeme ako n (\displaystyle n)) a násobenie ľubovoľným prvkom poľa je lineárna transformácia tohto priestoru. Nechaj e 1 , e 2 , … e n (\displaystyle e_(1),e_(2),\ldots e_(n))- nejaký základ F, potom transformácia x ↦ α x (\displaystyle x\mapsto \alpha x) zodpovedá matici A = (a i j) (\displaystyle A=(a_(ij))), určený stavom α 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) .) Prvky tejto matice závisia od výberu bázy, ale nezávisia od nej všetky invarianty matice, ako je determinant a stopa. V kontexte algebraických rozšírení sa nazýva determinant matice násobenia prvkov normou tento prvok (označený N (x) (\displaystyle N(x))); matricová stopa - ďalší prvok(označené Tr (x) (\displaystyle (\text(Tr))(x))). Stopa prvku je lineárny funkčný na F: Norma je multiplikatívna a homogénna funkcia: Ako počiatočný základ môžete zvoliť celočíselný základ, násobenie celočíselným algebraickým číslom (čiže prvkom kruhu celých čísel) v tomto základe bude zodpovedať matici s celočíselnými prvkami. Preto stopa a norma akéhokoľvek prvku kruhu celých čísel sú celé čísla. Nechaj d (\displaystyle d)- - celočíselný prvok, pretože je koreňom redukovaného polynómu x 2 − d (\displaystyle x^(2)-d)). Na tomto základe násobenie podľa a + b d (\displaystyle a+b(\sqrt (d))) zodpovedá matici teda N (a + b d) = a 2 − d b 2 (\displaystyle N(a+b(\sqrt (d)))=a^(2)-db^(2)). Na prvkoch kruhu má táto norma celočíselné hodnoty. Norma je homomorfizmus multiplikatívnej grupy Z [ d ] (\displaystyle \mathbb (Z) [(\sqrt (d))]) na multiplikatívnu skupinu Z (\displaystyle \mathbb (Z) ), preto sa norma invertovateľných prvkov prstenca môže rovnať iba 1 (\displaystyle 1) alebo − 1 (\displaystyle -1). Na vyriešenie Pellovej rovnice a 2 − d b 2 = 1 (\displaystyle a^(2)-db^(2)=1), stačí nájsť všetky invertibilné prvky kruhu celých čísel (tzv prstencové jednotky) a identifikovať medzi nimi tie, ktoré majú normu 1 (\displaystyle 1). Podľa Dirichletovej vety o jednote sú všetky invertibilné prvky daného kruhu mocniny jedného prvku (až do násobenia − 1 (\displaystyle -1)), preto na nájdenie všetkých riešení Pellovej rovnice stačí nájsť jedno zásadné riešenie. Federálna agentúra pre vzdelávanie Štátna vzdelávacia inštitúcia vyššieho odborného vzdelávania Štátna humanitárna univerzita Vyatka Katedra matematickej analýzy a metód Záverečná kvalifikačná práca Dokončené: študent 5. ročníka Matematická fakulta Gnusov V.V. ___________________________ Vedecký poradca: odborný asistent katedry algebra a geometria Semenov A.N. ___________________________ Recenzent: Kandidát fyziky a matematiky vedy, docent Katedra algebry a geometrie Kovyazina E.M. ___________________________ Prijatý k obhajobe na Štátnej atestačnej komisii Hlava Oddelenie________________ Vechtomov E.M. « »________________ dekanka fakulty ____________________ Varrankina V.I. Prsteň komplexných celých čísel K. Gauss prišiel na myšlienku možnosti a nevyhnutnosti rozšírenia pojmu celé číslo v súvislosti s hľadaním algoritmov na riešenie porovnávaní druhého stupňa. Preniesol pojem celé číslo na čísla formulára Teória vyvinutá K. Gaussom, opísaná v jeho diele Aritmetické štúdie, bola základným objavom pre teóriu čísel a algebru. V záverečnej práci boli stanovené tieto ciele: 1. Rozvinúť teóriu deliteľnosti v kruhu Gaussových čísel. 2. Zistite povahu prvočíselných Gaussových čísel. 3. Ukážte využitie Gaussových čísel pri riešení bežných diofantínskych úloh. Zoberme si množinu komplexných čísel. Analogicky s množinou reálnych čísel v nej možno rozlíšiť určitú podmnožinu celých čísel. Sada čísel formulára Keďže kruh Gaussových čísel je podmnožinou komplexných čísel, platia preň niektoré definície a vlastnosti komplexných čísel. Teda napríklad pre každé Gaussovo číslo Platnosť týchto vlastností je triviálne overená pomocou modulu. Na okraj si všimneme, že (2), (3), (5) platia aj pre akékoľvek komplexné čísla. Okruh Gaussových čísel je komutatívny kruh bez deliteľov 0, keďže ide o podkruh poľa komplexných čísel. To znamená multiplikatívnu kontraktilitu prstenca Pozrime sa, ktoré Gaussove čísla budú invertovateľné. Násobenie je neutrálne Ako vidíte, nie všetky Gaussove čísla budú invertovateľné. Je preto zaujímavé zamyslieť sa nad otázkou deliteľnosti. Ako obvykle, hovoríme to Ľahko skontrolovať (8), (9), (11), (12). Spravodlivosť (7) vyplýva z (2) a (10) vyplýva z (6). Vzhľadom na vlastnosť (9), prvky množiny Z kurzu programovania vieme, že celé číslo môže byť reprezentované v pamäti počítača rôznymi spôsobmi, najmä táto reprezentácia závisí od toho, ako je opísaná: ako hodnota typu integer, alebo real, alebo string. Navyše, vo väčšine programovacích jazykov sa celé čísla chápu ako čísla z veľmi obmedzeného rozsahu: typický prípad je od -2 15 = -32768 do 2 15 - 1 = 32767. systémy počítačová algebra poradí si s veľkými celými číslami, najmä každý takýto systém dokáže vypočítať a zobraziť čísla v tvare 1000 v desiatkovom zápise! (viac ako tisíc znakov). V tomto kurze sa budeme zaoberať reprezentáciou celých čísel v symbolickej forme a nebudeme sa podrobne zaoberať tým, aká pamäť je pridelená na záznam jedného znaku (bit, bajt alebo iný). Najbežnejšie je reprezentovať celé čísla v pozičné číselné sústavy. Takýto systém je určený výberom číselného základu, napríklad 10. Množina celých desatinných čísel je zvyčajne opísaná takto: Písomná definícia celých čísel dáva jednoznačnú reprezentáciu každého takéhoto čísla a podobná definícia (iba možno s iným základom) sa používa vo väčšine systémov počítačová algebra. Pomocou tejto reprezentácie je vhodné implementovať aritmetické operácie na celých číslach. Navyše sčítanie a odčítanie sú relatívne „lacné“ operácie, zatiaľ čo násobenie a delenie sú „drahé“. Pri posudzovaní zložitosti aritmetických operácií by sa mali brať do úvahy náklady na elementárnu operáciu (jednociferné), ako aj počet jednociferných operácií na vykonanie akejkoľvek operácie s viaccifernými číslami. Zložitosť násobenia a delenia je spôsobená predovšetkým skutočnosťou, že so zvyšujúcou sa dĺžkou čísla (jeho zaznamenaním v ľubovoľnej číselnej sústave) rastie počet elementárnych operácií podľa kvadratického zákona, na rozdiel od lineárneho zákon na sčítanie a odčítanie. Navyše to, čo zvyčajne nazývame algoritmom delenia viacciferných čísel, je v skutočnosti založené na vyhľadávaní (často dosť významnej) možnej ďalšej číslice kvocientu a nestačí jednoducho použiť pravidlá na delenie jednociferných čísel. čísla. Ak je základ číselnej sústavy veľký (často to môže byť rádovo 2 30), táto metóda je neúčinná. Nech je prirodzené číslo (zapísané v desiatkovej sústave). Získať jeho záznam Dané: A-prirodzené číslo v desiatkovej číselnej sústave k > 1-prirodzené číslo Potrebné: A-zápis čísla A v k-árnej číselnej sústave Začiatok i:= 0 cyklu, kým A > 0 bi:= A (mod k ) A:= i:= i + 1 koniec cyklu dA:= i - 1 koniec Na obnovenie desatinného čísla zo sekvencie jeho k-ary notácie sa používa nasledujúci algoritmus: Dané: k > 1-prirodzené číslo postupnosť číslic reprezentujúcich číslo A v k-ovej sústave Potrebné: A-zápis čísla A v desiatkovej sústave Začiatok A:= 0 cyklus až do konca postupnosti b:= ďalší prvok postupnosti A:= A * k + b koniec slučky Koniec 1.2. CVIČENIE. Vysvetlite, prečo sa delenie používa na prevod čísla z desiatkovej sústavy do k-árovej sústavy a násobenie sa používa na prevod z k-árovej sústavy do desiatkovej sústavy. Vynásobením dvoch dvojciferných čísel v desiatkovej sústave pomocou „stĺpca“ vykonáme nasledujúce operácie: (10a + b)(10c + d) = 100ac + 10(ad + bc) + bd, teda 4 operácie násobenia jednociferných čísel, 3 operácie sčítania a 2 operácie násobenia mocninou radixu, ktoré sú redukované na posun. Pri posudzovaní zložitosti môžete brať do úvahy všetky základné operácie bez delenia váhami (v tomto príklade máme 9 základných operácií). S týmto prístupom sa problém optimalizácie algoritmu redukuje na minimalizáciu celkového počtu elementárnych operácií. Dá sa však usúdiť, že násobenie je „drahšia“ operácia ako sčítanie, ktoré je naopak „drahšie“ ako posun. Ak vezmeme do úvahy len najdrahšie operácie, dostaneme to multiplikatívne Náročnosť násobenia dvojciferných čísel v stĺpci je 4. Časť 5 rozoberá algoritmy na výpočet najväčších spoločných deliteľov a hodnotí ich zložitosť. Uvažovaná reprezentácia nie je jedinou kanonickou reprezentáciou celých čísel. Ako už bolo uvedené, na výber kanonického zobrazenia môžete použiť jedinečnosť rozkladu prirodzeného čísla na prvočísla. Táto reprezentácia celého čísla sa dá použiť v tých úlohách, kde sa používajú iba operácie násobenia a delenia, pretože sú veľmi „lacné“, ale náklady na operácie sčítania a odčítania sa neúmerne zvyšujú, čo bráni použitiu takejto reprezentácie. V niektorých problémoch poskytuje opustenie kanonickej reprezentácie významný nárast výkonu, najmä je možné použiť čiastočnú faktorizáciu čísla. Podobná metóda je užitočná najmä pri práci nie s číslami, ale s polynómami. Ak je známe, že počas činnosti programu sú všetky celé čísla, s ktorými sa stretávame pri výpočtoch, obmedzené v absolútnej hodnote nejakou danou konštantou, potom na definovanie takýchto čísel možno použiť ich systém zvyškov modulo niektoré spolučísla, ktorých súčin presahuje spomínaná konštanta. Výpočty s triedami zvyškov sú vo všeobecnosti rýchlejšie ako aritmetika s viacnásobnou presnosťou. A s týmto prístupom by sa aritmetika s viacerými presnosťami mala používať iba pri zadávaní alebo výstupe informácií. Všimnite si, že spolu s kanonickými reprezentáciami v systémoch počítačová algebra Používajú sa aj iné reprezentácie. Predovšetkým je žiaduce, aby prítomnosť alebo neprítomnosť znamienka „+“ pred celým číslom neovplyvnila jeho vnímanie počítačom. Pre kladné čísla sa teda získa nejednoznačná reprezentácia, hoci tvar záporných čísel je jednoznačne určený. Ďalšou požiadavkou je, že vnímanie čísla by nemalo byť ovplyvnené prítomnosťou núl pred prvou platnou číslicou. 1.3. CVIČENIA.Príklady
a + b i (\displaystyle a+bi) Kde a (\displaystyle a) A b (\displaystyle b) racionálne čísla, i (\displaystyle i)- pomyselná jednotka. Takéto výrazy možno sčítať a násobiť podľa bežných pravidiel pre operácie s komplexnými číslami a každý nenulový prvok má inverznú hodnotu, ako je zrejmé z rovnosti (a + b i) (a a 2 + b 2 − b a 2 + b 2 i) = (a + b i) (a − b i) 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.) Z toho vyplýva, že racionálne Gaussove čísla tvoria pole, ktoré je dvojrozmerným priestorom nad (teda kvadratickým poľom). Celočíselný kruh číselného poľa
Rozklad primeru a triedna skupina
Základy číselných polí
Celý základ
Silový základ
Norma a stopa
Príklad použitia normy
pozri tiež
Literatúra
Matematická fakulta
vyučovanie matematikyna tému: Gaussov celočíselný kruh.
Úvod.KAPITOLA 1. DELENIE V krúžku GAUSSOVÝCH ČÍSEL.
1.1 REVERZITEĽNÉ A SPOJENÉ PRVKY.
v -ary číselnom systéme môžete použiť nasledujúci algoritmus (označuje celú časť čísla):
