Kruh celých čísel. P-adic celých čísel. na téma: Gaussův celočíselný kruh
Def. Kruh K se nazývá kruh celých čísel, jestliže aditivní grupa kruhu K je aditivní grupa celých čísel a násobení v kruhu K je komutativní a pokračuje v násobení přirozených čísel (v systému N přirozených čísel).
T1. Nechat
Doc. Ukažme, že algebra Z je komutativní okruh. Podle podmínky, algebry
Nechť a, b, c jsou libovolné prvky množiny Z. Lze je znázornit jako radost z přirozených čísel. Nechť (1) a=m-n, b=p-q, c=r-s (m, n, p, q, r, s N).
Přirozené násobení v Z je určeno vzorcem (2) a*b=(m-n)*(p-q)=(mp+nq)-(mq+np).
Přirozené násobení je komutativní, protože b*a= (p-q)*(m-n)=(pm+qn)-(pn+qm) a sčítání a násobení přirozených čísel jsou komutativní.
Přirozené množení je asociativní. Ve skutečnosti na základě (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).
Kvůli komutativitě sčítání přirozených čísel tedy a*(b*c)= (a*b)*c.
Prvek 1 je neutrální s ohledem na přirozené množení. Ve skutečnosti pro jakékoli a od 2 máme a*1=(m-n)(1-0)=m*1-n*1=m-n=a.
Proto algebra
Def. Pokud pro celá čísla a a b existuje přirozené číslo k takové, že a + k = b a k 0, pak řeknou, že „a je menší než nebo b“ a napíší a T2. Nechť Z= 2) pro libovolné celé číslo a je splněna pouze jedna ze tří podmínek: a<0, a=0, 0 3) postoj< монотонно относительно сложения, т.е. для любых целых a, bи c A 4) postoj<монотонно относительно умножения, т.е. для любых целых a, bи с Pokud T. o rozdělení se zbytkem. Nechť a je celé číslo a b přirozené číslo jiné než nula. Dělení čísla a a b zbytkem znamená jeho reprezentaci ve tvaru a=bq+r, kde 0 r Dělení se zbytkem je vždy proveditelné a částečný kvocient a zbytek jsou jednoznačně určeny dividendou a dělitelem. T. Pro všechna celá čísla a, b a b>0 existuje jedinečná dvojice celých čísel q a r, která splňují podmínky: (1) a=bq+r a 0 r Doc. Dokažme, že existuje alespoň jedna dvojice čísel q, r splňující podmínky (1). Nejprve uvažujme případ, kdy a je přirozené číslo. Zafixujeme b a dokážeme indukcí na a, že (2) existuje dvojice celých čísel q, r splňujících (1). Pro a=0 platí tvrzení (2), protože 0=b*0+0. Předpokládejme, že (2) platí pro a=n, tj. existují celá čísla q, r taková, že (3) n=bq+r a 0 r Největší společný dělitel. Celé číslo c se nazývá společný dělitel celých čísel a 1, ..., a n, pokud c je dělitel každého z těchto čísel. Def. Největší společný dělitel celých čísel a 1, ..., a n je jejich společný dělitel, který je dělitelný libovolným společným dělitelem těchto čísel. Celá čísla a 1 , …, a n se nazývají relativně prvočísla, pokud je jejich největší společný dělitel roven jedné. 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). Další 1. Je-li d gcd celých čísel a 1, ..., a n, pak se množina všech společných dělitelů těchto čísel shoduje s množinou všech dělitelů čísla d. Další 2. Libovolná dvě gcd celých čísel a 1 , …, a n jsou spojena, tzn. se může lišit pouze znaménkem. Jestliže d je gcd čísel a 1, …, a n, pak číslo (-d) je také gcd těchto čísel. Euklidův algoritmus. Metoda pro nalezení gcd dvou celých čísel. Nabídka. Nechť a a b jsou dvě celá čísla, b≠0 a (1) a=bq+r (0 r<|b|). Pak node(a,b)=nod(b,r). Doc. Z (1) vyplývá, že libovolný společný dělitel čísel aab je dělitelem čísla r=a-bq a libovolný společný dělitel čísel b a r je dělitelem čísla a. Proto se množina všech společných dělitelů čísel a a b shoduje s množinou všech společných dělitelů čísel b a r. Z toho vyplývá, že kladný společný dělitel čísel a a b se shoduje s kladným společným dělitelem čísel b a r, tzn. node(a,b)=nod(b,r). Jestliže b|a, kde b≥1, pak zjevně uzel(a,b)=b. K nalezení uzlů dvou celých čísel se používá metoda „sekvenčního dělení“, zvaná Euklidovský algoritmus. Podstata této metody spočívá v tom, že díky výše dokázanému tvrzení se problém hledání uzlů čísel a a b redukuje na jednodušší úlohu najít uzly čísel b a r, kde 0≤r<|b|. Если r=0, то нод(a,b)=b. Если же r≠0, то рассуждения повторяем, отправляясь от bи r. В результате получим цепочку равенств. Pokud a=0, pak b=0*c=0 a věta je pravdivá. Pokud a≠0, pak z (1) vyplývá cd=1. Podle věty z rovnosti cd=1 vyplývá, že d= 1. Navíc a=bd; proto a = b. Osvědčený. Nejmenší společný násobek. Celé číslo se nazývá společný násobek celých čísel a 1, ..., a n, pokud je dělitelné každým z těchto čísel. Def. Nejmenší společný násobek celých čísel a 1, ..., a n je jejich společný násobek, který dělí libovolný společný násobek těchto čísel. Ob-i: LCM(a 1, …, an). Kladný nejmenší společný násobek čísel a 1, ..., a n, odlišný od nuly, je vyjádřen pomocí . Sl-ie. Jakékoli dva nejmenší společné násobky celých čísel a 1 , …, a n jsou spojeny v Z, tj. se může lišit pouze znaménkem. Jestliže číslo m je LCM(a 1 , …, an), potom číslo (-m) je LCM(a 1 , …, an). Sl-ie. Je-li m nejmenší společný násobek čísel a 1, ..., a n, pak se množina všech společných násobků těchto čísel shoduje s množinou všech násobků m.
Protože číselné pole je algebraickým rozšířením pole Q (\displaystyle \mathbb (Q) ), kterýkoli jeho prvek je kořenem nějakého polynomu s racionálními koeficienty (to znamená, že je algebraický). Každý prvek je navíc kořenem polynomu s celočíselnými koeficienty, protože všechny racionální koeficienty lze vynásobit součinem jmenovatelů. Pokud je daný prvek kořenem nějakého unitárního polynomu s celočíselnými koeficienty, nazývá se celočíselný prvek (nebo algebraické celé číslo). Ne všechny prvky číselného pole jsou celá čísla: lze například snadno ukázat, že jediné celočíselné prvky Q (\displaystyle \mathbb (Q) ) jsou obyčejná celá čísla. Lze dokázat, že součet a součin dvou algebraických celých čísel je opět algebraické celé číslo, takže celočíselné prvky tvoří podkruh číselného pole K (\displaystyle K), volal prsten celku pole K (\displaystyle K) a označeno . Pole neobsahuje nulové dělitele a tato vlastnost se dědí při předání podkruhu, takže kruh celých čísel je integrální; soukromé kruhové pole O K (\displaystyle (\mathcal (O))_(K))- to je pole samotné K (\displaystyle K). Okruh celých čísel libovolného číselného pole má následující tři vlastnosti: je integrálně uzavřený, noetherovský a jednorozměrný. Komutativní prsten s takovými vlastnostmi se nazývá Dedekindův prsten, po Richardu Dedekindovi. V libovolném Dedekindově kruhu dochází k jedinečnému rozkladu nenulových ideálů na součin prvočísel. Ne každý kruh celých čísel však splňuje vlastnost faktoriálnosti: již pro kruh celých čísel kvadratického pole O Q (− 5) = Z [ − 5 ] (\displaystyle (\mathcal (O))_(\mathbb (Q) ((\sqrt (-5))))=\mathbb (Z) [(\sqrt ( -5))]) rozklad není jedinečný: Zavedením normy na tento prstenec můžeme ukázat, že tyto expanze jsou skutečně různé, to znamená, že jedno nelze získat od druhého vynásobením invertibilním prvkem. Míra porušení faktoriálové vlastnosti se měří pomocí grupy ideálních tříd, tato grupa pro kruh celých čísel je vždy konečná a její pořadí se nazývá počet tříd. Celý základčíselné pole F stupně n- to je hodně z n prvky kruhu celočíselných polí F, takže libovolný prvek kruhu celých čísel O F pole F Jediný způsob, jak to napsat, je jako Z-lineární kombinace prvků B; tedy pro kohokoli X z O F existuje pouze jeden rozklad Kde m i- obyčejná celá čísla. V tomto případě jakýkoli prvek F lze napsat jako Kde m i- racionální čísla. Poté následují celé prvky F se vyznačují vlastností, že to jsou přesně ty prvky, pro které vše m i Celý. Pomocí nástrojů, jako je lokalizace a Frobeniův endomorfismus, lze takový základ vytvořit pro libovolné číselné pole. Jeho konstrukce je součástí mnoha systémů počítačové algebry. Nechat F- číselné pole stupně n. Mezi všemi možnými základy F(Jak Q-vektorový prostor), existují mocninné základy, tedy základy tvaru pro některé X ∈ F. Podle věty o primitivním prvku je takový X vždy existuje, říká se tomu primitivní prvek tohoto rozšíření. Algebraické číselné pole je konečnorozměrný vektorový prostor nad Q (\displaystyle \mathbb (Q) )(jeho rozměr označujeme jako n (\displaystyle n)), a násobení libovolným prvkem pole je lineární transformace tohoto prostoru. Nechat e 1 , e 2 , … e n (\displaystyle e_(1),e_(2),\ldots e_(n))- nějaký základ F, pak transformace x ↦ α x (\displaystyle x\mapsto \alpha x) odpovídá matici A = (a i j) (\displaystyle A=(a_(ij))), určený podmínkou α 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 této matice závisí na volbě báze, ale všechny invarianty matice, jako je determinant a stopa, na ní nezávisí. V kontextu algebraických rozšíření se nazývá determinant matice násobení prvků norma tento prvek (označený N (x) (\displaystyle N(x))); maticová stopa - další prvek(označeno Tr (x) (\displaystyle (\text(Tr))(x))). Stopa prvku je lineární funkcionál na F: Norma je multiplikativní a homogenní funkce: Jako výchozí základ můžete zvolit celočíselný základ, násobení celočíselným algebraickým číslem (tedy prvkem kruhu celých čísel) v tomto základu bude odpovídat matici s celočíselnými prvky. Proto stopa a norma jakéhokoli prvku kruhu celých čísel jsou celá čísla. Nechat d (\displaystyle d)- - celočíselný prvek, protože je kořenem redukovaného polynomu x 2 − d (\displaystyle x^(2)-d)). Na tomto základě násobení podle a + b d (\displaystyle a+b(\sqrt (d))) odpovídá matici Proto, N (a + b d) = a 2 − d b 2 (\displaystyle N(a+b(\sqrt (d)))=a^(2)-db^(2)). Na prvcích kruhu tato norma nabývá celočíselných hodnot. Norma je homomorfismus multiplikativní grupy Z [ d ] (\displaystyle \mathbb (Z) [(\sqrt (d))]) na multiplikativní skupinu Z (\displaystyle \mathbb (Z) ), proto se norma invertibilních prvků prstence může rovnat pouze 1 (\displaystyle 1) nebo − 1 (\displaystyle -1). K vyřešení Pellovy rovnice a 2 − d b 2 = 1 (\displaystyle a^(2)-db^(2)=1), stačí najít všechny invertibilní prvky kruhu celých čísel (nazývaného také kroužkové jednotky) a identifikovat mezi nimi ty, které mají normu 1 (\displaystyle 1). Podle Dirichletovy věty o jednotě jsou všechny invertibilní prvky daného kruhu mocniny jednoho prvku (až do násobení − 1 (\displaystyle -1)), proto k nalezení všech řešení Pellovy rovnice stačí najít jedno základní řešení. Federální agentura pro vzdělávání Státní vzdělávací instituce vyššího odborného vzdělávání Vjatka státní humanitární univerzita Katedra matematické analýzy a metod Závěrečná kvalifikační práce Dokončeno: student 5. ročníku Matematická fakulta Gnusov V.V. ___________________________ Vědecký poradce: odborný asistent katedry algebra a geometrie Semenov A.N. ___________________________ Recenzent: Kandidát fyziky a matematiky vědy, docent Katedra algebry a geometrie Kovyazina E.M. ___________________________ Připuštěn k obhajobě u Státní atestační komise Hlava Oddělení________________ Vechtomov E.M. « »________________ Děkan fakulty ___________________ Varankina V.I. Okruh komplexních celých čísel K. Gauss přišel na myšlenku možnosti a nutnosti rozšíření pojmu celé číslo v souvislosti s hledáním algoritmů pro řešení porovnávání druhého stupně. Koncept celého čísla přenesl na čísla formuláře Teorie vyvinutá K. Gaussem, popsaná v jeho díle Aritmetická studia, byla zásadním objevem pro teorii čísel a algebru. V závěrečné práci byly stanoveny tyto cíle: 1. Rozvinout teorii dělitelnosti v kruhu Gaussových čísel. 2. Zjistěte povahu prvočísel Gaussových čísel. 3. Ukažte použití Gaussových čísel při řešení běžných diofantických úloh. Uvažujme množinu komplexních čísel. Analogicky s množinou reálných čísel v ní lze rozlišit určitou podmnožinu celých čísel. Sada čísel formuláře Protože kruh Gaussových čísel je podmnožinou komplexních čísel, platí pro něj některé definice a vlastnosti komplexních čísel. Tedy například pro každé Gaussovo číslo Platnost těchto vlastností je triviálně ověřována pomocí modulu. Na okraj si všimneme, že (2), (3), (5) jsou také platné pro všechna komplexní čísla. Okruh Gaussových čísel je komutativní kruh bez dělitelů 0, protože je podkruhem pole komplexních čísel. To implikuje multiplikativní kontraktilitu prstence Podívejme se, která Gaussova čísla budou invertibilní. Násobení je neutrální Jak vidíte, ne všechna Gaussova čísla budou invertibilní. Je proto zajímavé zamyslet se nad otázkou dělitelnosti. Jako obvykle to říkáme Snadno zkontrolovat (8), (9), (11), (12). Spravedlnost (7) vyplývá z (2) a (10) vyplývá z (6). Vzhledem k vlastnosti (9), prvky množiny Z kurzu programování víme, že celé číslo může být v paměti počítače reprezentováno různými způsoby, zejména tato reprezentace závisí na tom, jak je popsána: jako hodnota typu integer, nebo real, nebo string. Navíc ve většině programovacích jazyků jsou celá čísla chápána jako čísla z velmi omezeného rozsahu: typický případ je od -2 15 = -32768 do 2 15 - 1 = 32767. Systémy počítačová algebra poradí si s velkými celými čísly, zejména každý takový systém umí vypočítat a zobrazit čísla ve tvaru 1000 v desítkové soustavě! (více než tisíc znaků). V tomto kurzu se budeme zabývat reprezentací celých čísel v symbolické formě a nebudeme se podrobně zabývat tím, jaká paměť je přidělena pro záznam jednoho znaku (bit, bajt nebo jiný). Nejběžnější je reprezentovat celá čísla v poziční číselné soustavy. Takový systém je určen volbou číselného základu, například 10. Sada desetinných celých čísel je obvykle popsána takto: Psaná definice celých čísel poskytuje jednoznačnou reprezentaci každého takového čísla a podobná definice (pouze možná s jiným základem) se používá ve většině systémů počítačová algebra. Pomocí této reprezentace je vhodné implementovat aritmetické operace na celých číslech. Navíc sčítání a odčítání jsou relativně „levné“ operace, zatímco násobení a dělení jsou „drahé“. Při posuzování složitosti aritmetických operací je třeba vzít v úvahu jak náklady na elementární operaci (jednociferné), tak počet jednociferných operací k provedení jakékoli operace s vícemístnými čísly. Složitost násobení a dělení je dána především tím, že s rostoucí délkou čísla (jeho záznam v libovolné číselné soustavě) roste počet elementárních operací podle kvadratického zákona, na rozdíl od lineárního zákon pro sčítání a odčítání. Navíc to, co obvykle nazýváme algoritmem pro dělení víceciferných čísel, je ve skutečnosti založeno na hledání (často poměrně významné) možné další číslice kvocientu a nestačí jednoduše použít pravidla pro dělení jednociferných čísel. čísla. Pokud je základ číselné soustavy velký (často to může být řádově 2 30), je tato metoda neúčinná. Nechť je přirozené číslo (zapsané v desítkové soustavě). Aby získal jeho záznam Dáno: A-přirozené číslo v desítkové číselné soustavě k > 1-přirozené číslo Potřebné: A-záznam čísla A v k-ární číselné soustavě Začátek i:= 0 cyklu dokud A > 0 bi:= A (mod k ) A:= i:= i + 1 konec cyklu dA:= i - 1 konec K obnovení desetinného čísla z posloupnosti jeho k-ary notace se používá následující algoritmus: Dáno: k > 1-přirozená číselná posloupnost číslic reprezentujících číslo A v k-ární soustavě Potřebné: A-zápis čísla A v desítkové soustavě Začátek A:= 0 cyklus až do konce posloupnosti b:= další prvek posloupnosti A:= A * k + b konec smyčky Konec 1.2. CVIČENÍ. Vysvětlete, proč se dělení používá k převodu čísla z desítkové soustavy do k-ární soustavy a násobení se používá k převodu z k-ární soustavy do desítkové soustavy. Vynásobením „sloupcem“ dvou dvouciferných čísel v desítkové soustavě provádíme následující operace: (10a + b)(10c + d) = 100ac + 10(ad + bc) + bd, tj. 4 operace násobení jednociferných čísel, 3 operace sčítání a 2 operace násobení mocninou radixu, které jsou redukovány na posun. Při posuzování složitosti můžete vzít v úvahu všechny elementární operace bez dělení vahami (v tomto příkladu máme 9 elementárních operací). S tímto přístupem se problém optimalizace algoritmu redukuje na minimalizaci celkového počtu elementárních operací. Lze však mít za to, že násobení je „dražší“ operace než sčítání, které je naopak „dražší“ než směna. Pokud vezmeme v úvahu pouze nejdražší operace, dostaneme to multiplikativní Obtížnost násobení dvouciferných čísel ve sloupci je 4. Část 5 pojednává o algoritmech pro výpočet největších společných dělitelů a hodnotí jejich složitost. Uvažovaná reprezentace není jedinou kanonickou reprezentací celých čísel. Jak již bylo uvedeno, pro výběr kanonické reprezentace můžete využít jedinečnost rozkladu přirozeného čísla na prvočinitele. Tuto reprezentaci celého čísla lze použít v těch úlohách, kde se používají pouze operace násobení a dělení, protože jsou velmi „levné“, ale náklady na operace sčítání a odčítání neúměrně rostou, což brání použití takové reprezentace. V některých problémech poskytuje opuštění kanonické reprezentace významný nárůst výkonu, zejména lze použít částečnou faktorizaci čísla. Podobná metoda je užitečná zejména při práci nikoli s čísly, ale s polynomy. Je-li známo, že během činnosti programu jsou všechna celá čísla, se kterými se setkáváme ve výpočtech, omezena v absolutní hodnotě nějakou danou konstantou, pak lze k definování takových čísel použít jejich systém zbytků modulo nějaká koprimá čísla, jejichž součin přesahuje zmíněná konstanta. Výpočty se zbytkovými třídami jsou obecně rychlejší než aritmetika s vícenásobnou přesností. A s tímto přístupem by se aritmetika s vícenásobnou přesností měla používat pouze při zadávání nebo výstupu informací. Všimněte si, že spolu s kanonickými reprezentacemi v systémech počítačová algebra Používají se i další reprezentace. Zejména je žádoucí, aby přítomnost nebo nepřítomnost znaménka „+“ před celým číslem neovlivnila vnímání počítačem. Pro kladná čísla se tedy získá nejednoznačná reprezentace, ačkoli forma záporných čísel je jednoznačně určena. Dalším požadavkem je, že vnímání čísla by nemělo být ovlivněno přítomností nul před první platnou číslicí. 1.3. CVIČENÍ.Příklady
a + b i (\displaystyle a+bi) Kde a (\displaystyle a) A b (\displaystyle b) racionální čísla, i (\displaystyle i)- pomyslná jednotka. Takové výrazy lze sčítat a násobit podle obvyklých pravidel pro operace s komplexními čísly a každý nenulový prvek má inverzní hodnotu, jak je vidět 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ývá, že racionální Gaussova čísla tvoří pole, což je dvourozměrný prostor nad (tedy kvadratické pole). Číselné pole celé číslo kroužek
Rozklad primeru a třídní skupina
Základy číselných polí
Celý základ
Mocenský základ
Norma a stopa
Příklad použití normy
viz také
Literatura
Matematická fakulta
výuka matematikyna téma: Gaussův celočíselný kruh.
Úvod.KAPITOLA 1. ROZDĚLENÍ V KRUHU GAUSSOVÝCH ČÍSEL.
1.1 VRATNÉ A SPOJENÉ PRVKY.
v -ary číselném systému můžete použít následující algoritmus (označuje celočíselnou část čísla):
