Vsebina

• Koraki
• 1. del od 4: Kako napisati enačbo
• 2. del od 4: Kako napisati Euklidov algoritem
• 3. del od 4: Kako najti rešitev z uporabo Euklidovega algoritma
• 4. del 4: Poiščite neskončne druge rešitve

Če želite rešiti linearno diofantinsko enačbo, morate poiskati vrednosti spremenljivk "x" in "y", ki sta cela števila. Celobrojna rešitev je bolj zapletena kot običajno in zahteva poseben nabor dejanj. Najprej morate izračunati največji skupni delitelj (GCD) koeficientov in nato poiskati rešitev. Ko najdete eno celoštevilčno rešitev linearne enačbe, lahko s preprostim vzorcem poiščete neskončno število drugih rešitev.

Koraki

1. del od 4: Kako napisati enačbo

1. 1 Enačbo zapišite v standardni obliki. Linearna enačba je enačba, pri kateri eksponenti spremenljivk ne presegajo 1. Če želite rešiti takšno linearno enačbo, jo najprej zapišite v standardni obliki. Standardna oblika linearne enačbe izgleda tako: ${ displaystyle Axe + By = C}$, kje ${ displaystyle A, B}$ in ${ displaystyle C}$ - cele številke.
   • Če je enačba podana v drugačni obliki, jo z osnovnimi algebarskimi operacijami pripeljite v standardno obliko. Na primer, glede na enačbo ${ displaystyle 23x + 4y -7x = -3y + 15}$... Podajte podobne izraze in enačbo zapišite takole: ${ displaystyle 16x + 7y = 15}$.
2. 2 Poenostavite enačbo (če je mogoče). Ko enačbo napišete v standardni obliki, poglejte koeficiente ${ displaystyle A, B}$ in ${ displaystyle C}$... Če imajo te kvote GCD, z njimi razdelite vse tri kvote. Rešitev tako poenostavljene enačbe bo tudi rešitev prvotne enačbe.
   • Če so na primer vsi trije koeficienti parni, jih delite z najmanj 2. Na primer:
     • ${ displaystyle 42x + 36y = 48}$ (vsi člani so deljivi z 2)
     • ${ displaystyle 21x + 18y = 24}$ (zdaj so vsi člani deljivi s 3)
     • ${ displaystyle 7x + 6y = 8}$ (te enačbe ni več mogoče poenostaviti)
3. 3 Preverite, ali je enačbo mogoče rešiti. V nekaterih primerih lahko takoj trdite, da enačba nima rešitev. Če koeficient "C" ni deljiv z GCD koeficientov "A" in "B", enačba nima rešitev.
   • Na primer, če oba koeficienta ${ displaystyle A}$ in ${ displaystyle B}$ so sodo, potem je koeficient ${ displaystyle C}$ mora biti enakomerno. Ampak če ${ displaystyle C}$ čudno, potem ni rešitve.
     • Enačba ${ displaystyle 2x + 4y = 21}$ ni celobrojnih rešitev.
     • Enačba ${ displaystyle 5x + 10y = 17}$ ni celovitih rešitev, saj je leva stran enačbe deljiva s 5, desna pa ne.

2. del od 4: Kako napisati Euklidov algoritem

1. 1 Razumeti Euclidov algoritem. Gre za niz ponavljajočih se delitev, pri katerih se prejšnji ostanek uporabi kot naslednji delitelj. Zadnji delitelj, ki številke deli celovito, je največji skupni delitelj (GCD) obeh števil.
   • Najdemo na primer GCD številk 272 in 36 z uporabo Euclid -ovega algoritma:
     • ${ displaystyle 272 = 7 * 36 + 20}$ - Večje število (272) delite z manjšim (36) in bodite pozorni na preostanek (20);
     • ${ displaystyle 36 = 1 * 20 + 16}$ - prejšnji delitelj (36) razdelite na prejšnji ostanek (20). Upoštevajte nov ostanek (16);
     • ${ displaystyle 20 = 1 * 16 + 4}$ - prejšnji delitelj (20) razdelite na prejšnji ostanek (16). Upoštevajte nov ostanek (4);
     • ${ displaystyle 16 = 4 * 4 + 0}$ - Prejšnji delilec (16) razdelite na prejšnji ostanek (4). Ker je ostanek 0, lahko rečemo, da je 4 GCD prvotnih dveh števil 272 in 36.
2. 2 Uporabite Euklidov algoritem za koeficiente "A" in "B". Ko linearno enačbo zapišete v standardni obliki, določite koeficienta "A" in "B" in nato uporabite Euclidov algoritem, da poiščete GCD. Na primer, glede na linearno enačbo ${ displaystyle 87x-64y = 3}$.
   • Tu je Euklidov algoritem za koeficiente A = 87 in B = 64:
     • ${ displaystyle 87 = 1 * 64 + 23}$
     • ${ displaystyle 64 = 2 * 23 + 18}$
     • ${ displaystyle 23 = 1 * 18 + 5}$
     • ${ displaystyle 18 = 3 * 5 + 3}$
     • ${ displaystyle 5 = 1 * 3 + 2}$
     • ${ displaystyle 3 = 1 * 2 + 1}$
     • ${ displaystyle 2 = 2 * 1 + 0}$
3. 3 Poiščite največji skupni faktor (GCD). Ker je bil zadnji delitelj 1, sta GCD 87 in 64 1. Tako sta 87 in 64 prosta števila med seboj.
4. 4 Analizirajte rezultat. Ko najdete koeficiente gcd ${ displaystyle A}$ in ${ displaystyle B}$, primerjajte s koeficientom ${ displaystyle C}$ prvotna enačba. Če ${ displaystyle C}$ deljivo z gcd ${ displaystyle A}$ in ${ displaystyle B}$, ima enačba celoštevilčno rešitev; sicer enačba nima rešitev.
   • Na primer enačba ${ displaystyle 87x-64y = 3}$ je mogoče rešiti, ker je 3 deljivo z 1 (gcd = 1).
   • Recimo, da je GCD = 5. 3 ni enakomerno deljivo s 5, zato ta enačba nima celobrojnih rešitev.
   • Kot je prikazano spodaj, če ima enačba eno celoštevilčno rešitev, ima tudi neskončno število drugih celoštevilčnih rešitev.

3. del od 4: Kako najti rešitev z uporabo Euklidovega algoritma

1. 1 Številčite korake za izračun GCD. Če želite poiskati rešitev linearne enačbe, morate kot podlago za postopek zamenjave in poenostavitve uporabiti evklidov algoritem.
   • Začnite z oštevilčenjem korakov za izračun GCD. Postopek izračuna je videti tako:
     • ${ displaystyle { text {1. korak}}: 87 = (1 * 64) +23}$
     • ${ displaystyle { text {2. korak}}: 64 = (2 * 23) +18}$
     • ${ displaystyle { text {3. korak}}: 23 = (1 * 18) +5}$
     • ${ displaystyle { text {4. korak}}: 18 = (3 * 5) +3}$
     • ${ displaystyle { text {5. korak}}: 5 = (1 * 3) +2}$
     • ${ displaystyle { text {Korak 6}}: 3 = (1 * 2) +1}$
     • ${ displaystyle { text {7. korak}: 2 = (2 * 1) +0}$
2. 2 Bodite pozorni na zadnji korak, kjer je preostanek. Za ta korak prepišite enačbo, da izolirate preostanek.
   • V našem primeru je zadnji korak z ostankom 6. korak. Ostanek je 1. Enačbo v 6. koraku prepišite na naslednji način:
     • ${ displaystyle 1 = 3- (1 * 2)}$
3. 3 Preostanek prejšnjega koraka ločite. Ta postopek je korak za korakom "premik navzgor". Vsakič, ko boste v prejšnjem koraku ločili preostanek v enačbi.
   • Preostanek enačbe izolirajte v 5. koraku:
     • ${ displaystyle 2 = 5- (1 * 3)}$ ali ${ displaystyle 2 = 5-3}$
4. 4 Zamenjajte in poenostavite. Upoštevajte, da enačba v 6. koraku vsebuje številko 2, v enačbi v 5. koraku pa je številka 2 ločena. Namesto »2« v enačbi v 6. koraku zamenjajte izraz v 5. koraku:
   • ${ displaystyle 1 = 3-2}$ (enačba koraka 6)
   • ${ displaystyle 1 = 3- (5-3)}$ (namesto 2 je bil nadomeščen izraz)
   • ${ displaystyle 1 = 3-5 + 3}$ (odprti oklepaji)
   • ${ displaystyle 1 = 2 (3) -5}$ (poenostavljeno)
5. 5 Ponovite postopek zamenjave in poenostavitve. Ponovite opisani postopek, premikajte se po evklidskem algoritmu v obratnem vrstnem redu. Vsakič boste enačbo iz prejšnjega koraka prepisali in jo vključili v zadnjo enačbo, ki jo dobite.
   • Zadnji korak, ki smo ga pogledali, je bil korak 5. Torej pojdite na korak 4 in preostanek v enačbi izolirajte za ta korak:
     • ${ displaystyle 3 = 18- (3 * 5)}$
   • Ta izraz v zadnji enačbi nadomesti z "3":
     • ${ displaystyle 1 = 2 (18-3 * 5) -5}$
     • ${ displaystyle 1 = 2 (18) -6 (5) -5}$
     • ${ displaystyle 1 = 2 (18) -7 (5)}$
6. 6 Nadaljujte s postopkom zamenjave in poenostavitve. Ta postopek se bo ponavljal, dokler ne dosežete začetnega koraka evklidskega algoritma. Cilj postopka je zapisati enačbo s koeficientoma 87 in 64 prvotne enačbe, ki jo je treba rešiti. V našem primeru:
   • ${ displaystyle 1 = 2 (18) -7 (5)}$
   • ${ displaystyle 1 = 2 (18) -7 (23-18)}$ (nadomestil izraz iz koraka 3)
     • ${ displaystyle 1 = 2 (18) -7 (23) +7 (18)}$
     • ${ displaystyle 1 = 9 (18) -7 (23)}$
   • ${ displaystyle 1 = 9 (64-2 * 23) -7 (23)}$ (zamenjal izraz iz koraka 2)
     • ${ displaystyle 1 = 9 (64) -18 (23) -7 (23)}$
     • ${ displaystyle 1 = 9 (64) -25 (23)}$
   • ${ displaystyle 1 = 9 (64) -25 (87-64)}$ (zamenjal izraz iz koraka 1)
     • ${ displaystyle 1 = 9 (64) -25 (87) +25 (64)}$
     • ${ displaystyle 1 = 34 (64) -25 (87)}$
7. 7 Nastalo enačbo prepišite v skladu s prvotnimi koeficienti. Ko se vrnete na prvi korak evklidskega algoritma, boste videli, da nastala enačba vsebuje dva koeficienta prvotne enačbe. Enačbo prepišite tako, da se vrstni red njenih členov ujema s koeficienti prvotne enačbe.
   • V našem primeru izvirna enačba ${ displaystyle 87x-64y = 3}$... Zato prepišite nastalo enačbo, tako da se koeficienti uskladijo.Posebno pozornost posvetite koeficientu "64". V prvotni enačbi je ta koeficient negativen, v evklidskem algoritmu pa pozitiven. Zato je treba faktor 34 izločiti. Končna enačba bo zapisana tako:
     • ${ displaystyle 87 (-25) -64 (-34) = 1}$
8. 8 Za rešitev poiščite ustrezen multiplikator. Upoštevajte, da je v našem primeru GCD = 1, zato je končna enačba 1. Toda izvirna enačba (87x-64y) je 3. Zato je treba vse izraze v končni enačbi pomnožiti s 3, da dobimo rešitev:
   • ${ displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}$
   • ${ displaystyle 87 (-75) -64 (-102) = 3}$
9. 9 V enačbo zapišite celoštevilčno rešitev. Številke, pomnožene s koeficienti prvotne enačbe, so rešitve te enačbe.
   • V našem primeru rešitev zapišite kot par koordinat: ${ displaystyle (x, y) = ( - 75, -102)}$.

4. del 4: Poiščite neskončne druge rešitve

1. 1 Razumeti, da obstaja neskončno število rešitev. Če ima linearna enačba eno celoštevilčno rešitev, mora imeti neskončno veliko celoštevilčnih rešitev. Tu je hiter dokaz (v algebrski obliki):
   • ${ displaystyle Axe + By = C}$
   • ${ displaystyle A (x + B) + B (y-A) = C}$ (če "B" dodate "x" in od "y" odštejete "A", se vrednost prvotne enačbe ne bo spremenila)
2. 2 Zapišite izvirne vrednosti x in y. Predloga za izračun naslednjih (neskončnih) rešitev se začne z edino rešitvijo, ki ste jo že našli.
   • V našem primeru je rešitev par koordinat ${ displaystyle (x, y) = ( - 75, -102)}$.
3. 3 Vrednost "x" dodajte faktor "B". Naredite to, da poiščete novo vrednost x.
   • V našem primeru je x = -75 in B = -64:
     • ${ displaystyle x = -75 + ( - 64) = - 139}$
   • Tako je nova vrednost "x": x = -139.
4. 4 Od vrednosti "y" odštejte faktor "A". Da se vrednost prvotne enačbe ne spremeni, morate pri dodajanju ene številke "x" odšteti drugo številko od "y".
   • V našem primeru je y = -102 in A = 87:
     • ${ displaystyle y = -102-87 = -189}$
   • Tako je nova vrednost za "y": y = -189.
   • Novi par koordinat bo zapisan tako: ${ displaystyle (x, y) = ( - 139, -189)}$.
5. 5 Preverite rešitev. Če želite preveriti, ali je nov koordinatni par rešitev prvotne enačbe, vrednosti priključite v enačbo.
   • ${ displaystyle 87x-64y = 3}$
   • ${ displaystyle 87 (-139) -64 (-189) = 3}$
   • ${ displaystyle 3 = 3}$
   • Ker je enakost izpolnjena, je odločitev pravilna.
6. 6 Zapišite številne izraze in poiščite številne rešitve. Vrednosti "x" bodo enake prvotni rešitvi plus kateri koli večkratnik faktorja "B". To lahko zapišemo kot naslednji izraz:
   • x (k) = x + k (B), kjer je "x (k)" niz vrednosti "x" in "x" je prvotna (prva) vrednost "x", ki ste jo našli.
     • V našem primeru:
     • ${ displaystyle x (k) = - 75-64k}$
   • y (k) = y-k (A), kjer je y (k) niz vrednosti y, y pa izvirna (prva) vrednost y, ki ste jo našli.
     • V našem primeru:
     • ${ displaystyle y (k) = - 102-87k}$