[subject]/[topic]

Diszkrét matematikakimaradt

Lineáris diofantikus egyenletek

Az ax + by = c egyenlet egész megoldásai. Mikor van megoldás, hogyan találunk egyet a kiterjesztett euklideszi algoritmussal, és hogyan írjuk fel az összeset.

Forrás: DiMat_ea.pdf 28. dia · Feladatsor 3.22–3.24

Mi a kérdés?

Példa · 3.23: Gombóc Artúr

Gombóc Artúrnak 1420 Ft-ja van, és mindet csokoládéra akarja költeni. A lyukas csoki 35 Ft, a kerek 40 Ft. Hány darabot vehet az egyesekből?

Ha xx lyukasat és yy kereket vesz: 35x+40y=142035x + 40y = 1420. Ennek egész (sőt nemnegatív) megoldásai kellenek. Tört csokit nem lehet venni.

Definíció

Az ax+by=cax + by = c alakú egyenlet, ahol a,b,c∈ℤa, b, c \in \Z adottak és x,y∈ℤx, y \in \Z ismeretlenek, lineáris diofantikus egyenlet.

Mikor van megoldás?

Tétel

Az ax+by=cax + by = c egyenlet pontosan akkor oldható meg, ha (a,b)∣c(a, b) \mid c.

Az egyik irány könnyű: ha d=(a,b)d = (a, b), akkor d∣ad \mid a és d∣bd \mid b, tehát d∣ax+byd \mid ax + by bármilyen egész x,yx, y-ra. Így ha d∤cd \nmid c, nincs megoldás.

Példa · 3.22 (c)

12x−15y=2612x - 15y = 26: (12,15)=3(12, 15) = 3, de 3∤263 \nmid 26. Nincs megoldás. (A bal oldal mindig osztható 3-mal, a jobb nem.)

Egy megoldás: visszafelé az euklideszi algoritmuson

Az euklideszi algoritmus lépéseit visszafelé olvasva a legnagyobb közös osztót előállíthatjuk aa és bb kombinációjaként: d=as+btd = a s + b t (ez a Bézout-azonosság). Ha ezt megszorozzuk c/dc/d-vel, kész az egyenlet egy megoldása.

Példa · az előadásból: 147x + 69y = 3

Az algoritmus:

147=69⋅2+969=9⋅7+69=6⋅1+36=3⋅2+0\begin{aligned} 147 &= 69 \cdot 2 + 9 \\ 69 &= 9 \cdot 7 + 6 \\ 9 &= 6 \cdot 1 + 3 \\ 6 &= 3 \cdot 2 + 0 \end{aligned}

(147,69)=3∣3(147, 69) = 3 \mid 3, tehát van megoldás. Visszafelé, mindig a legutóbbi maradékot helyettesítve:

3=9−6⋅1=9−(69−9⋅7)=8⋅9−69=8 (147−69⋅2)−69=8⋅147−17⋅69.\begin{aligned} 3 &= 9 - 6 \cdot 1 \\ &= 9 - (69 - 9 \cdot 7) = 8 \cdot 9 - 69 \\ &= 8\,(147 - 69 \cdot 2) - 69 = 8 \cdot 147 - 17 \cdot 69. \end{aligned}

Tehát x0=8x_0 = 8, y0=−17y_0 = -17. Ellenőrzés: 1176−1173=31176 - 1173 = 3. ✓

Az összes megoldás

Tétel

Ha (x0,y0)(x_0, y_0) egy megoldás, akkor az összes megoldás

x=x0+t⋅b(a,b),y=y0−t⋅a(a,b),t∈ℤ.x = x_0 + t \cdot \frac{b}{(a, b)}, \qquad y = y_0 - t \cdot \frac{a}{(a, b)}, \qquad t \in \Z.

Miért? Ha xx-et bd\frac{b}{d}-vel növeljük, az axax tag abd\frac{ab}{d}-vel nő. Ha közben yy-t ad\frac{a}{d}-vel csökkentjük, a byby tag ugyanennyivel csökken, így az összeg nem változik.

Példa

147x+69y=3147x + 69y = 3 összes megoldása: x=8+23tx = 8 + 23t, y=−17−49ty = -17 - 49t. Például t=1t = 1-re (31,−66)(31, -66): 147⋅31−69⋅66=4557−4554=3147 \cdot 31 - 69 \cdot 66 = 4557 - 4554 = 3. ✓

Egyszerűsítés a lnko-val

Ha (a,b)=d∣c(a, b) = d \mid c, érdemes rögtön elosztani mindent dd-vel. Kisebb számokkal könnyebb dolgozni.

Példa · az előadásból: 140x + 322y = 98

(140,322)=14(140, 322) = 14 és 14∣9814 \mid 98, tehát osztható. Osztva: 10x+23y=710x + 23y = 7.

23=10⋅2+323 = 10 \cdot 2 + 3, 10=3⋅3+110 = 3 \cdot 3 + 1, így 1=10−3⋅3=10−3 (23−10⋅2)=7⋅10−3⋅231 = 10 - 3 \cdot 3 = 10 - 3\,(23 - 10 \cdot 2) = 7 \cdot 10 - 3 \cdot 23.

Szorozva 7-tel: 49⋅10−21⋅23=749 \cdot 10 - 21 \cdot 23 = 7, tehát x0=49x_0 = 49, y0=−21y_0 = -21. Az összes megoldás: x=49+23tx = 49 + 23t, y=−21−10ty = -21 - 10t. A legkisebb nemnegatív xx-hez (t=−2t = -2): x=3x = 3, y=−1y = -1. Ellenőrzés: 140⋅3−322=98140 \cdot 3 - 322 = 98. ✓

Szöveges feladat: nemnegatív megoldások

Példa · 3.23 megoldása

35x+40y=142035x + 40y = 1420, osztva 5-tel: 7x+8y=2847x + 8y = 284.

8=7⋅1+18 = 7 \cdot 1 + 1, tehát 1=8−71 = 8 - 7, vagyis 7⋅(−1)+8⋅1=17 \cdot (-1) + 8 \cdot 1 = 1. Szorozva 284-gyel: x0=−284x_0 = -284, y0=284y_0 = 284.

Az összes megoldás: x=−284+8tx = -284 + 8t, y=284−7ty = 284 - 7t. A csokik száma nem lehet negatív:

  • x≥0  ⟺  t≥35,5x \ge 0 \iff t \ge 35{,}5, tehát t≥36t \ge 36;
  • y≥0  ⟺  t≤40,57y \ge 0 \iff t \le 40{,}57, tehát t≤40t \le 40.

Öt lehetőség van: (x,y)=(4,32),(12,25),(20,18),(28,11),(36,4)(x, y) = (4, 32), (12, 25), (20, 18), (28, 11), (36, 4). Ellenőrzés: 35⋅4+40⋅32=140+1280=142035 \cdot 4 + 40 \cdot 32 = 140 + 1280 = 1420. ✓

Próbáld ki

Kapcsold be a cc-t, és a megoldó lépésről lépésre megmutatja az algoritmust, a Bézout-együtthatókat és az általános megoldást. Pozitív együtthatóknál a nemnegatív megoldásokat is kilistázza.

Interaktív

Euklideszi algoritmus

Írd át a számokat. Ha bekapcsolod a c-t, az ax + by = c diofantikus egyenletet is megoldja.

lépésmaradékos osztás
135 = 40 · 0 + 35
240 = 35 · 1 + 5
335 = 5 · 7 + 0
(a, b)
5 (az utolsó nem nulla maradék)
[a, b]
280
Bézout
35·(−1) + 40·1 = 5

megoldható mert 5 | 1420. A Bézout-azonosságot szorozzuk 1420/5 = 284-mal:

x₀ = −284, y₀ = 284

A legkisebb nemnegatív x-szel: x = 4, y = 32 (próba: 35·4 + 40·32 = 1420)

Az összes megoldás:

x = 4 + 8t,   y = 32 − 7t,   t ∈ ℤ

Nemnegatív megoldások (szöveges feladatokhoz): (4, 32), (12, 25), (20, 18), (28, 11), (36, 4)

Gyakorló feladatok

Gyakorló feladat · 3.22 (a)

Oldd meg: 14x−18y=614x - 18y = 6.

Megoldás

(14,18)=2∣6(14, 18) = 2 \mid 6, osztva: 7x−9y=37x - 9y = 3. Keressünk olyan xx-et, amire 7x−37x - 3 osztható 9-cel: x=3x = 3 esetén 21−3=18=9⋅221 - 3 = 18 = 9 \cdot 2, tehát y=2y = 2. Az összes megoldás: x=3+9tx = 3 + 9t, y=2+7ty = 2 + 7t. (Itt b=−18b = -18, így b/d=−9b/d = -9; a t→−tt \to -t csere miatt a két alak ugyanaz.) Ellenőrzés: 42−36=642 - 36 = 6. ✓

Gyakorló feladat · 3.22 (f)

Oldd meg: 18x+28y=1018x + 28y = 10.

Megoldás

(18,28)=2∣10(18, 28) = 2 \mid 10, osztva: 9x+14y=59x + 14y = 5. Euklidesz: 14=9⋅1+514 = 9 \cdot 1 + 5, 9=5⋅1+49 = 5 \cdot 1 + 4, 5=4⋅1+15 = 4 \cdot 1 + 1. Visszafelé: 1=5−4=5−(9−5)=2⋅5−9=2 (14−9)−9=2⋅14−3⋅91 = 5 - 4 = 5 - (9 - 5) = 2 \cdot 5 - 9 = 2\,(14 - 9) - 9 = 2 \cdot 14 - 3 \cdot 9. Szorozva 5-tel: x0=−15x_0 = -15, y0=10y_0 = 10. Összes: x=−15+14tx = -15 + 14t, y=10−9ty = 10 - 9t; például t=2t = 2: (13,−8)(13, -8), és 18⋅13−28⋅8=234−224=1018 \cdot 13 - 28 \cdot 8 = 234 - 224 = 10. ✓