Euklidovská divize - Euclidean division

17 je rozdělen do 3 skupin po 5, přičemž 2 zbyly. Zde je dividenda 17, dělitel 5, kvocient 3 a zbytek 2 (což je striktně menší než dělitel 5), nebo více symbolicky 17 = (5 × 3) + 2.

V aritmetice je euklidovské dělení - nebo dělení se zbytkem - proces dělení jednoho celého čísla (dividendy) jiným (dělitelem) způsobem, který vytváří kvocient a zbytek menší než dělitel. Základní vlastností je, že kvocient a zbytek existují a jsou za určitých podmínek jedinečné. Kvůli této jedinečnosti je euklidovské dělení často považováno bez odkazu na jakoukoli metodu výpočtu a bez výslovného výpočtu podílu a zbytku. Metody výpočtu se nazývají algoritmy celočíselného dělení , z nichž nejznámější je dlouhé dělení .

Euklidovské dělení a algoritmy pro jeho výpočet jsou zásadní pro mnoho otázek týkajících se celých čísel, jako je euklidovský algoritmus pro nalezení největšího společného dělitele dvou celých čísel a modulární aritmetika , u nichž se uvažuje pouze o zbytcích. Operace spočívající ve výpočtu pouze zbývající části se nazývá operace modulo a často se používá jak v matematice, tak v informatice.

Koláč má 9 plátků, takže každý ze 4 lidí obdrží 2 plátky a 1 zůstane.

Věta o dělení

Euklidovské dělení je založeno na následujícím výsledku, který se někdy nazývá Euklidovo dělící lemma .

Vzhledem k tomu, dvě celá čísla a a b , s b ≠ 0 , existují jedinečná celá čísla q a r taková

a = bq + r

a

0 ≤ r <| b | ,

kde | b | označuje absolutní hodnotu o b .

Ve výše uvedené větě má každé ze čtyř celých čísel své vlastní jméno: a se nazývá dividenda , b se nazývá dělitel , q se nazývá kvocient a r se nazývá zbytek .

Výpočet kvocientu a zbytku z dividendy a dělitele se nazývá dělení nebo - v případě nejednoznačnosti - euklidovské dělení . Věta je často označována jako algoritmus dělení (i když se jedná o větu a nikoli algoritmus), protože její důkaz, jak je uveden níže, je vhodný pro jednoduchý algoritmus dělení pro výpočet q a r (více v části Důkaz ).

Dělení není definováno v případě, že b = 0 ; viz dělení nulou .

Pro zbytek a provoz modulo existují jiné konvence než 0 ≤ r <| b | , viz § Ostatní intervaly pro zbytek .

Dějiny

Ačkoli je „euklidovské dělení“ pojmenováno po Euklidovi , zdá se, že neznal teorém o existenci a jedinečnosti a že jedinou výpočetní metodou, kterou znal, bylo dělení opakovaným odečtením .

Před objevením hindusko-arabského číselného systému , který v Evropě zavedl během 13. století Fibonacci , bylo dělení extrémně obtížné a dokázali to jen ti nejlepší matematici. V současné době je většina algoritmů dělení , včetně dlouhého dělení , založena na tomto zápisu nebo jeho variantách, jako jsou binární číslice . Pozoruhodnou výjimkou je divize Newton – Raphson , která je nezávislá na jakékoli číselné soustavě .

Termín „euklidovské rozdělení“ byl zaveden v průběhu 20. století jako zkratka pro „rozdělení euklidovských prstenů “. Matematici ho rychle přijali pro rozlišení tohoto dělení od ostatních druhů dělení čísel.

Intuitivní příklad

Předpokládejme, že koláč má 9 plátků a ty se mají rovnoměrně rozdělit mezi 4 lidi. Při použití euklidovského dělení je 9 děleno 4 2 se zbytkem 1. Jinými slovy, každá osoba obdrží 2 plátky koláče a zbývá 1 plátek.

To lze potvrdit pomocí násobení - inverzní k dělení: pokud každý ze 4 lidí obdržel 2 plátky, bylo rozdáno celkem 4 × 2 = 8 plátků. Po přidání zbývajícího 1 řezu je výsledkem 9 řezů. Souhrnně: 9 = 4 × 2 + 1.

Obecně platí, že pokud je označen počet řezů a je označen počet lidí , lze rozdělit koláč rovnoměrně mezi lidi tak, aby každý člověk dostal řezy (kvocient), přičemž určitý počet řezů je zbylých (zbytek ). V takovém případě platí rovnice . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle q}$${\ displaystyle r <b}$${\ displaystyle a = bq + r}$

Jako alternativní příklad, pokud by 9 plátků bylo rozděleno mezi 3 lidi místo 4, pak by každý obdržel 3 a nezůstal by žádný plátek, což znamená, že zbytek by byl nulový, což by vedlo k závěru, že 3 rovnoměrně rozdělí 9, nebo že 3 rozděluje 9.

Euklidovské dělení lze také rozšířit na zápornou dividendu (nebo záporný dělitel) pomocí stejného vzorce; například −9 = 4 × (−3) + 3, což znamená, že −9 děleno 4 je −3 se zbytkem 3.

Příklady

• Pokud a = 7 a b = 3, pak q = 2 a r = 1, protože 7 = 3 × 2 + 1.
• Pokud a = 7 a b = -3, pak q = −2 ar = 1, protože 7 = −3 × (−2) + 1.
• Pokud a = −7 a b = 3, pak q = −3 a r = 2, protože −7 = 3 × (−3) + 2.
• Pokud a = −7 a b = −3, pak q = 3 a r = 2, protože −7 = −3 × 3 + 2.

Důkaz

Následující důkaz věty o rozdělení se spoléhá na skutečnost, že klesající posloupnost nezáporných celých čísel se nakonec zastaví. Je rozdělena na dvě části: jednu pro existenci a druhou pro jedinečnost a . Jiné důkazy použít princip dobrého uspořádání (tedy tvrzení, že každý non-prázdná množina of non-záporná celá čísla má nejmenší prvek), aby se úvaha jednodušší, ale mají tu nevýhodu, že nezajišťuje přímo algoritmus pro řešení divize ( viz § Účinnost pro více). ${\ displaystyle q}$${\ displaystyle r}$

Existence

Zvažte nejprve případ b <0 . Nastavením b ' = - b a q' = - q lze rovnici a = bq + r přepsat jako a = b'q ' + r a nerovnost 0 ≤ r < | b | lze přepsat jako 0 ≤ r < | b ′ | . To snižuje existenci pro případ b <0 na případ b > 0 .

Podobně, pokud a <0 a b > 0 , nastavení a ' = - a , q' = - q - 1 , a r ' = b - r , lze rovnici a = bq + r přepsat jako ' = bq ' + r ′ a nerovnost 0 ≤ r <| b | lze přepsat jako 0 ≤ r ' <| b | . Důkaz o existenci se tedy redukuje na případ a ≥ 0 a b > 0 - o kterém se bude uvažovat ve zbývající části důkazu.

Nechť q ₁ = 0 a r ₁ = a , pak se jedná o nezáporná čísla, takže a = bq ₁ + r ₁ . Pokud r ₁ < b, pak je rozdělení úplné, předpokládejme tedy, že r ₁ ≥ b . Poté definujeme q ₂ = q ₁ + 1 a r ₂ = r ₁ - b , jeden má a = bq ₂ + r ₂ s 0 ≤ r ₂ < r ₁ . Jelikož existují pouze r ₁ nezáporná celá čísla menší než r ₁ , je třeba tento proces opakovat maximálně r ₁ krát, aby se dosáhlo konečného kvocientu a zbytku. To znamená, že existuje přirozené číslo k ≤ r ₁ takové, že a = bq _k + r _k a 0 ≤ r _k <| b | .

To dokazuje existenci a také poskytuje jednoduchý algoritmus dělení pro výpočet kvocientu a zbytku. Tento algoritmus však není efektivní, protože jeho počet kroků je řádově a / b .

Jedinečnost

Dvojice celých čísel r a q tak, že a = bq + r je jedinečné, v tom smyslu, že nemůže existovat další dvojice celých čísel, která splňují stejnou podmínku v euklidovské teorém dělení. Jinými slovy, pokud máme další dělení a na b , řekněme a = bq ' + r' s 0 ≤ r ' <| b | , pak to musíme mít

q ' = q a r' = r .

Abychom toto tvrzení dokázali, nejprve začneme s předpoklady, že

0 ≤ r <| b |

0 ≤ r ' <| b |

a = bq + r

a = bq ' + r'

Odečtením dvou rovnic se získá výtěžek

b ( q - q ′ ) = r ′ - r .

Takže b je dělitelem r ′ - r . Tak jako

| r ′ - r | <| b |

podle výše uvedených nerovností jeden dostane

r ′ - r = 0 ,

a

b ( q - q ' ) = 0 .

Protože b ≠ 0 , dostaneme r = r ′ a q = q ′ , což dokazuje jedinečnost části euklidovské věty o dělení.

Účinnost

Obecně důkaz existence neposkytuje algoritmus pro výpočet existujícího kvocientu a zbytku, ale výše uvedený důkaz poskytuje algoritmus okamžitě (viz algoritmus dělení # dělení opakovaným odečtením ), i když to není příliš efektivní, protože vyžaduje tolik kroků, kolik je velikost kvocientu. To souvisí se skutečností, že používá pouze sčítání, odčítání a porovnávání celých čísel bez zapojení násobení, ani žádnou konkrétní reprezentaci celých čísel, například desítkovou notaci.

Pokud jde o desetinnou notaci, dlouhé dělení poskytuje mnohem efektivnější algoritmus pro řešení euklidovských dělení. Jeho zobecnění na binární a hexadecimální zápis poskytuje další flexibilitu a možnost implementace do počítače. U velkých vstupů jsou však obvykle upřednostňovány algoritmy, které redukují dělení na násobení, jako je Newton – Raphson , protože potřebují pouze čas, který je úměrný době násobení potřebné k ověření výsledku - nezávisle na algoritmu násobení, který se používá (více viz Algoritmus dělení # Metody rychlého dělení ).

Varianty

Euklidovská divize připouští řadu variant, z nichž některé jsou uvedeny níže.

Ostatní intervaly pro zbytek

V euklidovském dělení s dělitelem d se předpokládá, že zbytek patří do intervalu [0, d ) délky | d | . Lze použít jakýkoli jiný interval stejné délky. Přesněji řečeno, vzhledem celá čísla , , s , existuje jedinečná celá čísla a s taková, že . ${\ displaystyle m}$${\ displaystyle a}$${\ displaystyle d}$${\ displaystyle m> 0}$${\ displaystyle q}$${\ displaystyle r}$${\ Displaystyle d \ leq r <m + d}$${\ displaystyle a = mq + r}$

Zejména pokud ano . Toto dělení se nazývá středové dělení a jeho zbytek se nazývá středový zbytek nebo nejméně absolutní zbytek .${\ displaystyle d = - \ levá \ lfloor {\ frac {m} {2}} \ pravá \ rfloor}$${\ Displaystyle - \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor \ leq r <m- \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor}$${\ displaystyle r}$

Slouží k aproximaci reálných čísel : Euklidovské dělení definuje zkrácení a středové dělení definuje zaokrouhlování .

Montgomeryova divize

Vzhledem k tomu, celá čísla , a s a pustíte být modulární multiplikativní inverzní of (tedy s být násobkem ), potom existují jedinečné celá čísla a s taková, že . Tento výsledek zobecňuje Henselovo liché dělení (1900). ${\ displaystyle a}$${\ displaystyle m}$${\ displaystyle R,}$${\ displaystyle m> 0}$${\ displaystyle \ gcd (R, m) = 1,}$${\ displaystyle R ^ {- 1}}$${\ displaystyle R}$${\ displaystyle 0 <R ^ {- 1} <m}$${\ displaystyle R ^ {- 1} R-1}$${\ displaystyle m}$${\ displaystyle q}$${\ displaystyle r}$${\ displaystyle 0 \ leq r <m}$${\ displaystyle a = mq + R ^ {- 1} \ cdot r}$

Hodnota je N- reziduum definované v Montgomeryho redukci . ${\ displaystyle r}$

V euklidovských doménách

Euklidovské domény (také známé jako euklidovské kruhy ) jsou definovány jako integrální domény, které podporují následující zobecnění euklidovského dělení:

Vzhledem k prvku a a nenulovému prvku b v euklidovské doméně R vybavené euklidovskou funkcí d (také známou jako euklidovská funkce pro hodnocení nebo stupeň ) existují v R q a r tak, že a = bq + r a buď r = 0 nebo d ( r ) < d ( b ) .

Jedinečnost q a r není vyžadována. Vyskytuje se pouze ve výjimečných případech, obvykle pro jednorozměrné polynomy a pro celá čísla, pokud je přidána další podmínka r ≥ 0 .

Mezi příklady euklidovských domén patří pole , polynomiální prstence v jedné proměnné nad polem a Gaussova celá čísla . Euklidovské dělení polynomů bylo předmětem konkrétního vývoje.

Viz také

• Euklidovo lemma
• Euklidovský algoritmus

Poznámky

Reference

• Fraleigh, John B. (1993), První kurz v abstraktní algebře (5. vydání), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), První kurz abstraktní algebry s aplikacemi (3. vyd.), Prentice-Hall, ISBN 978-0-13-186267-8