Podział euklidesowy - Euclidean division

17 podzielono na 3 grupy po 5, przy czym 2 pozostały. Tutaj dzielna wynosi 17, dzielnik 5, iloraz 3, a reszta to 2 (co jest ściśle mniejsze niż dzielnik 5) lub bardziej symbolicznie, 17 = (5 × 3) + 2.

W arytmetyczna , euklidesowa podziału - lub podziału z pozostający - jest to proces dzielenia jednego całkowitą (dywidenda) przez inny (dzielnik) w sposób, który daje iloraz i pozostałą mniejszą niż dzielnik. Podstawową właściwością jest to, że iloraz i reszta istnieją i są unikalne pod pewnymi warunkami. Ze względu na tę wyjątkowość, podział euklidesowy jest często rozważany bez odwoływania się do żadnej metody obliczeniowej i bez jawnego obliczania ilorazu i reszty. Metody obliczeń nazywane są algorytmami dzielenia liczb całkowitych , z których najbardziej znanym jest dzielenie długie .

Dzielenie euklidesowe i algorytmy do jego obliczania są podstawą wielu pytań dotyczących liczb całkowitych, takich jak algorytm euklidesowy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych oraz arytmetyka modularna , dla której brane są pod uwagę tylko reszty. Operacja polegająca na obliczeniu tylko reszty nazywana jest operacją modulo i jest często stosowana zarówno w matematyce, jak i informatyce.

Ciasto ma 9 kromek, więc każda z 4 osób otrzymuje 2 kromki, a 1 zostaje.

Twierdzenie o dzieleniu

Podział euklidesowy opiera się na następującym wyniku, który jest czasami nazywany lematem podziału Euklidesa .

Biorąc pod uwagę dwie liczby całkowite a i b , przy b ≠ 0 , istnieją unikalne liczby całkowite q i r takie, że

a = bq + r

i

0 ≤ r < | b | ,

gdzie | b | oznacza wartość bezwzględną w b .

W powyższym twierdzeniu każda z czterech liczb całkowitych ma swoją własną nazwę: a to dzielna , b to dzielnik , q to iloraz , a r to reszta .

Obliczenie ilorazu i reszty z dzielnej i dzielnika nazywa się dzieleniem lub — w przypadku niejednoznaczności — dzieleniem euklidesowym . Twierdzenie jest często nazywane algorytmem dzielenia (chociaż jest to twierdzenie, a nie algorytm), ponieważ jego dowód, jak podano poniżej, nadaje się do prostego algorytmu dzielenia do obliczania q i r (więcej informacji w rozdziale Dowód ).

Podział nie jest zdefiniowany w przypadku, gdy b = 0 ; zobacz dzielenie przez zero .

Dla reszty i operacji modulo istnieją konwencje inne niż 0 ≤ r < | b | , patrz § Inne przedziały dla reszty .

Historia

Chociaż „podział euklidesowy” nosi imię Euklidesa , wydaje się, że nie znał on twierdzenia o istnieniu i jednoznaczności, a jedyną znaną mu metodą obliczeniową było dzielenie przez wielokrotne odejmowanie .

Przed odkryciem hindusko-arabskiego systemu liczbowego , wprowadzonego w Europie w XIII wieku przez Fibonacciego , podział był niezwykle trudny i potrafili to zrobić tylko najlepsi matematycy. Obecnie większość algorytmów dzielenia , w tym dzielenie długie , opiera się na tej notacji lub jej odmianach, takich jak liczby binarne . Godnym uwagi wyjątkiem jest podział Newtona-Raphsona , który jest niezależny od jakiegokolwiek systemu liczbowego .

Termin „podział euklidesowy” został wprowadzony w XX wieku jako skrót oznaczający „podział pierścieni euklidesowych ”. Został on szybko przyjęty przez matematyków dla odróżnienia tego podziału od innych rodzajów podziału liczb.

Intuicyjny przykład

Załóżmy, że ciasto ma 9 kawałków i mają być podzielone równo między 4 osoby. Używając dzielenia euklidesowego, 9 podzielone przez 4 daje 2 z resztą 1. Innymi słowy, każda osoba otrzymuje 2 kromki ciasta i zostaje 1 kromka.

Można to potwierdzić za pomocą mnożenia — odwrotność dzielenia: jeśli każda z 4 osób otrzymała 2 wycinki, to w sumie rozdawane były 4 × 2 = 8 wycinków. Dodanie 1 pozostałego plasterka daje 9 plasterków. Podsumowując: 9 = 4 × 2 + 1.

Ogólnie rzecz biorąc, jeśli oznaczona jest liczba plasterków i liczba osób , to można podzielić ciasto równomiernie między osoby tak, aby każda osoba otrzymała plasterki (iloraz), przy czym pewna liczba plasterków jest pozostała (reszta ). W takim przypadku równanie jest aktualne. ${\displaystyle a}$${\displaystyle b}$${\displaystyle q}$${\displaystyle r<b}$${\displaystyle a=bq+r}$

Jako alternatywny przykład, jeśli 9 kawałków zostanie podzielonych między 3 osoby zamiast 4, to każda otrzyma 3 i nie pozostanie żaden kawałek, co oznacza, że ​​reszta będzie równa zero, co prowadzi do wniosku, że 3 równo dzieli 9, lub że 3 dzieli 9.

Podział euklidesowy można również rozszerzyć na ujemną dywidendę (lub ujemny dzielnik) przy użyciu tej samej formuły; na przykład -9 = 4 × (-3) + 3, co oznacza, że ​​-9 podzielone przez 4 to -3 z resztą 3.

Przykłady

• Jeśli a = 7 i b = 3, to q = 2 i r = 1, ponieważ 7 = 3 × 2 + 1.
• Jeśli a = 7 i b = -3, to q = -2 i r = 1, ponieważ 7 = -3 × (-2) + 1.
• Jeśli a = -7 i b = 3, to q = -3 i r = 2, ponieważ -7 = 3 × (-3) + 2.
• Jeśli a = -7 i b = -3, to q = 3 i r = 2, ponieważ -7 = -3 × 3 + 2.

Dowód

Poniższy dowód twierdzenia o dzieleniu opiera się na fakcie, że malejący ciąg nieujemnych liczb całkowitych ostatecznie się zatrzymuje. Dzieli się na dwie części: jedną na istnienie, a drugą na wyjątkowość i . Inne dowody użyć zasada dobrego uporządkowania (czyli twierdzenie, że każdy niepusty zbiór z nieujemnych liczb całkowitych ma najmniejszy element), aby rozumowanie prostsze, ale mają tę wadę, że nie zapewniając bezpośrednio algorytm rozwiązywania podział ( patrz § Skuteczność, aby uzyskać więcej). ${\displaystyle q}$${\ Displaystyle r}$

Istnienie

Rozważmy najpierw przypadek b < 0 . Zakładając b' = – b oraz q' = – q , równanie a = bq + r można przepisać jako a = b'q' + r i nierówność 0 ≤ r < | b | można przepisać jako 0 ≤ r < |b ′ | . To redukuje istnienie przypadku b < 0 do tego przypadku b > 0 .

Podobnie, jeśli a < 0 i b > 0 , ustawiając a' = – a , q' = – q – 1 , oraz r' = b – r , równanie a = bq + r można przepisać jako a' = bq' + r ′ , a nierówność 0 ≤ r < | b | można przepisać jako 0 ≤ r' < | b | . Tak więc dowód istnienia sprowadza się do przypadku a ≥ 0 i b > 0 — co zostanie uwzględnione w dalszej części dowodu.

Niech q ₁ = 0 i r ₁ = a , to są to liczby nieujemne takie, że a = bq ₁ + r ₁ . Jeśli r ₁ < b to dzielenie jest kompletne, więc załóżmy, że r ₁ ≥ b . Następnie definiujemy q ₂ = q ₁ + 1 i r ₂ = r ₁ – b , mamy a = bq ₂ + r ₂ gdzie 0 ≤ r ₂ < r ₁ . Ponieważ istnieje tylko r ₁ nieujemnych liczb całkowitych mniejszych niż r ₁ , wystarczy powtórzyć ten proces co najwyżej r ₁ razy, aby osiągnąć końcowy iloraz i resztę. Oznacza to, że istnieje liczba naturalna k ≤ r ₁ taka, że a = bq _k + r _k i 0 ≤ r _k < | b | .

To dowodzi istnienia, a także daje prosty algorytm dzielenia do obliczania ilorazu i reszty. Algorytm ten nie jest jednak wydajny, ponieważ jego liczba kroków jest rzędu a / b .

Wyjątkowość

Para liczb całkowitych r i q taka, że a = bq + r jest unikalna, w tym sensie, że nie może istnieć inna para liczb całkowitych spełniająca ten sam warunek w twierdzeniu o dzieleniu euklidesowym. Innymi słowy, jeśli mamy inny podział a przez b , powiedzmy a = bq' + r' z 0 ≤ r' < | b | , to musimy to mieć

q' = q i r' = r .

Aby udowodnić to stwierdzenie, zaczynamy od założeń, które:

0 ≤ r < | b |

0 ≤ r' < | b |

a = bq + r

a = bq' + r'

Odjęcie dwóch równań daje

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

Zatem b jest dzielnikiem r ′ – r . Tak jak

| r ′ – r | < | b |

przez powyższe nierówności otrzymujemy

r ′ – r = 0 ,

i

b ( q – q ′ ) = 0 .

Ponieważ b ≠ 0 , otrzymujemy, że r = r ′ i q = q ′ , co dowodzi jednoznaczności twierdzenia o dzieleniu euklidesowym.

Skuteczność

Ogólnie rzecz biorąc, dowód istnienia nie dostarcza algorytmu obliczania istniejącego ilorazu i reszty, ale powyższy dowód od razu dostarcza algorytmu (patrz Algorytm dzielenia#Dzielenie przez wielokrotne odejmowanie ), mimo że nie jest to bardzo wydajny, ponieważ wymaga tylu kroków, ile wynosi wielkość ilorazu. Wiąże się to z faktem, że używa tylko dodawania, odejmowania i porównywania liczb całkowitych, bez mnożenia, ani żadnej szczególnej reprezentacji liczb całkowitych, takiej jak notacja dziesiętna.

Jeśli chodzi o notację dziesiętną, dzielenie długie zapewnia znacznie bardziej wydajny algorytm rozwiązywania dzieleń euklidesowych. Jego uogólnienie na zapis binarny i szesnastkowy zapewnia dalszą elastyczność i możliwość implementacji komputerowej. Jednak w przypadku dużych danych wejściowych preferowane są zwykle algorytmy redukujące dzielenie do mnożenia, takie jak Newton-Raphson , ponieważ potrzebują tylko czasu proporcjonalnego do czasu mnożenia potrzebnego do zweryfikowania wyniku — niezależnie od algorytmu mnożenia, który jest używany (więcej informacji w rozdziale Algorytm dzielenia#Metody szybkiego dzielenia ).

Warianty

Podział Euklidesa dopuszcza szereg wariantów, z których niektóre wymieniono poniżej.

Inne interwały dla pozostałych

W dzieleniu euklidesowym z dzielnikiem d reszta powinna należeć do przedziału [0, d ) długości | d | . Można zastosować dowolny inny przedział o tej samej długości. Dokładniej, podane liczby całkowite , , ze istnieją unikalnych liczb całkowitych i z takim, że . ${\ Displaystyle m}$${\displaystyle a}$${\displaystyle d}$${\ Displaystyle m> 0}$${\displaystyle q}$${\ Displaystyle r}$${\displaystyle d\leq r<m+d}$${\displaystyle a=mq+r}$

W szczególności, jeśli wtedy . Ten podział nazywa się dzieleniem wyśrodkowanym , a jego reszta nazywana jest resztą wyśrodkowaną lub najmniejszą resztą bezwzględną .${\displaystyle d=-\lewo\lpodłoga {\frac {m}{2}}\prawo\rpodłoga}$${\displaystyle -\lewo\lpodłoga {\frac {m}{2}}\prawo\rpodłoga \leq r<m-\lewo\lpodłoga {\frac {m}{2}}\prawo\rpodłoga}$${\ Displaystyle r}$

Jest to używane do przybliżania liczb rzeczywistych : dzielenie euklidesowe definiuje obcięcie , a dzielenie wyśrodkowane definiuje zaokrąglenie .

Oddział Montgomery

Biorąc pod uwagę liczby całkowite , a ze i puszczeniu być modułowy Liczba odwrotna od (czyli z bycia wielokrotność ), to istnieje unikalnych liczb całkowitych i z takim, że . Ten wynik uogólnia nieparzysty podział Hensela (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}$

Wartość jest N- resztą zdefiniowaną w redukcji Montgomery'ego . ${\ Displaystyle r}$

W domenach euklidesowych

Domeny euklidesowe (znane również jako pierścienie euklidesowe ) są zdefiniowane jako domeny integralne, które wspierają następujące uogólnienie podziału euklidesowego:

Biorąc pod uwagę element a i niezerowy element b w domenie euklidesowej R wyposażonej w funkcję euklidesową d (znaną również jako wartość euklidesowa lub funkcja stopnia ), istnieją q i r w R takie, że a = bq + r i albo r = 0 lub d ( r ) < d ( b ) .

Unikalność q i r nie jest wymagana. Występuje tylko w wyjątkowych przypadkach, typowo dla wielomianów jednowymiarowych oraz dla liczb całkowitych, jeśli zostanie dodany dalszy warunek r ≥ 0 .

Przykłady domen euklidesowych obejmują pola , pierścienie wielomianowe w jednej zmiennej nad polem oraz liczby całkowite Gaussa . Podział euklidesowy wielomianów był przedmiotem specyficznych prac.

Zobacz też

• Lemat Euklidesa
• Algorytm Euklidesa

Uwagi

Bibliografia

• Fraleigh, John B. (1993), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), Pierwszy kurs algebry abstrakcyjnej z aplikacjami (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8