Hoe om `n lineêre Diophantine vergelyking op te los

`N Diofantiese vergelyking is `n algebraïese operasie met die spesiale beperking dat dit slegs oplossings in ag neem waarvan die veranderlikes heelgetalle is. In die algemeen is Diophantine vergelykings baie moeilik om op te los en daar is baie benaderings tot `n resultaat wat nog nie definitief `n oplossing kan vorm nie. (Fermat se Finale Stelling is `n bekende Diophantine vergelyking wat 350 jaar onopgelos gebly het.) `N Diofantiese vergelyking

2

Pas die Euclid-algoritme toe op die koëffisiënte "a" en "b". Dit voldoen aan twee doelwitte. Kyk eers of die koëffisiënte `n gemeenskaplike faktor het. As ons probeer om op te los 4x + 10y = 3, kan ons sê dadelik dat `n deel aan die linkerkant van die gelyk teken altyd selfs, en synde die uitdrukking aan die regterkant van die teken altyd nie, is dit onmoontlik om `n oplossing met `n positiewe heelgetalle. Op `n soortgelyke manier as ons 4 hetx + 10y = 2, kan ons die vergelyking vereenvoudig tot 2x + 5y = 1. Die tweede doelwit om te vervul is dat as daar `n oplossing bestaan, ons dit kan bou uit die volgorde van kwosiënte van die Euclid-algoritme.

3

indien `n, b, en c het `n gemeenskaplike faktor, vereenvoudig die vergelyking deur beide kante van die operasie tussen daardie faktor te verdeel. indien a en b het `n gemeenskaplike faktor wat nie gedeel word nie c, stop op daardie oomblik: daar is geen hele oplossings vir die vergelyking nie.

4

Maak `n tabel van drie rye soos hieronder getoon.

5

Stel die kwosiënte van jou Euclid-algoritme in die boonste ry. Hierdie prent illustreer hoe die proses sal lyk 87 op te losx - 64y = 3

6

Vul die volgende twee rye van links na regs met die volgende prosedure: Skryf vir elke sel die som van die boonste sel van die kolom en die twee onmiddellike selle aan die linkerkant neer.

7

Kyk na die laaste twee kolomme van u hele tafel. Die finale kolom moet bevat a en b, die aanvanklike koëffisiënte van die vergelyking. (Indien nie, hersien weer jou somme.) Die voorlaaste kolom sal twee ander nommers bevat. In hierdie voorbeeld is a = 87 en b = 64, die voorste kolom bevat 34 en 25.

8

Let op hoe 87 * 25 - 64 * 34 = -1. Die determinant van die 2x2 matriks in die onderste regs sal altyd 1 positief of negatief wees. As dit negatief is, vermenigvuldig albei kante van die vergelyking met -1 om -87 * 25 + 64 * 34 = 1. Hierdie waarneming is die beginpunt om `n oplossing te bou.

9

Gaan terug na die oorspronklike vergelyking. Herskryf die vorige gelykheid as óf 87 * (- 25) + 64 * (34) = 1 of 87 * (- 25) - 64 * (- 34) = 1, wat die meeste ooreenstem die oorspronklike vergelyking . Vir die voorbeeld is die tweede opsie beter omdat dit ooreenstem met die term en -64 in die oorspronklike wanneer y = -34.

10

Eers nou moet ons bekommerd wees oor die konstante c regs van die vergelyking. Aangesien die vorige vergelyking toon dat ax + by = 1, vermeerder albei kante met c om `n (cx) + b (cy) = c. As (-25, -34) `n oplossing is vir 87x - 64y = 1, dan (-75, -102) is `n oplossing vir 87x-64y = 3

11

As `n Diophantine vergelyking enige oplossing het, dan het dit onbeperkte oplossings. Dit is omdat ax + by = a (x + b) + b (y-a) = a (x + 2b) + b (y-2a), en in die algemeen aanx + by = a (x +kb) + b (yka) vir enige heelgetal k. As gevolg hiervan, as (-75, -102) `n oplossing vir 87 isx-64y = 3, ander oplossings (-11, -15), (53.72), (117.159), ens. Die algemene oplossing kan geskryf word as (53 + 64k, 72 + 87k) gedoen k is enige heelgetal.