Ezt a cikket népszerűsítették a Menéame oldalon. Ha tetszett és szeretnél rá szavazni, lépj ide és említsd meg.
Motiváció
Tegyük fel, hogy a következő problémába ütközünk:
Egy férfi egy ruhaüzletbe megy, és 12 öltönyt vásárol, némelyik fekete és szürke, 1200 euróért. Ha a fekete öltönyök 30 euróval többet érnek, mint a szürke, és az utóbbiból minél kevesebbet vásárolt, akkor hány színt vásárolt az egyes színekből?
Emeljük fel:
Az egyenlet:
A matematika elvégzése a következő:
Ha arra gondoltál, hogy egyszerű egyenletrendszert kell megoldanunk, akkor tévedsz. Egyetlen egyenletünk maradt két ismeretlenrel. Hiányoznak az adatok? Nem. Meg tudjuk oldani. Üdvözöljük a Diophantine egyenletek.
Diophantine egyenletek
A diofantin-egyenlet olyan algebrai egyenlet, amelyben több olyan változó jelenik meg, amelyek megoldása egész szám. Vagyis a Diophantine egyenlet megoldása abból áll, hogy meghatározzuk, mely egész számok elégítik ki. Nevét a matematikustól veszik Alexandriai Diophantus, aki amellett, hogy az elsők között használta a szimbolizmust az algebrában, többek között ezen egyenletek tanulmányozásának szentelte magát
A fenti típusú diofantin-egyenleteket Diophantine-egyenleteknek nevezzük lineáris. Az ilyen típusú egyenletek ezen konkrét esete az, amelyet meg fogunk tanulni megoldani ebben a cikkben. Pontosabban bemutatunk (és bemutatunk) egy módszert az egyenlet egész megoldásának kiszámítására
Megoldások megléte
Az első eredmény, amelyet meg fogunk nézni és bemutatni fogunk, összefügg ezeknek az egyenleteknek a megoldásával. Menjünk vele:
Tétel:
A forma diofantin lineáris egyenletének akkor és csak akkor van egész megoldása, ha y legnagyobb közös osztója az .
Továbbá, ha hívjuk, akkor megvan, hogy az említett egyenlet egy adott megoldása a következőképpen érhető el:
lény .
1.- Balról jobbra következtetéssel kezdjük:
van egész számú megoldása, akkor vannak olyanok, hogy
Ahogy y közös osztója, akkor y, -vel .
Ezután a következők állnak rendelkezésünkre:
Vagyis van egy típusú kifejezésünk, egész számokkal. Következésképpen annyit kell osztaniuk a-val, hogy ezzel a bizonyításnak ezt a részét lezárják.
2.- Most megyünk a következményekkel jobbról balra, bónuszként nyerjük a kiegészítést:
Tegyük fel, hogy most osztója. Akkor létezik olyan, hogy. Bezout Bezout tétele szerint viszont vannak olyanok. Ennek az egyenlőségnek a két tagját megszorozzuk:
Hová jutunk
Azzal, amit elértünk, és megoldások az (1) egyenletre.
az (1) egyenlet megoldása, amit meg akartunk mutatni.
Amit eddig elértünk, az az, hogy tudjuk-e felismerni, hogy mely lineáris diofantinegyenletek rendelkeznek megoldásokkal, és kiszámolhatunk egy adott megoldást ezekre. De általános megoldást akarunk, vagyis a lineáris diofantinegyenletek minden megoldható megoldását. Erre a következő pontban térünk ki.
Lineáris diofantikus egyenlet általános megoldása
A következő tételt fogjuk bizonyítani:
Tétel:
Ha ez az egyenlet adott megoldása
(1)
akkor az összes egész megoldása a következő:
(két)
a léttel .
Ha az (1) egyenlet megoldása, akkor igaz. De ekkor a (2) kifejezései is megoldják ezt az egyenletet:
Ekkor látni kell, hogy az (1) bekezdés összes megoldása a (2) bekezdésben leírtak szerint. Gyerünk:
Az előző megoldásból kiindulva tegyük fel, hogy megvan a (1) lineáris diofantin-egyenlet megoldása. Ezután a következő két egyenletünk van:
Kivonjuk a két egyenletet, megkapjuk
A második lépés átadása az egyenlőség másik tagjának hozzáadásával
Most osztjuk:
Mivel relatív elsődleges számok és ezek relatív egész számok (mivel a legnagyobb közös osztójukkal elosztva eltávolítottuk azokat a tényezőket, amelyek eleinte közösek voltak), és elosztjuk a-t, igaznak kell lennie, hogy .
Ez arra a tényre vezet minket, hogy annak léteznie kell, hogy:
Honnan tudjuk, hogy ennek formájúnak kell lennie:
A (3) egyenlet ezen értékének helyettesítésével néhány egyszerű számítás után elérjük a keresett kifejezést:
Gyakorlati példa
Térjünk vissza öltönyös barátunkhoz. A következő lineáris diofantikus egyenlet maradt számunkra:
Lássuk, meg tudjuk-e találni, hogy az ember hány színű színt vásárolt minden színből.
Mivel egyenletünk osztója, ezért vannak megoldásai. Az Euclid algoritmusának megszerzéséhez és ezt kell használnunk a legnagyobb közös osztó kiszámításához a fent említett Bezout azonossággal együtt. Ebben az esetben megkapja
Ekkor az adott megoldás a következő:
Ebből könnyű megtalálni az összes megoldást:
Elvileg ezek a kifejezések minden megoldást megadnak a problémára, de még nem vagyunk készen. Több dolgot is figyelembe kell venni. A kapott adatokat elemezve tudjuk, hogy a vásárolt fekete öltönyök száma, tehát a vásárolt szürke öltönyök száma .
Figyelembe véve, hogy a barátunk által megvásárolt ruhák számának pozitívnak kell lennie, és kevesebbnek kell lennie, mint 12, a következőket kapjuk:
Ezért az egyetlen lehetséges értéke a .
De a nyilatkozat azt is elmondta, hogy a lehető legkevesebb szürke öltönyt vásárolta meg. Az előző értékekkel tesztelve ez a feltétel teljesül. Következésképpen problémánk főszereplője szürke és fekete öltönyt vásárolt.
Bemutató forrása:
- Algebra és diszkrét matematika I., szerző: Carmen Moreno Valencia.