Art of Problem Solving | Tomas Rosprim

Równanie Diophantine’a jest równaniem odnoszącym się do kwantytów liczb całkowitych (lub czasami liczb naturalnych lub całkowitych).

Znalezienie rozwiązania lub rozwiązań równania Diophantine’a jest ściśle związane z arytmetyką modularną i teorią liczb. Często, gdy równanie Diophantine ma nieskończenie wiele rozwiązań, forma parametryczna jest używana do wyrażenia relacji między zmiennymi równania.

Równania Diophantine’a zostały nazwane na cześć starożytnego greckiego/aleksandryjskiego matematyka Diophantusa.

Łączenie liniowe

Równanie Diophantine’a w postaci jest znane jako kombinacja liniowa. Jeśli dwie względnie pierwsze liczby całkowite i zapiszemy w tej postaci z , to równanie będzie miało nieskończoną liczbę rozwiązań. Mówiąc ogólniej, zawsze będzie nieskończona liczba rozwiązań, gdy . Jeśli , to nie ma żadnych rozwiązań tego równania. Aby zobaczyć dlaczego, rozważ równanie . jest dzielnikiem LHS (zauważ również, że zawsze musi być liczbą całkowitą). Jednak nigdy nie będzie wielokrotnością , stąd nie ma rozwiązań.

Teraz rozważmy przypadek, w którym . Zatem . Jeśli i są względnie pierwsze, to wszystkie rozwiązania są oczywiście w postaci dla wszystkich liczb całkowitych . Jeśli nie są, to po prostu dzielimy je przez ich największy wspólny dzielnik.

Trójka pitagorejska

Główny artykuł: Trójka pitagorejska

Trójka pitagorejska to zbiór trzech liczb całkowitych, które spełniają Twierdzenie Pitagorejskie, . Istnieją trzy główne metody znajdowania trójek pitagorejskich:

Metoda Pitagorasa

Jeśli jest liczbą nieparzystą, to jest trójką pitagorejską.

Metoda Platona

Jeśli , to jest trójką pitagorejską.

Metoda Babilońska

Dla dowolnego , mamy jest trójką pitagorejską.

Suma potęg czwartych

Równanie postaci nie ma rozwiązań całkowitych, w następujący sposób:Zakładamy, że równanie ma rozwiązania całkowite i rozważamy rozwiązanie, które minimalizuje . Niech tym rozwiązaniem będzie . Jeśli , to ich GCD musi być równe . Rozwiązanie byłoby wtedy rozwiązaniem mniejszym od , co jest sprzeczne z naszym założeniem. Zatem to równanie nie ma rozwiązań całkowitych.

Jeśli , to kontynuujemy zadanie kazuistyczne, w .

Zauważmy, że każdy kwadrat, a więc każda czwarta potęga, jest albo , albo . Dowód na to jest dość prosty i można go pokazać samemu.

Przypadek 1:

To implikowałoby , sprzeczność.

Przypadek 2:

To implikowałoby , sprzeczność, ponieważ założyliśmy .

Przypadek 3: , i

Wiemy też, że kwadraty są albo , albo . Zatem wszystkie czwarte potęgi są albo , albo .

Przez podobne podejście pokazujemy, że:

, więc .

Jest to sprzeczność, gdyż implikuje, że jest nieparzyste, a implikuje, że jest parzyste. QED

Równania Pell’a

Główny artykuł: Równanie Pella

Równanie Pella to rodzaj równania Diophantine’a w postaci dla liczby naturalnej . Rozwiązania równania Pella, gdy nie jest kwadratem doskonałym, są związane z rozwinięciem ułamka ciągłego . Jeśli jest okresem ułamka ciągłego, a jest tą zbieżnością, to wszystkie rozwiązania równania Pella są w postaci dla dodatniej liczby całkowitej .

Metody rozwiązywania

Płaszczyzna współrzędnych

Zauważmy, że każdą kombinację liniową można przekształcić w równanie liniowe , które jest po prostu równaniem nachylenia linii. Rozwiązania równania diofantycznego odpowiadają punktom kratowym, które leżą na linii. Na przykład, rozważmy równanie lub . Jednym z rozwiązań jest (0,1). Jeśli wykreślić prostą, łatwo zauważyć, że przecina ona punkt kratowy, gdy x i y zwiększają się lub zmniejszają o tę samą wielokrotność odpowiednio i (jak to rozumieć?). Stąd rozwiązania równania można zapisać parametrycznie (jeśli myślimy o jako o „punkcie początkowym”).

Modular Arithmetic

Czasami arytmetyka modularna może być użyta do udowodnienia, że nie istnieją rozwiązania danego równania Diophantine. W szczególności, jeśli pokażemy, że dane równanie nigdy nie jest prawdziwe mod , dla jakiejś liczby całkowitej , to pokazaliśmy, że równanie jest fałszywe. Jednak ta technika nie może być użyta do pokazania, że rozwiązania równania Diophantine istnieją.

Indukcja

Czasami, gdy znaleziono kilka rozwiązań, indukcja może być użyta do znalezienia rodziny rozwiązań. Techniki takie jak nieskończone zstępowanie mogą również pokazać, że nie istnieją żadne rozwiązania danego równania lub że nie istnieją rozwiązania spoza danej rodziny.

Rozwiązania ogólne

Naturalne jest pytanie, czy istnieje ogólne rozwiązanie równań diofantycznych, tzn. algorytm, który znajdzie rozwiązania dla dowolnego równania diofantycznego. Jest to znane jako dziesiąty problem Hilberta. Odpowiedź jednak brzmi: nie.

Ostatnie twierdzenie Fermata

Główny artykuł: Ostatnie Twierdzenie Fermata

znane jest jako Ostatnie Twierdzenie Fermata ze względu na warunek . W 1600 roku Fermat, podczas pracy nad książką o równaniach diofantycznych, napisał na marginesie komentarz o następującej treści: „Mam naprawdę cudowny dowód tej tezy, który ten margines jest zbyt wąski, by go pomieścić”. Fermat rzeczywiście wysunął wiele przypuszczeń i zaproponował wiele „twierdzeń”, ale nie był jednym z tych, którzy zapisywali dowody lub coś innego niż nabazgrane komentarze. Po jego śmierci wszystkie jego przypuszczenia zostały ponownie udowodnione (albo fałszywe, albo prawdziwe) z wyjątkiem Ostatniego Twierdzenia Fermata. Po ponad 350 latach nieudanych prób udowodnienia tego twierdzenia, zostało ono w końcu udowodnione przez Andrew Wilesa po tym, jak spędził ponad 7 lat pracując nad 200-stronicowym dowodem i kolejny rok naprawiając błąd w oryginalnym dowodzie.

Problemy

Wprowadzenie

Dwaj farmerzy zgadzają się, że świnie są warte dolarów, a kozy dolarów. Kiedy jeden farmer jest winien drugiemu pieniądze, płaci dług w świniach lub kozach, z „resztą” otrzymaną w postaci kóz lub świń, jak trzeba. (Na przykład, dług dolarów może być spłacony dwiema świniami, a jedną kozę otrzymuje się jako resztę). Jaka jest kwota najmniejszego dodatniego długu, który można spłacić w ten sposób?

(Źródło)

Intermediate

Niech będzie wielomianem o współczynnikach całkowitych, który spełnia i Biorąc pod uwagę, że ma dwa różne rozwiązania całkowite i , znajdź iloczyn . (Źródło)