Kako riješiti linearnu Diofantovu jednadžbu

Autor: Mark Sanchez
Datum Stvaranja: 5 Siječanj 2021
Datum Ažuriranja: 1 Srpanj 2024
Anonim
Linear Diophantine Equations | Road to RSA Cryptography #3
Video: Linear Diophantine Equations | Road to RSA Cryptography #3

Sadržaj

Da biste riješili linearnu Diofantovu jednadžbu, morate pronaći vrijednosti varijabli "x" i "y", koje su cijeli brojevi. Cjelobrojno rješenje složenije je nego obično i zahtijeva određeni skup radnji. Prvo morate izračunati najveći zajednički djelitelj (GCD) koeficijenata, a zatim pronaći rješenje. Nakon što pronađete jedno cjelobrojno rješenje linearne jednadžbe, pomoću jednostavnog uzorka možete pronaći beskonačan broj drugih rješenja.

Koraci

1. dio od 4: Kako napisati jednadžbu

  1. 1 Zapišite jednadžbu u standardnom obliku. Linearna jednadžba je jednadžba u kojoj eksponenti varijabli ne prelaze 1. Da biste riješili takvu linearnu jednadžbu, najprije je napišite u standardnom obliku. Standardni oblik linearne jednadžbe izgleda ovako: Ax+By=C{ displaystyle sjekira + po = C}, gdje A,B{ displaystyle A, B} i C{ displaystyle C} - cijeli brojevi.
    • Ako je jednadžba dana u drugom obliku, dovedite je u standardni oblik pomoću osnovnih algebarskih operacija. Na primjer, s obzirom na jednadžbu 23x+4y−7x=−3y+15{ displaystyle 23x + 4y -7x = -3y + 15}... Navedite slične izraze i jednačinu napišite ovako: 16x+7y=15{ displaystyle 16x + 7y = 15}.
  2. 2 Pojednostavite jednadžbu (ako je moguće). Kada jednadžbu zapisujete u standardnom obliku, pogledajte koeficijente A,B{ displaystyle A, B} i C{ displaystyle C}... Ako ti izgledi imaju GCD, podijelite sve tri koeficijente s njim. Rješenje takve pojednostavljene jednadžbe bit će i rješenje izvorne jednadžbe.
    • Na primjer, ako su sva tri koeficijenta parna, podijelite ih s najmanje 2. Na primjer:
      • 42x+36y=48{ displaystyle 42x + 36y = 48} (svi članovi su djeljivi s 2)
      • 21x+18y=24{ displaystyle 21x + 18y = 24} (sada su svi članovi djeljivi s 3)
      • 7x+6y=8{ displaystyle 7x + 6y = 8} (ova se jednadžba više ne može pojednostaviti)
  3. 3 Provjerite može li se jednadžba riješiti. U nekim slučajevima možete odmah ustvrditi da jednadžba nema rješenja. Ako koeficijent "C" nije djeljiv s GCD koeficijenata "A" i "B", jednadžba nema rješenja.
    • Na primjer, ako oba koeficijenta A{ displaystyle A} i B{ displaystyle B} su parni, tada je koeficijent C{ displaystyle C} mora biti ujednačeno. Ali ako C{ displaystyle C} čudno, onda nema rješenja.
      • Jednadžba 2x+4y=21{ displaystyle 2x + 4y = 21} nema cjelobrojnih rješenja.
      • Jednadžba 5x+10y=17{ displaystyle 5x + 10y = 17} nema cjelobrojnih rješenja budući da je lijeva strana jednadžbe djeljiva s 5, a desna nije.

Dio 2 od 4: Kako napisati Euklidov algoritam

  1. 1 Razumjeti Euklidov algoritam. To je niz ponovljenih dijeljenja u kojima se prethodni ostatak koristi kao sljedeći djelitelj. Posljednji djelitelj koji dijeli brojeve integralno najveći je zajednički djelitelj (GCD) dva broja.
    • Na primjer, pronađimo GCD brojeva 272 i 36 koristeći Euklidov algoritam:
      • 272=7∗36+20{ displaystyle 272 = 7 * 36 + 20} - Podijelite veći broj (272) s manjim (36) i obratite pozornost na ostatak (20);
      • 36=1∗20+16{ displaystyle 36 = 1 * 20 + 16} - podijelite prethodni djelitelj (36) s prethodnim ostatkom (20). Zabilježite novi ostatak (16);
      • 20=1∗16+4{ displaystyle 20 = 1 * 16 + 4} - podijelite prethodni djelitelj (20) s prethodnim ostatkom (16). Zabilježite novi ostatak (4);
      • 16=4∗4+0{ displaystyle 16 = 4 * 4 + 0} - Podijelite prethodni djelitelj (16) s prethodnim ostatkom (4). Budući da je ostatak 0, možemo reći da je 4 GCD izvorna dva broja 272 i 36.
  2. 2 Primijenite Euklidov algoritam na koeficijente "A" i "B". Kad linearnu jednadžbu napišete u standardnom obliku, odredite koeficijente "A" i "B", a zatim na njih primijenite Euklidov algoritam kako biste pronašli GCD. Na primjer, s obzirom na linearnu jednadžbu 87x−64y=3{ displaystyle 87x-64y = 3}.
    • Evo Euklidovog algoritma za koeficijente A = 87 i B = 64:
      • 87=1∗64+23{ displaystyle 87 = 1 * 64 + 23}
      • 64=2∗23+18{ displaystyle 64 = 2 * 23 + 18}
      • 23=1∗18+5{ displaystyle 23 = 1 * 18 + 5}
      • 18=3∗5+3{ displaystyle 18 = 3 * 5 + 3}
      • 5=1∗3+2{ displaystyle 5 = 1 * 3 + 2}
      • 3=1∗2+1{ displaystyle 3 = 1 * 2 + 1}
      • 2=2∗1+0{ displaystyle 2 = 2 * 1 + 0}
  3. 3 Pronađite najveći zajednički faktor (GCD). Budući da je posljednji djelitelj 1, GCD 87 i 64 su 1. Dakle, 87 i 64 su prosti brojevi međusobno.
  4. 4 Analizirajte rezultat. Kad pronađete gcd koeficijente A{ displaystyle A} i B{ displaystyle B}, usporedite s koeficijentom C{ displaystyle C} izvorna jednadžba. Ako C{ displaystyle C} djeljivo sa gcd A{ displaystyle A} i B{ displaystyle B}, jednadžba ima cjelobrojno rješenje; inače jednadžba nema rješenja.
    • Na primjer, jednadžba 87x−64y=3{ displaystyle 87x-64y = 3} može se riješiti jer je 3 djeljivo s 1 (gcd = 1).
    • Na primjer, pretpostavimo da je GCD = 5. 3 nije ravnomjerno djeljiv sa 5, pa ova jednadžba nema cjelobrojna rješenja.
    • Kao što je dolje prikazano, ako jednadžba ima jedno cjelobrojno rješenje, ona također ima beskonačan broj drugih cjelobrojnih rješenja.

Dio 3 od 4: Kako pronaći rješenje pomoću Euklidova algoritma

  1. 1 Numerirajte korake za izračun GCD -a. Da biste pronašli rješenje linearne jednadžbe, morate koristiti Euklidov algoritam kao osnovu za proces zamjene i pojednostavljenja.
    • Počnite numeriranjem koraka za izračunavanje GCD -a. Postupak izračunavanja izgleda ovako:
      • Korak 1:87=(1∗64)+23{ displaystyle { text {Korak 1}}: 87 = (1 * 64) +23}
      • Korak 2:64=(2∗23)+18{ displaystyle { text {2. korak}}: 64 = (2 * 23) +18}
      • Korak 3:23=(1∗18)+5{ displaystyle { text {Korak 3}}: 23 = (1 * 18) +5}
      • Korak 4:18=(3∗5)+3{ displaystyle { text {Korak 4}}: 18 = (3 * 5) +3}
      • Korak 5:5=(1∗3)+2{ displaystyle { text {Korak 5}}: 5 = (1 * 3) +2}
      • Korak 6:3=(1∗2)+1{ displaystyle { text {Korak 6}}: 3 = (1 * 2) +1}
      • Korak 7:2=(2∗1)+0{ displaystyle { text {7. korak}: 2 = (2 * 1) +0}
  2. 2 Obratite pozornost na posljednji korak, gdje postoji ostatak. Prepišite jednadžbu za ovaj korak kako biste izolirali ostatak.
    • U našem primjeru posljednji korak s ostatkom je korak 6. Ostatak je 1. Prepišite jednadžbu u koraku 6 na sljedeći način:
      • 1=3−(1∗2){ displaystyle 1 = 3- (1 * 2)}
  3. 3 Izolirajte ostatak prethodnog koraka. Ovaj proces je korak po korak "pomicanje prema gore". Svaki put ćete izolirati ostatak u jednadžbi u prethodnom koraku.
    • Ostatak jednadžbe izolirajte u koraku 5:
      • 2=5−(1∗3){ displaystyle 2 = 5- (1 * 3)} ili 2=5−3{ displaystyle 2 = 5-3}
  4. 4 Zamijenite i pojednostavite. Primijetite da jednadžba u koraku 6 sadrži broj 2, a u jednadžbi u koraku 5 broj 2 je izoliran. Dakle, umjesto "2" u jednadžbi u koraku 6, zamijenite izraz u koraku 5:
    • 1=3−2{ displaystyle 1 = 3-2} (jednadžba koraka 6)
    • 1=3−(5−3){ displaystyle 1 = 3- (5-3)} (umjesto 2, izraz je zamijenjen)
    • 1=3−5+3{ displaystyle 1 = 3-5 + 3} (otvorene zagrade)
    • 1=2(3)−5{ displaystyle 1 = 2 (3) -5} (pojednostavljeno)
  5. 5 Ponovite postupak zamjene i pojednostavljenja. Ponovite opisani postupak krećući se kroz euklidski algoritam obrnutim redoslijedom. Svaki put ćete prepisati jednadžbu iz prethodnog koraka i uključiti je u posljednju jednadžbu koju dobijete.
    • Posljednji korak koji smo pogledali bio je korak 5. Pa idite na korak 4 i izolirajte ostatak u jednadžbi za taj korak:
      • 3=18−(3∗5){ displaystyle 3 = 18- (3 * 5)}
    • Zamijenite ovaj izraz za "3" u posljednjoj jednadžbi:
      • 1=2(18−3∗5)−5{ displaystyle 1 = 2 (18-3 * 5) -5}
      • 1=2(18)−6(5)−5{ displaystyle 1 = 2 (18) -6 (5) -5}
      • 1=2(18)−7(5){ displaystyle 1 = 2 (18) -7 (5)}
  6. 6 Nastavite s postupkom zamjene i pojednostavljenja. Ovaj će se postupak ponavljati sve dok ne dosegnete početni korak euklidskog algoritma. Cilj procesa je napisati jednadžbu s koeficijentima 87 i 64 izvorne jednadžbe koju treba riješiti. U našem primjeru:
    • 1=2(18)−7(5){ displaystyle 1 = 2 (18) -7 (5)}
    • 1=2(18)−7(23−18){ displaystyle 1 = 2 (18) -7 (23-18)} (zamijenio izraz iz koraka 3)
      • 1=2(18)−7(23)+7(18){ displaystyle 1 = 2 (18) -7 (23) +7 (18)}
      • 1=9(18)−7(23){ displaystyle 1 = 9 (18) -7 (23)}
    • 1=9(64−2∗23)−7(23){ displaystyle 1 = 9 (64-2 * 23) -7 (23)} (zamijenio izraz iz koraka 2)
      • 1=9(64)−18(23)−7(23){ displaystyle 1 = 9 (64) -18 (23) -7 (23)}
      • 1=9(64)−25(23){ displaystyle 1 = 9 (64) -25 (23)}
    • 1=9(64)−25(87−64){ displaystyle 1 = 9 (64) -25 (87-64)} (zamijenio izraz iz koraka 1)
      • 1=9(64)−25(87)+25(64){ displaystyle 1 = 9 (64) -25 (87) +25 (64)}
      • 1=34(64)−25(87){ displaystyle 1 = 34 (64) -25 (87)}
  7. 7 Prepišite dobivenu jednadžbu u skladu s izvornim koeficijentima. Kad se vratite na prvi korak euklidskog algoritma, vidjet ćete da rezultirajuća jednadžba sadrži dva koeficijenta izvorne jednadžbe. Prepišite jednadžbu tako da redoslijed njezinih članova odgovara koeficijentima izvorne jednadžbe.
    • U našem primjeru izvorna jednadžba 87x−64y=3{ displaystyle 87x-64y = 3}... Stoga prepišite dobivenu jednadžbu tako da se koeficijenti dovedu u red.Posebnu pozornost obratite na koeficijent "64". U izvornoj jednadžbi ovaj je koeficijent negativan, a u euklidskom algoritmu pozitivan. Stoga se faktor 34 mora učiniti negativnim. Konačna jednadžba bit će zapisana ovako:
      • 87(−25)−64(−34)=1{ displaystyle 87 (-25) -64 (-34) = 1}
  8. 8 Primijenite odgovarajući multiplikator da pronađete rješenje. Imajte na umu da je u našem primjeru GCD = 1, pa je konačna jednadžba 1. No izvorna jednadžba (87x-64y) je 3. Stoga se svi izrazi u završnoj jednadžbi moraju pomnožiti s 3 da bi se dobilo rješenje:
    • 87(−25∗3)−64(−34∗3)=1∗3{ displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}
    • 87(−75)−64(−102)=3{ displaystyle 87 (-75) -64 (-102) = 3}
  9. 9 Zapišite cjelobrojno rješenje u jednadžbu. Brojevi koji se množe s koeficijentima izvorne jednadžbe rješenja su te jednadžbe.
    • U našem primjeru rješenje napišite kao par koordinata: (x,y)=(−75,−102){ displaystyle (x, y) = ( - 75, -102)}.

4. dio od 4: Pronađite beskonačna druga rješenja

  1. 1 Shvatite da postoji beskonačan broj rješenja. Ako linearna jednadžba ima jedno cjelobrojno rješenje, onda mora imati beskonačno mnogo cjelobrojnih rješenja. Evo kratkog dokaza (u algebarskom obliku):
    • Ax+By=C{ displaystyle sjekira + po = C}
    • A(x+B)+B(y−A)=C{ displaystyle A (x + B) + B (y-A) = C} (ako dodate "B" u "x" i oduzmete "A" od "y", vrijednost izvorne jednadžbe neće se promijeniti)
  2. 2 Snimite izvorne vrijednosti x i y. Predložak za izračun sljedećih (beskonačnih) rješenja počinje jedinim rješenjem koje ste već pronašli.
    • U našem primjeru rješenje je par koordinata (x,y)=(−75,−102){ displaystyle (x, y) = ( - 75, -102)}.
  3. 3 Vrijednosti "x" dodajte faktor "B". Učinite to kako biste pronašli novu vrijednost x.
    • U našem primjeru x = -75 i B = -64:
      • x=−75+(−64)=−139{ displaystyle x = -75 + ( - 64) = - 139}
    • Dakle, nova vrijednost "x": x = -139.
  4. 4 Oduzmite faktor "A" od vrijednosti "y". Kako se vrijednost izvorne jednadžbe ne promijenila, prilikom dodavanja jednog broja u "x" morate oduzeti drugi broj od "y".
    • U našem primjeru, y = -102, i A = 87:
      • y=−102−87=−189{ displaystyle y = -102-87 = -189}
    • Dakle, nova vrijednost za "y": y = -189.
    • Novi par koordinata bit će napisan ovako: (x,y)=(−139,−189){ displaystyle (x, y) = ( - 139, -189)}.
  5. 5 Provjerite rješenje. Da biste provjerili je li novi par koordinata rješenje izvorne jednadžbe, uključite vrijednosti u jednadžbu.
    • 87x−64y=3{ displaystyle 87x-64y = 3}
    • 87(−139)−64(−189)=3{ displaystyle 87 (-139) -64 (-189) = 3}
    • 3=3{ displaystyle 3 = 3}
    • Budući da je jednakost zadovoljena, odluka je točna.
  6. 6 Zapišite izraze kako biste pronašli mnoga rješenja. Vrijednosti "x" bit će jednake izvornom rješenju plus bilo koji višekratnik "B" faktora. To se može napisati kao sljedeći izraz:
    • x (k) = x + k (B), gdje je “x (k)” skup vrijednosti “x”, a “x” izvorna (prva) vrijednost “x” koju ste pronašli.
      • U našem primjeru:
      • x(k)=−75−64k{ displaystyle x (k) = - 75-64k}
    • y (k) = y-k (A), gdje je y (k) skup vrijednosti y, a y izvorna (prva) vrijednost y koju ste pronašli.
      • U našem primjeru:
      • y(k)=−102−87k{ displaystyle y (k) = - 102-87k}

Članci Portala

Kako steći sposobnost letenja u Pokemon Fire Redu
Kako steći sposobnost letenja u Pokemon Fire Redu
Kako povećati stražnjicu
Kako povećati stražnjicu
Kako uzgajati jalapeno paprike
Kako uzgajati jalapeno paprike
Kako saznati više o tromjesečjima trudnoće
Kako saznati više o tromjesečjima trudnoće