05 - Obory integrity a dělitelnost
pátek 13. května 2016
9:46
Obory integrity a dělitelnost (okruhy polynomů, pravidla dělitelnosti, Gaussovy a Eukleidovy okruhy).
[link]
Obor integrity
Obor integrity je komutativní okruh R s jednotkovým prvkem, pro který navíc platí axiom
∀𝑎∈𝑅, 𝑎≠0   ∀𝑏∈𝑅,𝑏≠0    𝑎⋅𝑏≠0
Trošku jiný pohled na obor integity je, že se skládá z komutativní (Abelovské) grupy  a monoidu: (M, ⊕, ⊗)
(M, ⊕) je komutativní (Abelovská) grupa
(M, ⊗) je monoid
a ⊗ b ≠ „0“
Okruhy polynomů
Okruh polynomů je takový okruh, který je tvořen množinou polynomů s koeficienty z nějakého jiného okruhu. Jedná se o důležitý algebraický koncept a lze se s ním setkat například při konstrukci rozkladových těles nebo v Hilbertově větě o bázi.
Mějme komutativní okruh s množinou M s jednotkovým prvkem. Pak ∑ akxᵏ pro k od 0 do ∞ je polynom neurčité1) x nad M (ak ∈ M). Prvky M jsou právě tyto polynomy. 
"neurčitá" == "proměnná" … zkarátka stupidní názvosloví
Operace + * jsou definovány
značí se R[x]
Polynomy se násobí a sčítají podle pravidel původního okruhu.
Za parametr x polynomu lze dosadit a získat tak hodnotu polynomu v daném x. 
Násobení a sčítání je definováno po složkách - (např násobení dvou polynomů je suma součinů odpovídajích nenulových prvků  a1 * b1 + a2 * b2....)
Prostě 4a³ + 8,2a² − 5 je polynom neurčité 𝐚 nad M.
Polynom s největším nenulovým koeficientem rovným „1“ (kdyby u příkladu výše nebyla ta 4 na začátku) je normovaný polynom.
Stupeň polynomu je mocnina u nejvyššího „nenulového“ koeficientu (v příkladu výše tedy 3). Pokud je polynom jen číslo, tak je stupeň 0 a pokud jen polynom jen „0“, tak je jeho stupeň −1.
Když položíme polynom rovný „0“ a vyřešíme, tak dostaneme jeho kořeny.
Tedy: a je kořen polynomu p(x) práve tehdy, když p(a) = 0
Dělitelnost
Prvek 𝑎 je dělitelný dělitelem 𝑏 (značíme 𝑏|𝑎) právě tehdy pokud platí: ∃𝒄∈𝑰:𝒂=𝒃𝒄
Operace s dělením
Pokud A není prázdná a operace ∘ je asociativní tak plati:
∘ je operace s dělěním
existuje neutrální prvek a každý prvek 𝑥∈𝐴 je invertibilní, tzn. 
V Cayleyově tabulce operace se levá/pravá OSD pozná tak, že každý řádek/sloupec obsahuje každý prvek právě jednou.
Rovnice 𝑎∘𝑥=𝑏 a 𝑦∘𝑎=𝑏 mají v operaci s krácením maximálně jedno řešení. Pokud je operace i asociativní tak mají právě jedno řešení.
Pro konečnou množinu A platí: ∘ je operace s dělením ⇔ ∘ je operace s krácením
V tabulce operace se pozná tak, že každý řádek/sloupec obsahuje každý prvek max jednou.
Pravidla dělitelnosti
Prvek a je dělitelný b (značíme b|a) pokud existuje nějaké c kdy a = b ⊗ c.
a|„0“ („0“ lze dělit čímkoliv)
„1“|a (cokoli je dělitelné „1“)
a|a (cokoli je dělitelné samo sebou)
a|b ∧ b|c ⇒ a|c (dělitel mého dělitele je i můj dělitel)
a|b ⇒ a|bc (můj dělitel je i dělitel mého násobku)
a|b ∧ a|c ⇒ a|(b + c) (součet je dělitelný společným dělitelem sčítanců)
c ≠ „0“, a|b ⇒ ac|bc (vynásobením dělence i dělitele stejným nenulovým číslem se dělitelnost nemění)
a|b ∧ c|d ⇒ ac|bd (vynásobením dělenců mezi sebou a dělitelů mezi sebou se dělitelnost nemění)
a|b ⇒ aⁿ|bⁿ (umocnění dělence i dělitele stejným číslem dělitelnost nemění)
Dělitel „1“ se označuje jako jednotka. Množinu všech jednotek oboru integrity I značíme E(I).
Asociované prvky se liší jen vynásobením některou jednotkou. Asociované prvky jsou navzájem svými děliteli.
Triviální dělitelé prvku a jsou všechny jednotky a všechny prvky asociované s prvkem a.
Vlastní dělitelé jsou všichni netriviální dělitelé.
Ireducibilní prvek má pouze triviální dělitele („1“ a sám sebe, např. prvočísla)
Ireducibilní = "nerozložitelný". Platí to i pro polynomy, které nelze rozložit (ireducibilní polynomy).
Pokud a není nulou ani jendnotkou a pokud plati pro každé b,c z komutativního okruhu R: a|(b ⊗ c) ⇒ a|b ∨ a|c pak je a prvočinitel.
Prvočinitel - po lopatě
Název prvočinitel vznikl z názvů prvočíslo a činitel. Prvočinitel je prvočíslo, které dělí nějaké číslo. Každé složené číslo jde napsat jako součin prvočinitelů.
Gaussovy okruhy
Příklady Gaussových okruhů: celá čísla, reálná čísla, racionální čísla, komplexní čísla, všechna tělesa, …
Gaussův obor integrity neboli obor integrity s jednoznačným rozkladem je v algebře, volně řečeno, takový okruh, ve kterém platí analogie Základní věty aritmetiky, totiž že každý jeho prvek (až na určité výjimky) je možno v jistém smyslu jednoznačně vyjádřit jako součin prvočinitelů.
Obor integrity se nazývá Gaussův obor integrity (faktoriální obor integrity nebo obor integrity s jednoznačným rozkladem), právě když pro každé existuje rozklad v součin ireducibilních prvků a když libovolné dva rozklady prvku jsou spolu asociovány. [Blažek, 1985] 
V Gaussově okruhu platí:
každý ireducibilní prvek je prvočinitel
každý neprvočinitel je tvořen součinem určitých počtů (mocnin) různých (neasociovaných) prvočinitelů a jednotky
a|b ⇔ a se skládá ze stejného nebo menšího počtu výskytů jednotlivých prvočinitelů
Příkladem oboru jsou například celá čísla
Největší společný dělitel (NSD)
vezmu všechna prvočísla, která se vyskytují v obou prvočíselných rozkladech (pokud žádné takové není, je největší společný dělitel 1) a u každého použiji minimální mocninu, ve které se vyskytuje. Získávám tím prvočíselný rozklad největšího společného dělitele.
Například největšího společného dělitele čísel 136 a 204 lze nalézt tak, že zjistíme, že 136 = 2³×17 a 204 =2²×3×17. V rozkladech se vyskytují prvočísla 2, 3 a 17 s exponenty 3, 0, 1 u menšího čísla a 2, 1, 1 u většího čísla. Výsledné NSD pak je součin prvočísel vyskytujících se v obou rozkladech umocněných na příslušné nejmenší exponenty, tedy 2²×17 = 68.
Nejmenší společný násobek(NSN)
vezmu všechna prvočísla, která se vyskytují v rozkladu prvního nebo druhého čísla a u každého z nich použiji maximální mocninu, ve které se vyskytuje. Získávám tím prvočíselný rozklad nejmenšího společného násobku
Zadaná čísla: 15, 20, 90
Normované prvky
množinu I rozdelíme na triedy podľa relácie asociácie (~) a z každej triedy vybereme jedného zástupcu
príklad: celé čísla: triedy sú {0}, {+-1}, ... {+-n} a ako normované prvky vyberieme len kladné (použijeme absolútnu hodnotu)
normované prvočinitele: zástupcovia tried, ktoré obsahujú prvočinitele
Svaz dělitelů
je svaz nad množinou I/~ (faktorová množina asociovaných prvků) kde je relace uspořádání definována jako 𝑎~≤𝑏~⇔𝑎|𝑏
Eukleidovy okruhy
Okruhy na kterých je definováno dělení se zbytkem. Každý Eukleidův okruh je Gaussův okruh. 
Příkladem EO může být například okruh na celých číslech, kde operace f je absolutní hodnota pro  nenulová čísla.
Dělení se zbytkem:
∀ a ∈ I \ „0“ (dělitel)
∀ b ∈ I (dělenec)
∃ q ∈ I (výsledek)
∃ r ∈ I (zbytek)
Eukleidův algoritmus pro NSD
function nsd(a, b) // a > b !
    if b = 0
       return a
    else
       return nsd(b, a mod b)
Notes
2. Otazka (předmět) (okruh): 5. Obory integrity a delitelnost
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Tuto otazku som si nechal ako druhu, pretoze som vedel, ze k nej moc neviem. Nastastie som si predtym pozrel co je to obor integrity a aspon to vedel s istotou zadefinovat. Stacilo neformalne povedat, co to je. Potom hned padla otazka co je to delitelnost. To som si tiez presne nepamatal, ale stacilo, ked som na tabulu napisal ax=b (Rogalewicz povedal, ze to takto staci, ze predpokladajme, ze je to komutativne) a hned sa spytal kedy je b delitelne a-ckom. To som mu povedal a stacilo mu to. Potom sa pytal na Gausov okruh. Ten som si pomylil s Euklidovym, tak ma opravil. Dalej chcel vediet co je to okruh polynomov nad x a ze sa tam zachovavaju vztahy (ak je to nad oborom itegrity, tak aj to je obor integrity alebo nieco take. Tu uz som vobec nevedel a len prikivoval. Potom povedal, ze mu to staci. Rogalewicz celu dobu pomahal a napovedal. Bol som rad, ze ma tento okruh skusa zrovna on. Mam to za D.
From <[link]> 
1. Otazka (předmět) (okruh): MAT 5 - Obory integrity a dělitelnost
Kdo me primarne zkousel: Hrdina
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Nejprve jsem začal tím co to je obor integrity (algebra, dvě bin operace), tak mě zastavil a řekl že to chce zadefinovat pomocí okruhu, to jsem řekl (už teď to bylo určitě na E 
 ). pak se zeptal na operace s dělením a s krácením, chtěl vysvětlit co platí. To už bylo horší, nějak ne a ne naskočit, plantal jsem tam nějaké blbosti, až mi nakonec nadiktoval:
a*x1 = a*x2 => 
a zbytek už jsem dopsal 
x1 = x2
pak se ptal jak je to s těma operacema u těles a která je "silnější", chtěl slyšet něco jako 
když je to operace s dělením, pak je to operace s krácením (nebo naopak), no řekl jsem to přesně naopak, řekl že teda blbě a že mu to stačí. V tu chvíli sem myslel že amen, nakonec dali D.
From <[link]> 
1. Otazka (predmet) (okruh): MAT Obor integrity a dělitelnost
Kdo me primarne zkousel: Vojnar Tomáš, prof. Ing., Ph.D. UITS FIT VUT, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Hned ze startu mi oznámil, že ho bude zajímat právě ten obor integrity. Na začátek jsem mu popsal klasciké vlastnosti (asoc., komut., 0!=1). Pak se zeptal na operaci krácení, kterou jsem při učení tak trochu přeskočil. Nakonec mi to prakticky nadiktoval a pak jsem to měl dokázat. Občas jsem asi vypadal, že nerozumím česky. ale nakonec jsme se nějak dobrali k cíli. Češka měl ještě kontrolní otázku: jaktože můžu mluvit o dělení, když není tahle operace definována (stačilo říct, že máme inverzní prvky). 
From <[link]> 