En Diofantisk ekvation är en algebraisk ekvation med den ytterligare begränsningen att vi bara sysslar med lösningar där variablerna är heltal. I allmänhet Diophantine ekvationer är mycket svåra att lösa och det finns många metoder. (Fermats stora sats är en berömd Diofantisk ekvation som satt olöst i över 350 år.)
Emellertid linjära Diophantine ekvationer av formen a x + b y = c kan lösas relativt enkelt genom att den algoritm som beskrivs här. Genom att använda denna metod, kan vi hitta som den enda lösningen i positiva heltal till 31 x + 8 y = 180. Division i modulär aritmetik kan också uttryckas som en linjär Diofantisk ekvation. Till exempel frågar 12/7 (mod 18) för lösningen till 7 x = 12 (mod 18) och kan skrivas om som 7 x = 12 + 18 år eller 7 x - 18 y = 12. Medan vissa av de diofantiska ekvationerna är extremt svåra att lösa, kan du ge det ett försök.
Steg
- 1Om det inte redan, lägg ekvationen i formen a x + b y = c.
- 2Applicera Euklides algoritm för koefficienterna a och b. Detta har två syften. Först vill vi veta om A och B har en gemensam faktor. Om vi försöker att lösa 4 x + 10 y = 3, kan vi sedan snabbt hävda att eftersom den vänstra sidan är alltid jämn och den högra sidan alltid udda, inga heltal lösningar finns. Likaså om vi hade 4 x + 10 y = 2, kan vi förenkla problemet till 2 x + 5 y = 1. Det andra skälet är att, förutsatt en lösning existerar, kan vi konstruera en från sekvensen av kvoter erhållna från Euklides algoritm.
- 3Om a, b och c har en gemensam faktor, förenkla sedan ekvationen genom att dividera de vänstra och högra sidorna av ekvationen med denna faktor. Om a och b har en gemensam faktor som inte delas av c, sedan stopp. Det finns inga heltal lösningar.
- 4Bygg en tre rad bord som visas.
- 5Fylla den översta raden i tabellen med de kvoter från Euklides algoritm. Bilden visar hur det skulle se ut för att lösa 87 x - 64 y = 3.
- 6Fylla de nedre två rader från vänster till höger enligt följande förfarande: För varje cell, beräkna produkten av den översta cellen i den kolumnen och cellen omedelbart till vänster om den tomma cellen. Fyll den tomma cellen med den produkten plus värdet två celler till vänster.
- 7Titta på de två sista kolumnerna i den färdiga tabellen. Den sista kolumnen ska innehålla a och b är koefficienterna från ekvationen i steg 3. (Om inte, kontrollera dina beräkningar.) Den näst sista kolumnen kommer att innehålla två andra siffror. I exemplet med en = 87 och b = 64, den näst sista kolumnen innehåller 34 och 25.
- 8Lägg märke till att 87 * 25-64 * 34 = -1. Determinanten av 2x2 matrisen i det nedre högra kommer alltid att vara antingen plus eller minus 1. Om negativ, multiplicera båda sidor av identiteten med -1 för att få -87 * 25 + 64 * 34 = 1. Denna observation är utgångspunkten från vilken vi kan bygga en lösning.
- 9Återgå till den ursprungliga ekvationen. Skriv om identitet i föregående steg som antingen 87 * (-25) + 64 * (34) = 1 eller 87 * (-25) - 64 * (-34) = 1, vilket som bäst liknar den ursprungliga ekvationen. För exempel, är det andra valet föredra eftersom det matchar -64 y term i original när y = -34.
- 10Först nu behöver vi titta på den konstanta termen c på den högra sidan av ekvationen. Sedan föregående ekvationen visar en lösning på ett x + b y = 1, multiplicera båda sidor av c för att få en (c x) + b (c y) = c. Om (-25, -34) är en lösning på 87 x - 64 y = 1, sedan (-75, -102) är en lösning på 87 x -64 y = 3.
- 11Om en linjär Diofantisk ekvation har några lösningar, då det finns oändligt många lösningar. Detta beror på en x + b y = a (x + b) + b (y-a) = a (x 2 b) + b (y-2a), och generellt sett en x + b y = a (x + k b) + b (y - k a) för något heltal k.. Därför är sedan (-75, -102) en lösning på 87 x -64 y = 3, andra lösningar (-11, -15), (53,72), (117.159), etc. Den allmänna lösningen kan vara skrivs som (53 +64 k, 72 +87 k), där k är ett heltal.
Tips
- Du bör kunna göra detta med penna och papper, men när man arbetar med större siffror, en miniräknare, eller ännu bättre, kan ett kalkylblad vara till stor hjälp.
- Kontrollera ditt svar. Identiteten i steg 8 bör fånga eventuella felaktigheter i Euklides algoritm eller fylla i tabellen. Kontrollera det slutliga svaret mot den ursprungliga ekvationen ska fånga några andra fel.
Saker du behöver
- Penna och papper, kanske en miniräknare