Diofantoszi egyenletek

Fejezzük ki az egyik változót, például az $y$-t a másik segítségével: $$5y = 14 - 3x \implies y = \frac{14 - 3x}{5}$$ Ahhoz, hogy $y$ egész legyen, a $(14 - 3x)$ kifejezésnek oszthatónak kell lennie 5-tel. Vizsgáljuk modulo 5: $$14 - 3x \equiv 0 \pmod 5$$ $$-3x \equiv -14 \pmod 5 \implies 2x \equiv 1 \pmod 5$$ Szorozzuk be az egyenletet 3-mal: $$6x \equiv 3 \pmod 5 \implies x \equiv 3 \pmod 5$$ Tehát $x = 5k + 3$, ahol $k \in \mathbb{Z}$. Helyettesítsük vissza az $y$-ra kapott képletbe: $$y = \frac{14 - 3(5k + 3)}{5} = \frac{14 - 15k - 9}{5} = \frac{5 - 15k}{5} = 1 - 3k$$ A megoldás tehát minden olyan $(x; y)$ számpár, ahol $x = 5k + 3$ és $y = 1 - 3k$ ($k \in \mathbb{Z}$).

Jelölje $x$ az 50 Ft-os, $y$ a 70 Ft-os bélyegek számát. A feltételek szerint $x \ge 1$, $y \ge 1$ és $x, y \in \mathbb{Z}$. $$50x + 70y = 680$$ Osztva 10-zel a diofantoszi egyenletet: $$5x + 7y = 68$$ Fejezzük ki $x$-et, mivel annak együtthatója kisebb: $$5x = 68 - 7y \implies x = \frac{68 - 7y}{5} = 13 - y + \frac{3 - 2y}{5}$$ Ahhoz, hogy $x$ egész legyen, $(3 - 2y)$-nak oszthatónak kell lennie 5-tel. Kongruenciával: $$2y \equiv 3 \pmod 5 \implies 2y \equiv 8 \pmod 5 \implies y \equiv 4 \pmod 5$$ Tehát $y = 5k + 4$ ($k \in \mathbb{Z}$). Mivel $y \ge 1$, $k$ lehet 0, 1, 2 stb. Ha $k = 0 \implies y = 4$, ekkor $x = \frac{68 - 28}{5} = 8$. Ha $k = 1 \implies y = 9$, ekkor $x = \frac{68 - 63}{5} = 1$. Ha $k = 2 \implies y = 14$, ekkor $x = \frac{68 - 98}{5} < 0$, ami nem lehetséges. Tehát pontosan 2-féleképpen vásárolhatunk (8 db 50-es és 4 db 70-es, vagy 1 db 50-es és 9 db 70-es).

Alakítsuk az egyenletet szorzattá. Ehhez adjunk hozzá egy megfelelő konstanst mindkét oldalhoz: $$x(y - 2) - 3y = 5$$ Ahhoz, hogy ki tudjuk emelni az $(y - 2)$-t, szükségünk van egy $+6$-ra a bal oldalon: $$x(y - 2) - 3(y - 2) - 6 = 5$$ $$x(y - 2) - 3(y - 2) = 11$$ $$(x - 3)(y - 2) = 11$$ Mivel $x, y \in \mathbb{N}$, a tényezők egész számok. A 11 prímszám, osztópárjai: $(1, 11), (11, 1), (-1, -11), (-11, -1)$. Vizsgáljuk az eseteket: 1. $x - 3 = 1 \implies x = 4$, és $y - 2 = 11 \implies y = 13$. Megoldás: $(4; 13)$. 2. $x - 3 = 11 \implies x = 14$, és $y - 2 = 1 \implies y = 3$. Megoldás: $(14; 3)$. 3. $x - 3 = -1 \implies x = 2$, és $y - 2 = -11 \implies y = -9 \notin \mathbb{N}$. 4. $x - 3 = -11 \implies x = -8 \notin \mathbb{N}$. A megoldások a természetes számok halmazán: $(4; 13)$ és $(14; 3)$.

Alkalmazzuk ismét a szorzattá alakítás módszerét: $$x(y + 3) - 4y = 18$$ Vonjunk le 12-t mindkét oldalból, hogy kiemelhető legyen az $(y+3)$: $$x(y + 3) - 4(y + 3) = 18 - 12$$ $$(x - 4)(y + 3) = 6$$ A 6 egész osztópárjai a következők: $(1; 6), (6; 1), (2; 3), (3; 2), (-1; -6), (-6; -1), (-2; -3), (-3; -2)$. Ezekből kapjuk a lehetséges $(x; y)$ párokat az $x=o_1+4$ és $y=o_2-3$ szabály alapján: - $(1, 6) \implies (5; 3)$ - $(6, 1) \implies (10; -2)$ - $(2, 3) \implies (6; 0)$ - $(3, 2) \implies (7; -1)$ - $(-1, -6) \implies (3; -9)$ - $(-6, -1) \implies (-2; -4)$ - $(-2, -3) \implies (2; -6)$ - $(-3, -2) \implies (1; -5)$ Ezzel megkaptuk mind a 8 egész megoldáspárt.

Jelölje $m$ a férfiak, $n$ a nők, $g$ a gyerekek számát ($m, n, g \ge 1$ egész számok). Egyenletrendszer: 1) $m + n + g = 20$ 2) $5000m + 3000n + 1000g = 44000 \implies 5m + 3n + g = 44$ Fejezzük ki $g$-t az elsőből: $g = 20 - m - n$, és helyettesítsük a másodikba: $$5m + 3n + (20 - m - n) = 44$$ $$4m + 2n = 24 \implies 2m + n = 12$$ Fejezzük ki $n$-et: $n = 12 - 2m$. Mivel $n \ge 1$, ezért $12 - 2m \ge 1 \implies 2m \le 11 \implies m \le 5$. Lehetséges $m$ értékek és a megfelelő $n, g$ értékek (ahol $g = 20 - m - n$): - $m = 1 \implies n = 10, g = 9$ - $m = 2 \implies n = 8, g = 10$ - $m = 3 \implies n = 6, g = 11$ - $m = 4 \implies n = 4, g = 12$ - $m = 5 \implies n = 2, g = 13$ Mind az 5 eloszlás érvényes megoldást ad.

Oldjuk meg a kongruenciák módszerével. Vizsgáljuk modulo 17: $$23y \equiv 400 \pmod{17}$$ Mivel $23 \equiv 6 \pmod{17}$ és $400 = 17 \cdot 23 + 9 \implies 400 \equiv 9 \pmod{17}$: $$6y \equiv 9 \pmod{17}$$ Osszuk el 3-mal, mivel a $(3, 17) = 1$: $$2y \equiv 3 \pmod{17}$$ Adjuk hozzá a modulus egy többszörösét (pl. 17-et) a jobb oldalhoz, hogy páros legyen: $$2y \equiv 20 \pmod{17} \implies y \equiv 10 \pmod{17}$$ Tehát $y = 17k + 10$ ($k \in \mathbb{Z}$). Helyettesítsük vissza az eredeti egyenletbe, hogy megkapjuk az $x$-et: $$17x + 23(17k + 10) = 400$$ $$17x + 391k + 230 = 400$$ $$17x = 170 - 391k \implies x = 10 - 23k$$ Az összes egész megoldás: $x = 10 - 23k$ és $y = 10 + 17k$.

A bal oldalon található kifejezés, a $4x - 6y$, felírható szorzat alakban is, ha kiemelünk 2-t: $$2(2x - 3y) = 11$$ Mivel feltételeztük, hogy $x$ és $y$ egész számok, ezért a $(2x - 3y)$ kifejezés is egész szám lesz. Ebből az következik, hogy a bal oldal minden egész $(x; y)$ pár esetén egy páros szám. Ezzel szemben a jobb oldalon álló 11 egy páratlan szám. Mivel páros szám sosem lehet egyenlő páratlan számmal, a $4x - 6y = 11$ egyenletnek nincs megoldása az egész számok halmazán. Képletben kifejezve: $\gcd(4, -6) = 2$, és mivel 2 nem osztója a 11-nek ($2 \nmid 11$), a lineáris diofantoszi egyenlet megoldhatatlan.

Alkalmazzuk a négyzetek különbségének azonosságát: $$(x - y)(x + y) = 15$$ Mivel $x$ és $y$ egész, a két tényező 15 osztópárjaiból kerülhet ki. Ezek a $(1, 15), (3, 5), (15, 1), (5, 3)$, és ezek ellentettjei. Mivel $(x-y)$ és $(x+y)$ azonos paritású kell legyen (hiszen összegük $2x$, ami páros), és 15 minden osztója páratlan, ez a feltétel automatikusan teljesül. 1) $x+y=15, x-y=1 \implies 2x=16 \implies x=8, y=7$. 2) $x+y=5, x-y=3 \implies 2x=8 \implies x=4, y=1$. Mivel az eredeti egyenlet szimmetrikus az előjelekre, a további esetek kiszámítása nélkül is látjuk, hogy a lehetséges megoldások: $(\pm 8, \pm 7)$ és $(\pm 4, \pm 1)$. Ezek összesen 8 db számpárt jelentenek.

Rendezzük át az egyenletet oszthatósági vizsgálathoz: $$8y = 120 - 11x$$ Látjuk, hogy a bal oldal osztható 8-cal. A jobb oldalon a 120 is osztható 8-cal ($120 = 8 \cdot 15$), ami azt jelenti, hogy a $11x$-nek is oszthatónak kell lennie 8-cal. Mivel 11 és 8 relatív prímek, ebből következik, hogy 8 osztója $x$-nek. Legyen $x = 8k$, ahol $k$ pozitív egész. Tudjuk, hogy $y > 0$, így $11x < 120$, tehát $11(8k) < 120 \implies 88k < 120$. Mivel $k$ pozitív egész, a fenti egyenlőtlenség csak $k = 1$ esetén teljesülhet. Ha $k = 1$, akkor $x = 8$. Helyettesítsünk vissza: $$11 \cdot 8 + 8y = 120 \implies 88 + 8y = 120 \implies 8y = 32 \implies y = 4$$ Az egyetlen pozitív egész számpár a $(8; 4)$.

Célunk, hogy a bal oldalt szorzattá alakítsuk. Adjuk hozzá az 1-et mindkét oldalhoz: $$x(y+1) + y + 1 = 11$$ Most már kiemelhető az $(y+1)$ kifejezés: $$(x+1)(y+1) = 11$$ Mivel a 11 prímszám, egész osztópárjai a következők: $(1; 11), (11; 1), (-1; -11), (-11; -1)$. Vizsgáljuk meg az egyes eseteket ($x=o_1-1, y=o_2-1$ alapján): - Ha a pár $(1, 11) \implies x = 0, y = 10$. - Ha a pár $(11, 1) \implies x = 10, y = 0$. - Ha a pár $(-1, -11) \implies x = -2, y = -12$. - Ha a pár $(-11, -1) \implies x = -12, y = -2$. Az összes egész megoldáspár: $(0; 10), (10; 0), (-2; -12), (-12; -2)$.

Legyen $x$ a 80 Ft-os, $y$ a 120 Ft-os füzetek száma, ahol $x, y \in \mathbb{Z}^+$. $$80x + 120y = 1400$$ Osszuk végig 40-nel az egyenletet: $$2x + 3y = 35$$ Fejezzük ki $2x$-et: $2x = 35 - 3y$. A bal oldal páros, így a jobb oldalnak is annak kell lennie. Mivel 35 páratlan, a $3y$-nak is páratlannak kell lennie, tehát az $y$ csak páratlan szám lehet. Mivel $x \ge 1 \implies 2x \ge 2 \implies 35 - 3y \ge 2 \implies 3y \le 33 \implies y \le 11$. Helyettesítsük be a lehetséges páratlan értékeket 1-től 11-ig: - $y = 1 \implies 2x = 32 \implies x = 16$ - $y = 3 \implies 2x = 26 \implies x = 13$ - $y = 5 \implies 2x = 20 \implies x = 10$ - $y = 7 \implies 2x = 14 \implies x = 7$ - $y = 9 \implies 2x = 8 \implies x = 4$ - $y = 11 \implies 2x = 2 \implies x = 1$ Összesen 6-féleképpen vásárolhatott.

A bal oldal szorzattá alakításához érdemes az egyenletet beszorozni 2-vel, hogy a tagokat megfelelően tudjuk csoportosítani: $$4xy + 2x + 2y = 14$$ Kiemelve $2x$-et az első két tagból: $$2x(2y + 1) + 2y = 14$$ Ha hozzáadunk 1-et mindkét oldalhoz, a szorzat összeáll: $$2x(2y + 1) + (2y + 1) = 15$$ $$(2x + 1)(2y + 1) = 15$$ A 15 egész osztópárjait kell megkeresnünk, miközben tudjuk, hogy mindkét tényező páratlan szám (ez minden osztóra teljesül). Osztópárok: $(1, 15), (3, 5), (5, 3), (15, 1)$ és a negatívok. A tényezőkből $(x, y)$ értékek: - $(1, 15) \implies 2x=0, 2y=14 \implies (0, 7)$ - $(3, 5) \implies 2x=2, 2y=4 \implies (1, 2)$ - $(5, 3) \implies (2, 1)$ - $(15, 1) \implies (7, 0)$ - $(-1, -15) \implies 2x=-2, 2y=-16 \implies (-1, -8)$ - $(-3, -5) \implies 2x=-4, 2y=-6 \implies (-2, -3)$ - $(-5, -3) \implies (-3, -2)$ - $(-15, -1) \implies (-8, -1)$ Összesen 8 megoldás van.

A feladat a $3x + 5y = 43$ egyenlet nemnegatív egész megoldásait keresi ($x, y \ge 0$). Vizsgáljuk mod 5: $$3x \equiv 43 \pmod 5 \implies 3x \equiv 3 \pmod 5 \implies x \equiv 1 \pmod 5$$ Tehát $x = 5k + 1$. Fejezzük ki $y$-t is: $$y = \frac{43 - 3x}{5} = \frac{43 - 3(5k+1)}{5} = \frac{40 - 15k}{5} = 8 - 3k$$ Ahhoz, hogy az eredmény nemnegatív legyen, $x \ge 0 \implies k \ge 0$, és $y \ge 0 \implies 8 - 3k \ge 0 \implies k \le 2$. Így $k$ lehetséges értékei 0, 1 és 2. - $k = 0 \implies x = 1, y = 8$ - $k = 1 \implies x = 6, y = 5$ - $k = 2 \implies x = 11, y = 2$ Tehát a teherautón (1 db 3t és 8 db 5t) vagy (6 db 3t és 5 db 5t) vagy (11 db 3t és 2 db 5t) konténer lehet.

Alkalmazzuk a kibővített euklideszi algoritmust. Osszuk el 101-et 37-tel maradékosan, majd folytassuk az osztóval és a maradékkal: $$101 = 2 \cdot 37 + 27 \implies 27 = 101 - 2 \cdot 37$$ $$37 = 1 \cdot 27 + 10 \implies 10 = 37 - 27$$ $$27 = 2 \cdot 10 + 7 \implies 7 = 27 - 2 \cdot 10$$ $$10 = 1 \cdot 7 + 3 \implies 3 = 10 - 7$$ $$7 = 2 \cdot 3 + 1 \implies 1 = 7 - 2 \cdot 3$$ Helyettesítsünk vissza lentről felfelé: $$1 = 7 - 2(10 - 7) = 3 \cdot 7 - 2 \cdot 10$$ $$1 = 3(27 - 2 \cdot 10) - 2 \cdot 10 = 3 \cdot 27 - 8 \cdot 10$$ $$1 = 3 \cdot 27 - 8(37 - 27) = 11 \cdot 27 - 8 \cdot 37$$ $$1 = 11(101 - 2 \cdot 37) - 8 \cdot 37 = 11 \cdot 101 - 30 \cdot 37$$ Ez éppen azt jelenti, hogy $101 \cdot (11) - 37 \cdot (30) = 1$. Egy partikuláris megoldás tehát $x_0 = 11, y_0 = 30$. Az általános megoldás: $x = 11 + 37k, y = 30 + 101k$ ($k \in \mathbb{Z}$).

A bal oldali polinom másodfokú homogén, gyöktényezős alakra bontható. Tekintsük $x$-re nézve másodfokú egyenletként, melynek gyökei $2y$ és $-y$. A szorzat: $(x - 2y)(x + y) = 7$. Mivel a 7 prímszám, egész osztópárjai: $(1, 7), (7, 1), (-1, -7), (-7, -1)$. Oldjuk meg az egyenletrendszereket: 1) $x - 2y = 1$ és $x + y = 7$. Vonjuk ki az elsőt a másodikból: $3y = 6 \implies y = 2 \implies x = 5$. 2) $x - 2y = 7$ és $x + y = 1$. Kivonva: $3y = -6 \implies y = -2 \implies x = 3$. 3) $x - 2y = -1$ és $x + y = -7$. Kivonva: $3y = -6 \implies y = -2 \implies x = -5$. 4) $x - 2y = -7$ és $x + y = -1$. Kivonva: $3y = 6 \implies y = 2 \implies x = -3$. Az összes megoldás: $(5; 2), (3; -2), (-5; -2), (-3; 2)$.

Szorozzuk be az egyenletet a közös nevezővel, $4xy$-nal (tudjuk, hogy $x,y > 0$): $$4y + 4x = xy$$ Rendezzük egy oldalra az összes tagot: $$xy - 4x - 4y = 0$$ Adjuk hozzá 16-ot mindkét oldalhoz a szorzattá alakításhoz: $$x(y - 4) - 4(y - 4) = 16 \implies (x - 4)(y - 4) = 16$$ Mivel $x, y \ge 1 \implies x-4 \ge -3$ és $y-4 \ge -3$. Így csak a 16 pozitív osztópárjait kell vizsgálnunk, hiszen a negatív osztók -4-nél kisebbek lennének, amit a feltétel kizár. Osztópárok $(x-4, y-4)$: - $(1, 16) \implies x = 5, y = 20$ - $(2, 8) \implies x = 6, y = 12$ - $(4, 4) \implies x = 8, y = 8$ - $(8, 2) \implies x = 12, y = 6$ - $(16, 1) \implies x = 20, y = 5$ A megoldások a felsorolt 5 darab pozitív egész számpár.

A törtek eltüntetéséhez szorozzuk be az egyenletet $3xy$-nal: $$3y + 6x = xy \implies xy - 6x - 3y = 0$$ Adjunk a két oldalhoz $18$-at: $$x(y - 6) - 3(y - 6) = 18 \implies (x - 3)(y - 6) = 18$$ Mivel $x, y \ge 1 \implies x-3 \ge -2$ és $y-6 \ge -5$. Vizsgáljuk meg a 18 egész osztópárjait, amelyek megfelelnek ezeknek a határfeltételeknek. Pozitív osztópárok: - $(1, 18) \implies x=4, y=24$ - $(2, 9) \implies x=5, y=15$ - $(3, 6) \implies x=6, y=12$ - $(6, 3) \implies x=9, y=9$ - $(9, 2) \implies x=12, y=8$ - $(18, 1) \implies x=21, y=7$ Negatív osztók esetén, ha $x-3 = -1, y-6 = -18$, ami nem jó. Ha $x-3 = -2, y-6 = -9$, ez sem jó. Az érvényes megoldások száma tehát 6.

Bontsuk fel köbök különbségeként: $$(x - y)(x^2 + xy + y^2) = 19$$ A második tényező $x^2 + xy + y^2 = (x + \frac{y}{2})^2 + \frac{3}{4}y^2 \ge 0$, és csak $x=y=0$ esetén lenne 0. Mivel 19 pozitív, mindkét tényezőnek pozitívnak kell lennie. A 19 prímszám, így az egyetlen érvényes pozitív osztópár az $(1, 19)$, hiszen az első tényező értéke várhatóan sokkal kisebb. Tehát $x - y = 1 \implies x = y + 1$. Helyettesítsük be a második egyenletbe: $$(y+1)^2 + (y+1)y + y^2 = 19$$ $$y^2 + 2y + 1 + y^2 + y + y^2 = 19$$ $$3y^2 + 3y - 18 = 0 \implies y^2 + y - 6 = 0$$ Ez egy másodfokú egyenlet, melyet megoldóképlettel vagy szorzattá alakítással oldunk meg: $$(y + 3)(y - 2) = 0 \implies y_1 = 2, \ y_2 = -3$$ A hozzájuk tartozó $x$ értékek ($x = y+1$): $x_1 = 3$, $x_2 = -2$. Az egész megoldások: $(3; 2)$ és $(-2; -3)$.

Írjuk fel az egyenletet, ahol $p, k, z \ge 1$: $$12p + 15k + 20z = 200$$ Vegyük észre, hogy 15, 20 és 200 oszthatók 5-tel. Ahhoz, hogy az egyenlőség fennálljon, $12p$-nek is oszthatónak kell lennie 5-tel. Mivel $(12, 5) = 1$, ezért $p$-nek 5 többszörösének kell lennie. Lehetséges $p$ értékek: 5, 10, 15 stb. - Ha $p = 5 \implies 60 + 15k + 20z = 200 \implies 15k + 20z = 140 \implies 3k + 4z = 28$. Mivel $3k = 28 - 4z$, és ez nemnegatív, próbáljuk végig $z$-t: $z = 1 \implies 3k = 24 \implies k = 8$. (5 piros, 8 kék, 1 zöld) $z = 4 \implies 3k = 12 \implies k = 4$. (5 piros, 4 kék, 4 zöld) $z = 7 \implies 3k = 0$ (de $k \ge 1$, nem jó). - Ha $p = 10 \implies 120 + 15k + 20z = 200 \implies 15k + 20z = 80 \implies 3k + 4z = 16$. $z = 1 \implies 3k = 12 \implies k = 4$. (10 piros, 4 kék, 1 zöld) $z = 4 \implies 3k = 0$, nem jó. - Ha $p = 15 \implies 180 + 15k + 20z = 200 \implies 15k + 20z = 20 \implies 3k + 4z = 4$. Nincs egész pozitív megoldása. A három lehetséges kombináció: (5, 8, 1), (5, 4, 4) és (10, 4, 1).

Csoportosítsuk a bal oldali tagokat: $$x^2(y - 1) - y = 5$$ Ahhoz, hogy $(y - 1)$ kiemelhető legyen, vonjunk le 1-et és adjunk is hozzá 1-et, vagy egyszerűen adjunk 1-et mindkét oldalhoz (vagy adjunk hozzá -1-et, nézzük meg, melyik a hasznos): A helyes átalakítás: vonjunk ki 1-et, hogy kialakuljon a $-(y-1)$ tag. $$x^2(y - 1) - (y - 1) = 6 \implies (x^2 - 1)(y - 1) = 6$$ Tudjuk, hogy $x \in \mathbb{Z}$, így $x^2 \ge 0$, amiből következik, hogy $x^2 - 1 \ge -1$. Ezért a 6 azon osztóit keressük, amelyek $\ge -1$. Ezek: $-1, 1, 2, 3, 6$. Vizsgáljuk az $x^2 - 1$ lehetséges értékeit: 1) $x^2 - 1 = -1 \implies x^2 = 0 \implies x = 0$. Ekkor $y - 1 = -6 \implies y = -5$. Megoldás: $(0; -5)$. 2) $x^2 - 1 = 1 \implies x^2 = 2$. Nincs egész megoldás. 3) $x^2 - 1 = 2 \implies x^2 = 3$. Nincs egész megoldás. 4) $x^2 - 1 = 3 \implies x^2 = 4 \implies x = \pm 2$. Ekkor $y - 1 = 2 \implies y = 3$. Megoldás: $(2; 3)$ és $(-2; 3)$. 5) $x^2 - 1 = 6 \implies x^2 = 7$. Nincs egész megoldás. Az összes egész számpár: $(0; -5), (2; 3)$ és $(-2; 3)$.