Art of Problem Solving | Tomas Rosprim

Een Diophantijnse vergelijking is een vergelijking die betrekking heeft op gehele (of soms natuurlijke getallen of gehele getallen) quanitieten.

Het vinden van de oplossing of oplossingen van een Diophantijnse vergelijking is nauw verbonden met modulaire rekenkunde en getaltheorie. Vaak, wanneer een Diophantine vergelijking oneindig veel oplossingen heeft, wordt de parametrische vorm gebruikt om de relatie tussen de variabelen van de vergelijking uit te drukken.

Diophantine vergelijkingen zijn genoemd naar de oude Griekse/Alexandrijnse wiskundige Diophantus.

Lineaire Combinatie

Een Diophantine vergelijking in de vorm staat bekend als een lineaire combinatie. Als twee betrekkelijk priemgetallen en in deze vorm worden geschreven met , dan zal de vergelijking een oneindig aantal oplossingen hebben. Meer in het algemeen geldt dat er altijd een oneindig aantal oplossingen zal zijn als . Als , dan zijn er geen oplossingen voor de vergelijking. Om te zien waarom, beschouw de vergelijking . is een deler van de LHS (merk ook op dat altijd een geheel getal moet zijn). zal echter nooit een veelvoud zijn van , dus er bestaan geen oplossingen.

Bedenk nu het geval waarin . Dus . Als en relatief priem zijn, dan zijn alle oplossingen uiteraard in de vorm voor alle gehele getallen . Zijn ze dat niet, dan delen we ze gewoon door hun grootste gemene deler.

Pythagoreïsche drietallen

Hoofdartikel: Pythagorean-drievoud

Een Pythagorean-drievoud is een verzameling van drie gehele getallen die voldoen aan de Stelling van Pythagoras, . Er zijn drie hoofdmethoden om Pythagoras-driehoeken te vinden:

Methode van Pythagoras

Als een oneven getal is, dan is een Pythagoras-drievoud.

Methode van Plato

Als , dan is een Pythagoras-drievoud.

Babylonische methode

Voor elke geldt dat een Pythagoreïsch tripel is.

Som van vierde machten

Een vergelijking van de vorm heeft geen gehele oplossingen, en wel als volgt:We nemen aan dat de vergelijking wel gehele oplossingen heeft, en beschouwen de oplossing die minimaliseert. Laat deze oplossing zijn. Als dan moet hun GCD gelijk zijn aan . De oplossing zou dan een oplossing zijn kleiner dan , hetgeen in tegenspraak is met onze aanname. Deze vergelijking heeft dus geen gehele oplossingen.

Als , dan gaan we verder met casework, in .

Merk op dat elk kwadraat, en dus elke vierde macht, òf òf is. Het bewijs hiervoor is vrij eenvoudig, en u kunt het zelf aantonen.

Geval 1:

Dit zou impliceren, een tegenstrijdigheid.

Zaak 2:

Dit zou betekenen , een tegenspraak omdat we uitgingen van .

Zaak 3: , en

We weten ook dat kwadraten ofwel ofwel zijn. Dus alle vierde machten zijn of of .

Met een soortgelijke benadering laten we zien dat:

, dus .

Dit is een tegenspraak, want impliceert dat oneven is, en impliceert dat even is. QED

Pell-vergelijkingen

Hoofdartikel: Pell-vergelijking

Een Pell-vergelijking is een type Diophantijnse vergelijking in de vorm voor natuurlijk getal . De oplossingen van de Pell-vergelijking als geen volmaakt kwadraat is, zijn verbonden met de voortdurende breukexpansie van . Als de periode is van de voortgezette breuk en de e convergent, dan hebben alle oplossingen van de vergelijking van Pell de vorm voor positief geheel getal .

Oplosmethoden

Coordinatenvlak

Merk op dat elke lineaire combinatie kan worden getransformeerd in de lineaire vergelijking , die gewoon de hellingshoek-vergelijking voor een lijn is. De oplossingen van de diofantische vergelijking komen overeen met de roosterpunten die op de rechte liggen. Neem bijvoorbeeld de vergelijking of . Eén oplossing is (0,1). Als je de lijn grafisch weergeeft, is het gemakkelijk te zien dat de lijn een roosterpunt snijdt als x en y toenemen of afnemen met hetzelfde veelvoud van respectievelijk en (formulering?). De oplossingen van de vergelijking kunnen dus parametrisch worden geschreven (als we als een “beginpunt” beschouwen).

Modulaire rekenkunde

Soms kan modulaire rekenkunde gebruikt worden om te bewijzen dat er geen oplossingen van een gegeven Diophantijnse vergelijking bestaan. Als men aantoont dat de vergelijking in kwestie nooit waar is mod , voor een geheel getal , dan heeft men aangetoond dat de vergelijking onwaar is. Deze techniek kan echter niet worden gebruikt om aan te tonen dat oplossingen van een Diophantijnse vergelijking wel bestaan.

Inductie

Soms kan, als een paar oplossingen zijn gevonden, inductie worden gebruikt om een familie van oplossingen te vinden. Technieken zoals oneindige afstamming kunnen ook aantonen dat er geen oplossingen voor een bepaalde vergelijking bestaan, of dat er geen oplossingen buiten een bepaalde familie bestaan.

Algemene oplossingen

Het ligt voor de hand zich af te vragen of er een algemene oplossing voor Diophantijnse vergelijkingen bestaat, d.w.z. een algoritme dat de oplossingen voor alle gegeven Diophantijnse vergelijkingen zal vinden. Dit staat bekend als het tiende probleem van Hilbert. Het antwoord is echter nee.

De laatste stelling van Fermat

Hoofdartikel: De Laatste Stelling van Fermat

staat bekend als de Laatste Stelling van Fermat vanwege de voorwaarde . In de jaren 1600 schreef Fermat, toen hij bezig was met een boek over Diophantine Vergelijkingen, een commentaar in de kantlijn met de strekking van “Ik heb een werkelijk wonderbaarlijk bewijs van deze stelling waarvoor deze kantlijn te smal is om het te bevatten”. Fermat maakte veel vermoedens en stelde veel “stellingen” voor, maar was niet iemand die de bewijzen opschreef of veel anders dan gekrabbelde commentaren. Na zijn dood werden al zijn vermoedens opnieuw bewezen (vals of waar), behalve de Laatste Stelling van Fermat. Na meer dan 350 jaar niet bewezen te zijn, werd de stelling eindelijk bewezen door Andrew Wiles nadat hij meer dan 7 jaar had gewerkt aan het 200 pagina’s tellende bewijs, en nog een jaar om een fout in het oorspronkelijke bewijs te herstellen.

Problemen

Inleiding

Twee boeren zijn het erover eens dat varkens dollar waard zijn en dat geiten dollar waard zijn. Wanneer de ene boer de andere geld schuldig is, betaalt hij de schuld in varkens of geiten, met “wisselgeld” ontvangen in de vorm van geiten of varkens als dat nodig is. (Bijvoorbeeld, een schuld van dollar kan worden betaald met twee varkens, met één geit als wisselgeld). Wat is het bedrag van de kleinste positieve schuld die op deze manier kan worden opgelost?

(Bron)

Tussentijds

Laat een veelterm zijn met gehele coëfficiënten die voldoet aan en Gegeven dat twee verschillende gehele oplossingen en heeft, vind het product . (Bron)