Wkono

Hvordan løse en lineær Diofantisk ligning

En Diofantisk ligningen er en algebraisk ligning med ytterligere begrensning at vi er kun opptatt av løsninger der variablene er heltall. Generelt, Diofantisk ligningene er meget vanskelig å løse, og det er mange måter. (Fermats siste sats er en berømt Diofantisk ligning som lø uløst i over 350 år.)

Imidlertid Diofantisk lineære ligninger av formen a x + b y = c kan løses relativt enkelt ved algoritmen som er beskrevet her. Ved å bruke denne metoden kan vi finne som den eneste løsningen i positive heltall til 31 x + 8 y = 180. Divisjon i modulær aritmetikk kan også uttrykkes som en lineær Diofantisk ligningen. Eksempelvis spør 12/7 (mod 18) for løsningen til 7 x = 12 (mod 18) og kan bli omskrevet som 7 x = 12 + 18 y eller x 7 - 18 Y = 12. Mens noen av de Diofantisk ligningene er ekstremt vanskelig å løse, kan du gi denne en prøve.

Trinn

Hvordan løse en lineær Diofantisk ligning. Påfør Euklids algoritme til koeffisientene a og b.
Hvordan løse en lineær Diofantisk ligning. Påfør Euklids algoritme til koeffisientene a og b.
  1. 1
    Hvis det ikke allerede, sette ligningen i form en x + b y = c.
  2. 2
    Påfør Euklids algoritme til koeffisientene a og b. Dette har to hensikter. Først ønsker vi å vite om a og b har en felles faktor. Hvis vi prøver å løse 4 x + 10 y = 3, kan vi deretter raskt hevde at siden venstre side er alltid jevnt og høyre side alltid rart, ingen heltallsløsninger eksisterer. Tilsvarende, hvis vi hadde 4 x + 10 y = 2, kan vi forenkle problemet til 2 x + 5 y = 1. Den andre grunnen er at en løsning eksisterer, kan vi konstruere en fra sekvensen av kvotienter hentet fra Euklids algoritme.
  3. 3
    Dersom a, b og c har en felles faktor, og deretter forenkle ligning ved å dele de venstre og høyre side av likningen på at faktor. Hvis a og b har en felles faktor som ikke deles av c, så stopp. Det er ingen heltallsløsninger.
  4. 4
    Bygge en tre rad tabell som vist.
  5. 5
    Befolke den øverste raden i tabellen med quotients fra Euklids algoritme. Bildet viser hvordan dette ville se etter løse 87 x - 64 y = 3.
  6. 6
    Fylle de to nederste radene fra venstre mot høyre ved hjelp av følgende prosedyre: For hver celle, er å beregne et produkt av den øverste celle av denne kolonnen og cellen umiddelbart til venstre for den tomme cellen. Fyll den tomme cellen med det produktet pluss verdien to celler til venstre.
  7. 7
    Se på de to siste kolonnene i den ferdige tabellen. Den siste kolonnen bør inneholde a og b, koeffisientene fra ligningen i trinn 3. (Hvis ikke, kontrolere dine beregninger.) Den nest siste kolonnen vil inneholde to andre tall. I eksempelet med a = 87 og b = 64, den nest siste kolonnen inneholder 34 og 25.
  8. 8
    Legg merke til at 87 * 25-64 * 34 = -1. Den determinant av 2x2 matrise i nedre høyre vil alltid være enten pluss eller minus 1. Hvis negativ, multiplisere begge sider av identitet ved -1 for å få -87 * 25 + 64 * 34 = 1. Denne observasjonen er utgangspunktet som vi kan bygge en løsning.
  9. 9
    Tilbake til den opprinnelige ligningen. Omskrive identitet i forrige trinn som enten 87 * (-25) + 64 * (34) = 1 eller 87 * (-25) - 64 * (-34) = 1, avhengig av hva beste ligner den opprinnelige ligningen. For eksempel er det andre valget foretrukket fordi det samsvarer med -64 y sikt i den opprinnelige når y = -34.
  10. 10
    Først nå trenger vi å se på konstantleddet c på høyre side av ligningen. Ettersom den foregående ligning viser en løsning til en x + b y = 1, multiplisere begge sider av c for å få en (C x) + b (c y) = c. If (-25, -34) er en løsning på 87 x - 64 y = 1, deretter (-75, -102) er en løsning på 87 x -64 y = 3.
  11. 11
    Hvis en lineær Diofantisk ligningen har noen løsninger, da den har uendelig mange løsninger. Dette er fordi en x + b y = et (x + b) + B (y-a) = a (x +2 B) + b (y-2a), og generelt en x + b y = et (x + k b) + b (y - k a) for alle heltall k. Derfor er siden (-75, -102) til en løsning 87 -64 x y = 3, andre løsninger er (-11, -15), (53,72), (117159), etc. Den generelle løsning kan være skrives som (53 64 k, 72 87 k) der k er et heltall.

Tips

  • Du bør være i stand til å gjøre dette med blyant og papir, men når du arbeider med større tall, en kalkulator, eller enda bedre, kan et regneark være svært nyttig.
  • Sjekk svaret. Identiteten i trinn 8 skal fange opp eventuelle feil som er gjort i Euklids algoritme eller å fylle ut tabellen. Kontrollere det endelige svaret mot den opprinnelige ligningen skal fange eventuelle andre feil.

Ting du trenger

  • Blyant og papir, kanskje en kalkulator