Art of Problem Solving | Tomas Rosprim

En diophantinsk ligning er en ligning, der relaterer heltalskvantiteter (eller undertiden naturlige tal eller hele tal).

Findelse af løsningen eller løsningerne til en diophantinsk ligning er tæt knyttet til modulær aritmetik og talteori. Ofte, når en diophantinsk ligning har uendeligt mange løsninger, anvendes parametrisk form til at udtrykke forholdet mellem ligningens variabler.

Diophantinske ligninger er opkaldt efter den oldgræske/allexandrinske matematiker Diophantus.

Linær kombination

En diophantinsk ligning i formen er kendt som en lineær kombination. Hvis to relativt primtal og skrives i denne form med , vil ligningen have et uendeligt antal løsninger. Mere generelt vil der altid være et uendeligt antal løsninger, når . Hvis , er der ingen løsninger til ligningen. For at se hvorfor, kan man betragte ligningen . er en divisor af LHS (bemærk også, at altid skal være et heltal). Men vil aldrig være et multiplum af , og derfor findes der ingen løsninger.

Se nu på det tilfælde, hvor . Dermed er . Hvis og er relativt primtal, så er alle løsninger naturligvis i formen for alle hele tal . Hvis de ikke er det, dividerer vi dem simpelthen med deres største fælles divisor.

Pythagoræiske trioler

Hovedartikel: Pythagoræisk trippel

En pythagoræisk trippel er en mængde af tre hele tal, der opfylder den pythagoræiske sætning, . Der findes tre hovedmetoder til at finde pythagoræiske trioler:

Pythagoras’ metode

Hvis er et ulige tal, så er en pythagoræisk trippel.

Platons metode

Hvis , så er en pythagoræisk trippel.

Babylonisk metode

For ethvert har vi er en pythagoræisk tripel.

Summen af fjerde potenser

En ligning af formen har ingen heltalsløsninger, som følger: Vi antager, at ligningen har heltalsløsninger, og betragter den løsning, som minimerer . Lad denne løsning være . Hvis , så må deres GCD være lig med . Løsningen ville så være en løsning, der er mindre end , hvilket er i modstrid med vores antagelse. Denne ligning har således ingen heltalsløsninger.

Hvis , fortsætter vi så med kasuistik, i .

Bemærk, at hvert kvadrat, og dermed hver fjerde potens, er enten eller . Beviset for dette er ret simpelt, og du kan selv vise det.

Fald 1:

Dette ville indebære , en selvmodsigelse.

Fald 2:

Dette ville indebære , en modsigelse, da vi antog .

Fald 3: , og

Vi ved også, at firkanter er enten eller . Således er alle fjerde potenser enten eller .

Med en lignende fremgangsmåde viser vi, at:

, altså .

Dette er en modsigelse, da indebærer, at er ulige, og indebærer, at er lige. QED

Pell-ligninger

Hovedartikel: Pell-ligning

En Pell-ligning er en type diophantine ligning i formen for det naturlige tal . Løsningerne til Pell-ligningen, når ikke er et perfekt kvadrat, er forbundet med den fortsatte brøkudvidelse af . Hvis er perioden for den fortsatte brøk og er den te konvergent, er alle løsninger til Pell-ligningen i formen for positivt heltal .

Løsningsmetoder

Koordinatplan

Bemærk, at enhver lineær kombination kan omdannes til den lineære ligning , som blot er hældningsintervalligningen for en linje. Løsningerne til den diophantine ligning svarer til gitterpunkter, der ligger på linjen. Betragt f.eks. ligningen eller . En af løsningerne er (0,1). Hvis du tegner linjen grafisk, er det let at se, at linjen skærer et gitterpunkt, når x og y stiger eller falder med det samme multiplum af henholdsvis og (ordlyd?). Derfor kan løsningerne til ligningen skrives parametrisk (hvis vi tænker på som et “udgangspunkt”).

Modulær aritmetik

I nogle tilfælde kan modulær aritmetik bruges til at bevise, at der ikke findes nogen løsninger til en given diophantinsk ligning. Specifikt, hvis vi viser, at den pågældende ligning aldrig er sand mod for et eller andet heltal , så har vi vist, at ligningen er falsk. Denne teknik kan dog ikke bruges til at vise, at der findes løsninger til en diophantinsk ligning.

Induktion

I nogle tilfælde, når der er fundet nogle få løsninger, kan man bruge induktion til at finde en familie af løsninger. Teknikker som infinite Descent kan også vise, at der ikke findes løsninger til en bestemt ligning, eller at der ikke findes løsninger uden for en bestemt familie.

Generelle løsninger

Det er naturligt at spørge, om der findes en generel løsning for diophantinske ligninger, dvs. en algoritme, der kan finde løsningerne for enhver given diophantinsk ligning. Dette er kendt som Hilberts tiende problem. Svaret er imidlertid nej.

Fermats sidste sætning

Hovedartikel: Fermats sidste sætning

er kendt som Fermats sidste sætning for betingelsen . I 1600-tallet skrev Fermat, da han arbejdede sig igennem en bog om diophantinske ligninger, en kommentar i marginen, der lød: “Jeg har et virkelig vidunderligt bevis for denne sætning, som denne margin er for smal til at indeholde”. Fermat fremsatte faktisk mange formodninger og foreslog masser af “sætninger”, men var ikke den, der skrev beviserne ned eller meget andet end kladrede kommentarer. Efter hans død blev alle hans formodninger genbevist (enten falske eller sande) med undtagelse af Fermats sidste sætning. Efter at teoremet i over 350 år ikke var blevet bevist, blev det endelig bevist af Andrew Wiles, efter at han havde brugt over 7 år på at arbejde på det 200 sider lange bevis og yderligere et år på at rette en fejl i det oprindelige bevis.

Problemer

Introduktion

To landmænd er enige om, at grise er dollars værd, og at geder er dollars værd. Når den ene landmand skylder den anden penge, betaler han gælden i svin eller geder, idet han efter behov modtager “byttepenge” i form af geder eller svin. (F.eks. kan en gæld på dollar betales med to grise, mens man modtager en ged i byttepenge). Hvor stor er den mindste positive gæld, der kan løses på denne måde?