Een Diophantine vergelijking een algebraïsche vergelijking met de extra beperking dat we enkel gaat oplossingen waarin de variabelen gehele getallen. In het algemeen diophantische vergelijkingen zijn zeer moeilijk op te lossen en er zijn vele benaderingen. (Laatste Stelling van Fermat is een beroemde Diophantische vergelijking die zat onopgelost meer dan 350 jaar.)
Echter, lineaire diophantische vergelijkingen van de vorm a x + y = b c kunnen relatief eenvoudig worden opgelost door de hier beschreven algoritme. Door het gebruik van deze methode, kunnen we vinden als de enige oplossing in positieve gehele getallen tot 31 x 8 + y = 180. Divisie in modulaire rekenkunde kunnen ook worden uitgedrukt als een lineaire Diophantine vergelijking. Bijvoorbeeld, 12/7 (mod 18) verzoekt de oplossing 7 x = 12 (mod 18) en kan worden herschreven als x 7 = 12 + y 18 of 7 x - 18 y = 12. Hoewel sommige van de diophantische vergelijkingen zijn zeer moeilijk op te lossen, kunt u deze een keer te proberen.
Stappen
- 1Als dit nog niet is, zet de vergelijking in de vorm van een x + b y = c.
- 2Solliciteer Euclides algoritme om de coëfficiënten a en b. Dit heeft twee doelen. Ten eerste willen we weten of a en b hebben een gemeenschappelijke factor. Als we proberen op te lossen 4 x + 10 y = 3, dan kunnen we snel beweren dat sinds de linkerkant is altijd nog en de rechterzijde altijd oneven, geen integer oplossingen bestaan. Evenzo, als we hadden 4 x + 10 y = 2, we konden het probleem te vereenvoudigen tot 2 x + 5 y = 1. De tweede reden is dat een oplossing bestaat, kunnen we construeren een uit de reeks waarden die worden verkregen door het algoritme van Euclides.
- 3Als a, b en c een gemeenschappelijke factor, vereenvoudig dan de vergelijking door het linker-en rechterkant van de vergelijking met die factor. Indien a en b hebben een gemeenschappelijke factor gedeeld door c, dan stoppen. Er zijn geen gehele oplossingen.
- 4Bouw een drie rij-tabel zoals weergegeven.
- 5Bevolken de bovenste rij van de tabel met de waarden van het algoritme van Euclides. De afbeelding laat zien hoe deze eruit zou zien voor het oplossen van 87 x - 64 y = 3.
- 6Vullen van de onderste twee rijen van links naar rechts door de volgende procedure: Voor elke cel, berekent het product van de bovenste cel van die kolom en de cel direct links van de lege cel. Vul de lege cel met dat produkt en de waarde twee cellen naar links.
- 7Kijk naar de laatste twee kolommen van de tabel afgerond. De laatste kolom a en b, de coëfficiënten van de vergelijking in stap 3 bevatten. (Indien niet, controleer je berekeningen.) De een na laatste kolom zullen twee andere nummers bevatten. In het voorbeeld met a = 87 en b = 64, de voorlaatste kolom 34 en 25.
- 8Merk op dat 87 * 25-64 * 34 = -1. De determinant van de 2x2 matrix rechtsonder altijd ofwel plus of min 1. Indien negatief, vermenigvuldig beide zijden van de identiteit van -1 tot -87 krijgen * 25 + 64 * 34 = 1. Deze waarneming is het uitgangspunt van waaruit we kunnen een oplossing te bouwen.
- 9Terugkeren naar de oorspronkelijke vergelijking. Herschrijven van de identiteit in de vorige stap als ofwel 87 * (-25) + 64 * (34) = 1 en 87 * (-25) - 64 * (-34) = 1, indien best lijkt de oorspronkelijke vergelijking. In het voorbeeld wordt de tweede keuze voorkeur omdat het overeenkomt -64 y term in het origineel wanneer y = -34.
- 10Alleen nu moeten we kijken naar de constante term c op de rechterzijde van de vergelijking. Aangezien de vorige vergelijking toont een oplossing voor een x + y = 1 b, c beide zijden vermenigvuldigen om een (c x) + b (c y) = c. If (-25, -34) is een oplossing tot 87 x - 64 y = 1, dan (-75, -102) is een oplossing tot 87 -64 x y = 3.
- 11Indien een lineaire diophantische vergelijking heeft geen oplossingen, dan heeft oneindig veel oplossingen. Dit komt omdat een x + y = b a (x + b) + b (y-a) = a (x +2 b) + b (y-2a), en in het algemeen a x b + y = a (x + k b) + b (y - k a) voor elk geheel getal k. Aangezien (-75, -102) is een oplossing tot 87 -64 x y = 3, andere oplossingen (-11, -15), (53,72), (117.159), etc. De algemene oplossing kan geschreven als (53 +64 k, 72 +87 k), waarbij k een geheel getal.
Tips
- Je moet in staat zijn om dit te doen met potlood en papier, maar bij het werken met grotere aantallen, een rekenmachine, of beter nog, kan een spreadsheet zeer nuttig zijn.
- Controleer je antwoord. De identiteit in stap 8 moeten eventuele fouten in het algoritme van Euclides of bij het invullen van de tabel te vangen. Controle van het definitieve antwoord tegen de oorspronkelijke vergelijking mag geen andere fouten te vangen.
Dingen die je nodig hebt
- Potlood en papier, misschien een rekenmachine