Wko

Hvordan til at løse en lineær diofantisk ligning

En Diophantine ligning er en algebraisk ligning med yderligere begrænsning, at vi kun beskæftiger sig med løsninger, hvor de variable er heltal. I almindelighed er Diophantine ligninger meget vanskelige at løse, og der er mange tilgange. (Fermats sidste sætning er en berømt Diophantine ligning, der sad uopklaret for over 350 år.)

Men lineære Diophantine ligninger af formen a x + b y = c kan løses relativt let af algoritmen beskrevet her. Ved at bruge denne metode, kan vi finde som den eneste løsning i positive heltal til 31 x + 8 y = 180. Division i modulære aritmetik kan også udtrykkes som en lineær Diophantine ligning. For eksempel spørger 12/7 (mod 18) for løsningen på 7 x = 12 (mod 18) og kan omskrives 7 x = 12 + 18 y eller 7 x - 18 y = 12. Mens nogle af de Diophantine ligninger er ekstremt vanskelige at løse, kan du give denne en prøve.

Steps

Hvordan til at løse en lineær diofantisk ligning. Påfør Euklids algoritme til koefficienterne a og b.
Hvordan til at løse en lineær diofantisk ligning. Påfør Euklids algoritme til koefficienterne a og b.
  1. 1
    Hvis det ikke allerede, satte ligningen i form a x + b y = c.
  2. 2
    Påfør Euklids algoritme til koefficienterne a og b. Dette har to formål. Først vil vi gerne vide, om a og b har en fælles faktor. Hvis vi forsøger at løse 4 x + 10 y = 3, kan vi så hurtigt hævde, at da den venstre side er altid selv, og højre side altid mærkeligt, ingen heltal løsninger findes. Tilsvarende, hvis vi havde 4 x + 10 y = 2, kunne vi forenkle problemet til 2 x + 5 y = 1. Den anden grund er, at forudsat en løsning findes, kan vi konstruere en fra sekvensen af ​​tal, der fremkommer fra Euklids algoritme.
  3. 3
    Hvis a, b og c har en fælles faktor, derefter at forenkle ligningen ved at dividere de venstre og højre side af ligningen ved denne faktor. Hvis a og b har en fælles faktor, der ikke deles af c og derefter stoppe. Der er ingen heltal løsninger.
  4. 4
    Byg en tre række bord som vist.
  5. 5
    Befolker den øverste række i tabellen med kvotienter fra Euklids algoritme. Billedet viser, hvordan det ville se ud for at løse 87 x - 64 y = 3.
  6. 6
    Udfylde to nederste rækker fra venstre til højre ved den følgende fremgangsmåde: For hver celle, produktet af den øverste celle i denne kolonne og cellen umiddelbart til venstre for den tomme celle beregne. Fyld den tomme celle med dette produkt plus værdien to celler til venstre.
  7. 7
    Kig på de to sidste kolonner i den færdige tabel. Den endelige kolonne skal indeholde a og b, koefficienterne fra ligningen i trin 3. (Hvis ikke, søges efter dine beregninger.) I næstsidste kolonne vil indeholde to andre numre. I eksemplet med en = 87 og b = 64, næstsidste kolonne indeholder 34 og 25 år.
  8. 8
    Bemærk, at 87 * 25-64 * 34 = -1. Den faktor for 2x2 matrix i nederste højre vil altid være enten plus eller minus 1. Hvis negativ, multipliceres begge sider af identiteten med -1 for at få -87 * 25 + 64 * 34 = 1. Denne observation er udgangspunktet, hvorfra vi kan bygge en løsning.
  9. 9
    Tilbage til den oprindelige ligning. Omskrive identitet i det foregående trin som enten 87 * (-25) + 64 * (34) = 1 eller 87 * (-25) - 64 * (-34) = 1, dog bedst ligner den oprindelige ligning. For eksempel er det andet valg foretrækkes, eftersom den svarer til -64 y sigt i den oprindelige, når y = -34.
  10. 10
    Først nu har vi brug for at se på den konstante sigt c på højre side af ligningen. Siden den forrige ligning demonstrerer en løsning på et x + b y = 1, multiplicere begge sider af c for at få en (c x) + b (c y) = c. Hvis (-25, -34) er en løsning til 87 x - 64 y = 1, da (-75, -102) er en løsning til 87 x -64 y = 3.
  11. 11
    Hvis en lineær diofantisk ligning har nogen løsninger, så det har uendelig mange løsninger. Dette er fordi en x + b y = a (x + b) + b (y-a) = a (x +2 b) + b (y-2a), og generelt en x + b y = a (x + k b) + b (y - k a) for ethvert heltal k.. Derfor da (-75, -102) er en løsning til 87 x -64 y = 3, andre løsninger er (-11, -15), (53,72), (117.159), osv. Den generelle løsning kunne være skrives som (53 +64 k, 72 +87 k), hvor k er et vilkårligt heltal.

Tips

  • Du bør være i stand til at gøre dette med blyant og papir, men når man arbejder med større tal, en lommeregner, eller bedre endnu, kan et regneark være meget nyttig.
  • Tjek dit svar. Identiteten i trin 8 bør fange eventuelle fejl i Euklids algoritme eller udfylde skemaet. Kontrol det endelige svar mod den oprindelige ligning skal fange eventuelle andre fejl.

Ting du behøver

  • Blyant og papir, måske en lommeregner