Hoe een lineaire Diophantische vergelijking op te lossen

Een diophantische vergelijking is een algebraïsche bewerking met de speciale beperking dat alleen rekening wordt gehouden met oplossingen waarvan de variabelen gehele getallen zijn. Over het algemeen zijn Diophantine-vergelijkingen erg moeilijk op te lossen en er zijn veel benaderingen van een resultaat die mogelijk nog geen definitieve oplossing vormen. (Fermat`s Final Theorem is een beroemde Diophantine-vergelijking die 350 jaar onopgelost bleef.) Echter, een Diophantine-vergelijking

2

Past het Euclid-algoritme toe op de coëfficiënten "a" en "b". Dit vervult twee doelstellingen. Zoek eerst uit of de coëfficiënten een gemeenschappelijke factor hebben. Als we proberen op te lossen 4x + 10y = 3, we kunnen meteen bevestigen dat het deel links van het gelijkteken altijd gelijk is en als de uitdrukking aan de rechterkant van het teken altijd niet is, is het onmogelijk dat er een oplossing is met positieve gehele getallen. Op dezelfde manier als we er 4 hebbenx + 10y = 2, we kunnen de vergelijking vereenvoudigen tot 2x + 5y = 1. Het tweede doel dat moet worden vervuld, is dat als er een oplossing bestaat, we deze kunnen bouwen op basis van de sequentie van quotiënten van het Euclid-algoritme.

3

als a, b, en c hebben een gemeenschappelijke factor, vereenvoudig gewoon de vergelijking door beide kanten van de operatie tussen die factor te verdelen. als a en b hebben een gemeenschappelijke factor die niet gedeeld wordt door c, stop op dat moment: er zijn geen hele oplossingen voor de vergelijking.

4

Maak een tabel met drie rijen, zoals hieronder weergegeven.

5

Stel de quotiënten van uw Euclid-algoritme in de bovenste rij in. Deze afbeelding illustreert hoe het proces er zou uitzien 87x - 64y = 3

6

Vul de volgende twee rijen van links naar rechts met de volgende procedure: Noteer voor elke cel de som van de bovenste cel van die kolom en de twee directe cellen links ervan.

7

Kijk naar de laatste twee kolommen van uw hele tafel. De laatste kolom moet bevatten a en b, de initiële coëfficiënten van de vergelijking. (Controleer anders uw sommen opnieuw.) De voorlaatste kolom bevat twee andere nummers. In dit voorbeeld zijn a = 87 en b = 64, de voorlaatste kolom bevat 34 en 25.

8

Merk op hoe 87 * 25 - 64 * 34 = -1. De determinant van de 2x2-matrix rechtsonder is altijd 1 positief of negatief. Als het negatief is, vermenigvuldig dan beide zijden van de vergelijking met -1 om -87 * 25 + 64 * 34 = 1 te krijgen. Deze waarneming is het startpunt om een ​​oplossing te bouwen.

9

Ga terug naar de oorspronkelijke vergelijking. Herschrijf de vorige gelijkheid als 87 * (- 25) + 64 * (34) = 1 of als 87 * (- 25) - 64 * (- 34) = 1, wat dichter bij de oorspronkelijke vergelijking ligt . Voor het voorbeeld is de tweede optie beter omdat deze overeenkomt met de term en -64 in het origineel wanneer y = -34.

10

Alleen nu moeten we ons zorgen maken over de constante c rechts van de vergelijking. Aangezien de vorige vergelijking laat zien dat ax + by = 1, vermenigvuldig beide zijden met c om een ​​(cx) + b (ca.y) = c. Als (-25, -34) een oplossing is voor 87x - 64y = 1, dan (-75, -102) is een oplossing voor 87x-64y = 3

11

Als een Diophantische vergelijking een oplossing heeft, dan heeft het onbeperkte oplossingen. Dit komt omdat ax + by = a (x + b) + b (y-a) = a (x + 2b) + b (y-2a), en in het algemeen totx + by = a (x +kb) + b (y-ka) voor elk geheel getal k. Dientengevolge, als (-75, -102) een oplossing is voor 87x-64y = 3, andere oplossingen (-11, -15), (53.72), (117.159), etc. De algemene oplossing kan worden geschreven als (53 + 64k, 72 + 87k) gedaan k is een geheel getal.