Hur man löser en linjär diophantin ekvation

En diophantin (eller diophantin) ekvation är en algebraisk ekvation vars lösningar söks för vilka variablerna tar på sig hela värden. i allmänna, Diophantinekvationerna är ganska svåra att lösa och det finns olika tillvägagångssätt (Fermats sista teorem är en känd diophantinekvation som har förblev oupplösad i över 350 år).

Men diophantin ekvationer linjär av typen axel + by = c kan lösas enkelt med hjälp av den nedan beskrivna algoritmen. Med hjälp av denna metod hittar vi (4,7) som de enda positiva hela lösningarna i ekvationen 31x + 8y = 180. Uppdelningarna i modulär aritmetik kan också uttryckas som linjära diophant-ekvationer. Till exempel kräver 12/7 (mod 18) lösning 7x = 12 (mod 18) och kan skrivas om som 7x = 12 + 18y eller 7x - 18y = 12. Även om många diophantinekvationer är svåra att lösa, kan du fortfarande prova.

2

ansöka den euklidiska algoritmen till koefficienterna a och b. Detta tjänar av två skäl. Först vill vi ta reda på om a och b har en gemensam divisor. Om vi ​​försöker lösa 4x + 10y = 3 kan vi omedelbart säga att eftersom vänster sida alltid är jämn och höger sida alltid är udda, finns det inga kompletta lösningar för ekvationen. På samma sätt, om vi har 4x + 10y = 2, kan vi förenkla till 2x + 5y = 1. Den andra anledningen ligger i det faktum att, visat att det finns en lösning, kan vi konstruera en från sekvensen av kvotienter erhållna av den euklidiska algoritmen.

3

om till, b och c ha en gemensam divisor, förenklar ekvationen genom att dividera den högra och den vänstra delen av divideraren. om till och b De har en gemensam divisor mellan dem men det här är inte en delare av jämn c, sluta sedan. Det finns inga kompletta lösningar.

4

Konstruera ett treradigt bord som visas på bilden ovan.

5

Skriv i den första raden av tabellen de kvoter som erhållits med den euklidiska algoritmen. Bilden ovan visar vad du skulle få genom att lösa ekvation 87x - 64y = 3.

6

Fyll de två sista raderna från vänster till höger enligt följande procedur: För varje cell beräknar du produkten mellan den första cellen överst på den kolumnen och cellen omedelbart till vänster om den tomma cellen. Skriv den här produkten i den tomma cellen plus värdet av två celler till vänster.

7

Se de två sista kolumnerna i det färdiga tabellen. Den sista kolumnen ska innehålla till och b, ekvationens koefficienter från steg 3 (om inte, kontrollera dina beräkningar igen). Den näst sista kolumnen kommer att innehålla två andra nummer. I exemplet med till = 87 e b = 64, den näst sista kolumnen innehåller 34 och 25.

8

Observera att (87 * 25) - (64 * 34) = -1. Bestämningen av 2x2-matrisen längst ner till höger kommer alltid att vara antingen +1 eller -1. Om det är negativt multiplicerar det båda sidor av jämlikheten med -1 för att få - (87 * 25) + (64 * 34) = 1. Denna observation är utgångspunkten för att bygga en lösning.

9

Återgå till den ursprungliga ekvationen. Skriva om lika det tidigare steget eller i form 87 * (- 25) + 64 * (34) = 1 eller som * 87 (- 25) - 64 * (- 34) = 1, beroende på vilket som är mer besläktad med ursprunglig ekvation. I exemplet är det andra valet att föredra eftersom det uppfyller -64 termeny av den ursprungliga ekvationen när y = -34.

10

Först nu måste vi överväga termen c i den högra delen av ekvationen. Eftersom den tidigare ekvationen visar en lösning för ax + by = 1, multiplicera båda delarna med c erhålla en (cx) + b (cy) = c. Om (-25, -34) är en lösning av 87x - 64y = 1, då (-75, -102) är en lösning av 87x-64y = 3.

11

Om en linjär diophantinekvation har en lösning, har den oändliga lösningar. Detta beror på att ax + by = till (x+b) + b (y-a) = a (x+2b) + b (y-2a), och i allmänhet ax + by = till (x+kb) + b (y-ka) för varje k heltal Därför är sedan (-75, -102) en lösning av 87x-64y = 3, andra lösningar är (-11, -15), (53,72), (117,159) etc. Den allmänna lösningen kan skrivas som (53 + 64k, 72 + 87k) var k Det är ett helt tal.