Obory integrity a dělitelnost

Obor integrity: (M, ⊕, ⊗)

(M, ⊕) je komutativní grupa

(M, ⊗) je monoid

a ⊗ b ≠ „0“

Okruhy polynomů

Polynomial ring

Mějme komutativní okruh s množinou M s „1“. Pak ∑ aₖxᵏ pro k od 0 do ∞ je polynom neurčité1) Tak se říká té proměnné co má mocniny. x nad M (aₖ ∈ M).

Prostě 4a³ + 8,2a² − 5 je polynom neurčité a nad ℝ.

Polynom ve tvaru ax + b je to lineární polynom.

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.

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 ma pouze triviální dělitele („1“ a sám sebe, např. prvočísla)

Pokud plati: a|(b ⊗ c) ⇒ a|b ∨ a|c pak je a prvočinitel.

Gaussovy okruhy

Gauss's lemma (polynomial)

Základní vlastností Gaussových okruhů je jednoznačnost rozkladu na prvočinitele, tj. každý prvek, který není „0“ nebo „1“, je prvočinitelem, nebo ho lze jednoznačně rozložit na součin prvočinitelů.

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ů.

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.

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.

Normované prvky: když mám množinu rozdělěnou na třídy, použiju jeden jako zástupce celé třídy

Eukleidovy okruhy

Euclidean domain

Okruhy na kterých je definováno dělení se zbytkem. Každý Eukleidův okruh je Gaussův okruh.

Dělení se zbytkem:

∀ a ∈ I \ „0“ (dělitel)

∀ b ∈ I (dělenec)

∃ q ∈ I (výsledek)

∃ r ∈ I (zbytek)

b = aq + r

r < a

Euclidean algorithm