Podstawowe twierdzenie arytmetyki - Fundamental theorem of arithmetic

Unikalne twierdzenie o faktoryzacji zostało udowodnione przez Gaussa w jego książce z 1801 r. Disquisitiones Arithmeticae . W tej książce Gauss wykorzystał podstawowe twierdzenie do udowodnienia prawa kwadratowej wzajemności .

W teorii liczb , na podstawowej twierdzenia arytmetyczne , zwany także unikalny twierdzenie faktoryzacji , stwierdza się, że każda liczba całkowita większa niż 1 może być przedstawione jednoznacznie jako produkt liczb pierwszych do kolejności czynników. Na przykład,

${\ Displaystyle 1200 = 2 ^ {4} \ cdot 3 \ cdot 5 ^ {2} = (2 \ cdot 2 \ cdot 2 \ cdot 2) \ cdot 3 \ cdot (5 \ cdot 5) = 5 \ cdot 2 \ cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots }$

Twierdzenie mówi dwie rzeczy o tym przykładzie: po pierwsze, że 1200 może być reprezentowane jako iloczyn liczb pierwszych, a po drugie, że bez względu na to, jak to się robi, zawsze będą dokładnie cztery dwójki, jedna 3, dwie piątki i żadne inne liczby pierwsze w produkcie.

Wymaganie, aby czynniki były liczbami pierwszymi, jest konieczne: faktoryzacja zawierająca liczby złożone może nie być unikatowa (na przykład ). ${\ Displaystyle 12 = 2 \ cdot 6 = 3 \ cdot 4}$

Twierdzenie to jest jednym z głównych powodów, dla których 1 nie jest uważana za liczbę pierwszą : gdyby 1 była liczbą pierwszą, to faktoryzacja na liczby pierwsze nie byłaby unikatowa; na przykład,${\ Displaystyle 2 = 2 \ cdot 1 = 2 \ cdot 1 \ cdot 1 = \ ldots}$

Oryginalna wersja Euklidesa

Księga VII, propozycje 30, 31 i 32, a książka IX propozycja 14 Euklides „s Elements są zasadniczo takie oświadczenie i dowód podstawowego twierdzenia.

Jeśli dwie liczby przez pomnożenie siebie tworzą pewną liczbę, a dowolna liczba pierwsza mierzy iloczyn, zmierzy również jedną z pierwotnych liczb.

—  Euklides, Księga Elementów VII , Twierdzenie 30

(Według współczesnej terminologii: jeśli liczba pierwsza p dzieli iloczyn ab , to p dzieli albo a albo b albo oba.) Twierdzenie 30 jest określane jako lemat Euklidesa i jest kluczem w dowodzie podstawowego twierdzenia arytmetyki.

Każda liczba złożona jest mierzona jakąś liczbą pierwszą.

—  Euklides, Księga Elementów VII , Stwierdzenie 31

(Według współczesnej terminologii: każda liczba całkowita większa niż jeden jest dzielona równo przez jakąś liczbę pierwszą.) Twierdzenie 31 dowodzi wprost nieskończonym spadkiem .

Każda liczba albo jest liczbą pierwszą, albo jest mierzona przez jakąś liczbę pierwszą.

—  Euklides, Księga Elementów VII , Stwierdzenie 32

Twierdzenie 32 wywodzi się z twierdzenia 31 i dowodzi, że rozkład jest możliwy.

Jeśli liczba jest najmniejsza niż mierzona liczbami pierwszymi, nie będzie mierzona przez żadną inną liczbę pierwszą z wyjątkiem tych, które pierwotnie ją mierzą.

—  Euklides, Księga Elementów IX , Twierdzenie 14

(Według współczesnej terminologii: najmniejsza wspólna wielokrotność kilku liczb pierwszych nie jest wielokrotnością żadnej innej liczby pierwszej.) Księga IX, twierdzenie 14 wywodzi się z księgi VII, twierdzenie 30 i dowodzi częściowo, że rozkład jest unikalny – punkt krytycznie zauważył André Weil . Rzeczywiście, w tym zdaniu wszystkie wykładniki są równe jeden, więc nic nie mówi się o ogólnym przypadku.

Artykuł 16 Gaussa ' Disquisitiones Arithmeticae jest wczesnym nowoczesny oświadczenie i dowód wykorzystujący modułowy arytmetyki .

Aplikacje

Kanoniczna reprezentacja dodatniej liczby całkowitej

Każdą dodatnią liczbę całkowitą n > 1 można przedstawić dokładnie w jeden sposób jako iloczyn potęg pierwszych:

${\ Displaystyle n = p_ {1} ^ {n_ {1}} p_ {2} ^ {n_ {2}} \ cdots p_ {k} ^ {n_ {k}} = \ prod _ {i = 1} ^ {k}p_{i}^{n_{i}}}$

gdzie p ₁ < p ₂ < ... < p _k są liczbami pierwszymi, a n _i są dodatnimi liczbami całkowitymi. Ta reprezentacja jest powszechnie rozszerzona na wszystkie dodatnie liczby całkowite, w tym 1, przyjętą konwencją, że pusty iloczyn jest równy 1 (pusty iloczyn odpowiada k = 0).

Ta reprezentacja jest nazywany kanonicznej reprezentacji z N , lub standardową formę o n . Na przykład,

999 = 3 ³ × 37,

1000 = 2 ³ × 5 ³ ,

1001 = 7×11×13.

Współczynniki p ⁰ = 1 można wstawić bez zmiany wartości n (na przykład 1000 = 2 ³ ×3 ⁰ ×5 ³ ). W rzeczywistości każda dodatnia liczba całkowita może być jednoznacznie reprezentowana jako nieskończony iloczyn przejęty wszystkich dodatnich liczb pierwszych:

${\ Displaystyle n = 2 ^ {n_ {1}} 3 ^ {n_ {2}} 5 ^ {n_ {3}} 7 ^ {n_ {4}} \ cdots = \ prod _ {i = 1} ^ { \infty }p_{i}^{n_{i}},}$

gdzie skończona liczba n _i to dodatnie liczby całkowite, a reszta to zero. Dopuszczenie ujemnych wykładników zapewnia formę kanoniczną dla dodatnich liczb wymiernych .

Działania arytmetyczne

Kanoniczne reprezentacją urządzenia, największy wspólny dzielnik (GCD) i najmniejszą wspólną wielokrotność (LCM) dwóch liczb i B może być wyrażony w odniesieniu do kanonicznych reprezentacji i b siebie:

${\ Displaystyle {\ zacząć {wyrównany} {2} a \ cdot b i = 2 ^ {a_ {1} + b_ {1}} 3 ^ {a_ {2} + b_ {2}} 5 ^ {a_ {3} +b_{3}}7^{a_{4}+b_{4}}\cdots &&=\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b )&=2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{ 3})}7^{\min(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\min(a_{i},b_{i})},\\ \operatorname {lcm} (a,b)&=2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\ max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\max(a_{i}, b_{i})}.\end{alignedat}}}$

Jednak faktoryzacja liczb całkowitych , zwłaszcza dużych liczb, jest znacznie trudniejsza niż produkty obliczeniowe, GCD lub LCM. Tak więc te formuły mają ograniczone zastosowanie w praktyce.

Funkcje arytmetyczne

Wiele funkcji arytmetycznych jest definiowanych za pomocą reprezentacji kanonicznej. W szczególności wartości funkcji addytywnych i multiplikatywnych są określone przez ich wartości na potęgach liczb pierwszych.

Dowód

Dowód wykorzystuje lemat Euklidesa ( Elementy VII, 30): Jeśli liczba pierwsza dzieli iloczyn dwóch liczb całkowitych, to musi podzielić przynajmniej jedną z tych liczb całkowitych.

Istnienie

Należy wykazać, że każda liczba całkowita większa niż 1 jest albo liczbą pierwszą, albo iloczynem liczb pierwszych. Po pierwsze, 2 to liczba pierwsza. Następnie przez silną indukcję załóżmy, że jest to prawdą dla wszystkich liczb większych niż 1 i mniejszych niż n . Jeśli n jest liczbą pierwszą, nie ma nic więcej do udowodnienia. W przeciwnym razie istnieją liczby całkowite a i b , gdzie n = ab i 1 < a ≤ b < n . Zgodnie z hipotezą indukcji, a = p ₁ p ₂ ⋅⋅⋅ p _j oraz b = q ₁ q ₂ ⋅⋅⋅ q _k są iloczynami liczb pierwszych. Ale wtedy n = ab = p ₁ p ₂ ⋅⋅⋅ p _j q ₁ q ₂ ⋅⋅⋅ q _k jest iloczynem liczb pierwszych.

Wyjątkowość

Załóżmy, że jest liczba całkowita, która ma dwie różne rozkłady na czynniki pierwsze. Niech n będzie najmniejszą taką liczbę całkowitą i zapis n = p ₁ p ₂ ... p _j = q ₁ q ₂ ... q _k , gdzie każdy p _I i Q _i jest liczbą pierwszą. Widzimy, że p ₁ dzieli q ₁ q ₂ ... q _k , więc p ₁ dzieli część q _i przez lemat Euklidesa . Bez utraty ogólności powiedzmy, że p ₁ dzieli q ₁ . Ponieważ p ₁ i q ₁ są obie liczby pierwsze, wynika z tego, że p ₁ = q ₁ . Wracając do faktoryzacji n , możemy anulować te dwa czynniki i stwierdzić, że p ₂ ... p _j = q ₂ ... q _k . Mamy teraz dwie odrębne rozkłady na czynniki pierwsze pewnej liczby całkowitej, ściśle mniejszej niż n , co jest sprzeczne z minimalnością n .

Wyjątkowość bez lematu Euklidesa

Podstawowe twierdzenie arytmetyki można również udowodnić bez użycia lematu Euklidesa. Dowód, który następuje, jest inspirowany oryginalną wersją algorytmu Euklidesa autorstwa Euklidesa .

Załóżmy, że jest to najmniejsza dodatnia liczba całkowita, która jest iloczynem liczb pierwszych na dwa różne sposoby. Nawiasem mówiąc, oznacza to , że , jeśli istnieje, musi być liczbą złożoną większą niż . Teraz powiedz ${\displaystyle s}$${\displaystyle s}$${\ Displaystyle 1}$

${\ Displaystyle {\ zacząć {wyrównane} s& = p_ {1} p_ {2} \ cdots p_ {m} \ \ & = q_ {1} q_ {2} \ cdots q_ {n}. \ koniec {wyrównane}} }$

Każdy musi być różny od każdego W przeciwnym razie, jeśli powiedzmy , istniałaby jakaś dodatnia liczba całkowita, która jest mniejsza niż s i ma dwie różne rozkłady na czynniki pierwsze. Można również przypuszczać, że w razie potrzeby wymieniając dwie faktoryzacje. ${\displaystyle p_{i}}$${\displaystyle q_{j}.}$${\displaystyle p_{i}=q_{j},}$${\ Displaystyle t = s/p_ {i} = s/q_ {j}}$${\displaystyle p_{1}<q_{1},}$

Ustawienie i jeden ma Wynika to z tego ${\ Displaystyle P = p_ {2} \ cdots p_ {m}}$${\ Displaystyle Q = q_ {2} \ cdots q_ {n},}$${\displaystyle s=p_{1}P=q_{1}Q.}$

${\displaystyle (q_{1}-p_{1})Q=p_{1}(PQ)<s.}$

Ponieważ liczby całkowite dodatnie mniejsze niż s miały mieć unikalną faktoryzację pierwszą, muszą wystąpić w faktoryzacji jednego lub Q . Ten drugi przypadek jest niemożliwy, ponieważ Q , mniejsze niż s , musi mieć unikalną pierwszą faktoryzację i różni się od wszystkich. Pierwszy przypadek jest również niemożliwy, ponieważ jeśli jest dzielnikiem tego , musi być również dzielnikiem, którego jest niemożliwy, ponieważ i są odrębnymi liczbami pierwszymi. ${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1}}$${\displaystyle p_{1}}$${\displaystyle q_{j}.}$${\displaystyle p_{1}}$${\displaystyle q_{1}-p_{1},}$${\displaystyle q_{1},}$${\displaystyle p_{1}}$${\displaystyle q_{1}}$

Dlatego nie może istnieć najmniejsza liczba całkowita z więcej niż jedną odrębną faktoryzacją pierwszą. Każda dodatnia liczba całkowita musi być albo samą liczbą pierwszą, która rozkłada się jednoznacznie, albo złożoną, która również rozkłada się jednoznacznie na liczby pierwsze, lub, w przypadku liczby całkowitej , nie jest rozkładana na żadną liczbę pierwszą. ${\ Displaystyle 1}$

Uogólnienia

Pierwsze uogólnienie twierdzenia znajduje się w drugiej monografii Gaussa (1832) na temat dwukwadratowej wzajemności . Dokument ten wprowadził, co obecnie nazywa się pierścień z całkowitych Gaussa , zbiór wszystkich liczb zespolonych + bi , gdzie i b są liczbami całkowitymi. Jest to teraz oznaczone przez On pokazał, że ten pierścień ma cztery jednostki ±1 i ± i , że niezerowe, niejednostkowe liczby należą do dwóch klas, liczb pierwszych i kompozytów, i że (z wyjątkiem porządku) kompozyty mają unikalna faktoryzacja jako iloczyn liczb pierwszych. ${\ Displaystyle \ mathbb {Z} [i].}$

Podobnie w 1844 roku, pracując nad wzajemnością sześcienną , Eisenstein wprowadził pierścień , gdzie jest pierwiastkiem sześciennym jedności . To jest pierścień liczb całkowitych Eisensteina , który udowodnił, że ma sześć jednostek i ma unikalną faktoryzację. ${\ Displaystyle \ mathbb {Z} [\ omega]}$${\ Displaystyle \ omega = {\ Frac {-1 + {\ sqrt {-3}}} {2}},}$   ${\ Displaystyle \ omega ^ {3} = 1}$${\ Displaystyle \ pm 1 \ pm \ omega \ pm \ omega ^ {2}}$

Odkryto jednak również, że unikalna faktoryzacja nie zawsze jest aktualna. Przykład podaje . Na tym ringu trzeba ${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}]}$

${\ Displaystyle 6 = 2 \ cdot 3 = (1+ {\ sqrt {-5}}) (1-{\ sqrt {-5}}).}$

Takie przykłady spowodowały modyfikację pojęcia „pierwszy”. W może być dowiedzione, że w przypadku każdego z powyższych czynników może być przedstawiony w postaci produktu, na przykład, 2 = ab , wówczas jeden z i b muszą być jednostką. To jest tradycyjna definicja „pierwszego”. Można również udowodnić, że żaden z tych czynników nie jest zgodny z lematem Euklidesa; na przykład 2 nie dzieli ani (1 + √ −5 ) ani (1 − √ −5 ), mimo że dzieli ich iloczyn 6. W algebraicznej teorii liczb 2 nazywa się nierozkładalne w (tylko podzielne przez siebie lub jednostkę), ale nie jest liczbą pierwszą in (jeśli dzieli produkt, musi podzielić jeden z czynników). Wzmianka o jest wymagana, ponieważ 2 jest liczbą pierwszą i nieredukowalną. Używając tych definicji można udowodnić, że w każdej dziedzinie integralnej liczba pierwsza musi być nieredukowalna. Klasyczny lemat Euklidesa można przeformułować jako „w pierścieniu liczb całkowitych każda nieredukowalna jest liczbą pierwszą”. Odnosi się to również w a , ale nie w${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}]}$${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}]}$${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}]}$${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}]}$${\ Displaystyle \ mathbb {Z}.}$${\ Displaystyle \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} [i]}$${\ Displaystyle \ mathbb {Z} [\ omega],}$${\ Displaystyle \ mathbb {Z} [{\ sqrt {-5}}].}$

Pierścienie, w których rozkład na czynniki nieredukowalne jest zasadniczo unikalne, nazywane są unikalnymi domenami rozkładu na czynniki . Ważnymi przykładami są wielomianowe pierścienie ciągu liczb całkowitych lub nad pola , domeny euklidesowe i główne domeny idealne .

W 1843 Kummer wprowadził do nowoczesnej teorii ideałów , specjalnych podzbiorów pierścieni, koncepcję liczby idealnej , rozwiniętą dalej przez Dedekinda (1876) . Mnożenie jest zdefiniowane dla ideałów, a pierścienie, w których mają one unikalną faktoryzację, nazywane są domenami Dedekind .

Istnieje wersja unikatowej faktoryzacji dla liczb porządkowych , chociaż wymaga ona pewnych dodatkowych warunków, aby zapewnić unikalność.

Zobacz też

• Faktoryzacja  liczby całkowitej — rozkład liczby całkowitej na produkt
• Sygnatura  pierwsza – Multiset wykładników pierwszych w faktoryzacji liczby pierwszej

Uwagi

Bibliografia

Disquisitiones Arithmeticae został przetłumaczony z łaciny na język angielski i niemiecki. Wydanie niemieckie zawiera wszystkie jego artykuły z teorii liczb: wszystkie dowody kwadratowej wzajemności, określenie znaku sumy Gaussa, badania nad dwukwadratową wzajemnością i niepublikowane notatki.

• Gaussa, Carla Friedricha; Clarke, Arthur A. (tłumacz na język angielski) (1986), Disquisitiones Arithemeticae (drugie wydanie poprawione) , New York: Springer , ISBN 978-0-387-96254-2
• Gaussa, Carla Friedricha; Maser, H. (tłumacz na język niemiecki) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae i inne artykuły dotyczące teorii liczb) (wydanie drugie) , New York: Chelsea, ISBN 0-8284-0191-8

Dwie monografie Gaussa opublikowane na temat dwukwadratowej wzajemności mają kolejno ponumerowane sekcje: pierwsza zawiera §§ 1-23, a druga §§ 24-76. Przypisy odnoszące się do nich mają postać „Gauss, BQ, § n ”. Przypisy odnoszące się do Disquisitiones Arithmeticae mają postać „Gauss, DA, art. n ”.

• Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima , Getynga: Komentarz. Soc. regiae sci, Getynga 6
• Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda , Getynga: Komentarz. Soc. regiae sci, Getynga 7

Są to w Werke Gaussa , tom II, s. 65–92 i 93–148; Tłumaczenia niemieckie znajdują się na s. 511–533 i 534–586 niemieckiego wydania Disquisitiones .

• Baker, Alan (1984), Zwięzłe wprowadzenie do teorii liczb , Cambridge, Wielka Brytania: Cambridge University Press, ISBN 978-0-521-28654-1
• Euclid (1956), trzynaście ksiąg Elementów , 2 (Księgi III-IX), przetłumaczone przez Thomasa Little Heath (wydanie drugie nieskrócone ed.), New York: Dover , ISBN 978-0-486-60089-5
• Hardy, GH ; Wright, EM (2008) [1938]. Wprowadzenie do teorii liczb . Poprawione przez DR Heath-Browna i JH Silvermana . Przedmowa Andrew Wilesa . (wyd. 6). Oksford: Oxford University Press . Numer ISBN 978-0-19-921986-5. MR  2445243 . Zbl  1159.11001 .
• A. Korniłowicza; P. Rudnicki (2004), „Podstawowe twierdzenie arytmetyki”, Matematyka sformalizowana , 12 (2): 179–185
• Long, Calvin T. (1972), Elementary Wprowadzenie do teorii liczb (2nd ed.), Lexington: DC Heath and Company , LCCN  77-171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elementy teorii liczb , Englewood Cliffs: Prentice Hall , LCCN  77-81766.
• Riesel, Hans (1994), Liczby pierwsze i metody komputerowe dla faktoryzacji (wydanie drugie) , Boston: Birkhäuser, ISBN 0-8176-3743-5
• Weil, André (2007) [1984]. Teoria liczb: podejście poprzez historię od Hammurapiego do Legendre . Nowoczesna klasyka Birkhäuser. Boston, MA: Birkhäuser. Numer ISBN 978-0-817-64565-6.
• Weisstein, Eric W. „Liczba nienormalna” . MatematykaŚwiat .
• Weisstein, Eric W. „Podstawowe twierdzenie o arytmetyce” . MatematykaŚwiat .

Zewnętrzne linki

• Dlaczego podstawowe twierdzenie arytmetyki nie jest oczywiste?
• NWD i podstawowe twierdzenie o arytmetyce na przecięciu węzła .
• PlanetMath: Dowód podstawowego twierdzenia arytmetyki
• Fermat's Last Theorem Blog: Unique Factorization , blog, który opisuje historię ostatniego twierdzenia Fermata od Diofanta z Aleksandrii do dowodu Andrew Wilesa .
• „Podstawowe twierdzenie o arytmetyce” Hectora Zenila, Wolfram Demonstrations Project , 2007.
• Brud, James. „1 i liczby pierwsze” . Numerfil . Brady Haran .