Fölérendelt lap:21.2. TételLineáris diofantoszi egyenlet összes megoldása

Bizonyítás

Az általánosság megsértése nélkül feltehetjük, hogy az $m\neq 0$ feltétel teljesül. Ha ugyanis mégsem így lenne, akkor a tétel szövege alapján szükségképpen teljesül az $a\neq 0$ feltétel, és az alábbi gondolatmenet az $a$ és $m$ együtthatók szerepének felcserélésével ugyanígy végigjátszható. Először az $m\gt 0$ esetet igazoljuk.

Az 1. állítás az $m\gt 0$ esetben: Mivel az egyenlet megoldható, ezért a 20.13. Tétel alapján teljesül az $(a,m)|b$ oszthatóság. Vagyis létezik olyan egész szám, amellyel az $(a,m)$ kitüntetett közös osztót megszorozva $b$ -t kapunk. Jelöljük ezt az egész számot $\frac{b}{(a,m)}$ -mel, azaz:

(a,m)\cdot \frac{b}{(a,m)} = b

A 21.1. Tétel alapján az $(a,m)$ kitüntetett közös osztó felírható az $a$ és $m$ egész számok lineáris kombinációjaként. Azaz léteznek olyan $u$ és $v$ egész számok, hogy teljesül az alábbi:

(a,m)=au+mv

Ezt összevetve az előző egyenlettel:

(\underbrace{au+mv}_{=(a,m)})\cdot \frac{b}{(a,m)} = a\cdot (\underbrace{u\cdot \frac{b}{(a,m)}}_{=x}) + m\cdot (\underbrace{v\cdot \frac{b}{(a,m)}}_{=y}) = b

Azaz lényegében megkaptuk az $ax+my=b$ lineáris diofantoszi egyenlet egy megoldását:

\begin{aligned}x&=u\frac{b}{(a,m)} \\ y&=v\frac{b}{(a,m)}\end{aligned}

Az $u$ és $v$ együtthatók a 21.1. Tétel bizonyításában szereplő kibővített euklidészi algoritmussal hatékonyan kiszámíthatók.

A 2. állítás az $m\gt 0$ esetben: Tegyük fel, hogy az $x=s$ , $y=t$ számpár egy megoldása az $ax+my=b$ egyenletnek, és helyettesítsük be ugyanebbe az egyenletbe az állításban szereplő számpárt:

a\cdot(\underbrace{s+k\cdot \frac{m}{(a,m)}}_{=x})+m\cdot (\underbrace{t-k\cdot \frac{a}{(a,m)}}_{=y})=b

A zárójeleket felbontva az alábbit kapjuk:

as+ka\cdot \frac{m}{(a,m)}+mt-km\cdot \frac{a}{(a,m)}=b

Szorozzuk meg mindkét oldalt az $(a,m)$ kitüntetett közös osztóval:

as\cdot (a,m)+ka\cdot \frac{m}{(a,m)}\cdot (a,m)+mt\cdot (a,m)-km\cdot \frac{a}{(a,m)}\cdot (a,m)=b\cdot (a,m)

A tétel szövege alapján $\frac{m}{(a,m)}\cdot (a,m)=m$ és $\frac{a}{(a,m)}\cdot (a,m)=a$ , ezért az alábbit kapjuk:

as\cdot (a,m)+\cancel{kam}+mt\cdot (a,m)-\cancel{kma}=b\cdot (a,m)

Mivel $m\neq 0$ , és teljesül az $(a,m)|m$ oszthatóság – hiszen $(a,m)$ közös osztó –, ezért az oszthatóság tulajdonságairól szóló 16.2. Tétel 4. pontja miatt $(a,m)\neq 0$ , és így a 15.4. Tétel alapján az egyenlet mindkét oldalát lehet egyszerűsíteni vele:

as+mt=b

Ez viszont teljesül, mivel az $x=s$ , $y=t$ számpárról tudjuk, hogy megoldása az $ax+my=b$ egyenletnek.

A 3. állítás az $m\gt 0$ esetben: Tegyük fel, hogy az $x=s_1$ , $y=t_1$ számpár, valamint az $x=s_2$ , $y=t_2$ számpár is megoldása az $ax+my=b$ egyenletnek.

Ez a 20.13. Tétel alapján azt jelenti, hogy az $[s_1]_m$ és az $[s_2]_m$ maradékosztályok egyaránt megoldásai az $ax\equiv b\pmod m$ lineáris kongruenciának, azaz tejesülnek az alábbiak:

\begin{aligned}as_1&\equiv b\pmod m \\ as_2&\equiv b\pmod m\end{aligned}

A 20.2. Tétel 4. pontja miatt ez a két kongruencia kivonható egymásból. A másodikat az elsőből kivonva ezt kapjuk:

a\cdot (s_2-s_1)\equiv 0\pmod m

A kongruenciák egyszerűsítéséről szóló 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük $a$ -val, amennyiben az $m$ modulust is egyszerűsítjük az $(a,m)$ kitüntetett közös osztóval. Ezt végrehajtva a következőt kapjuk:

s_2-s_1\equiv 0\pmod{\frac{m}{(a,m)}}

Ez a kongruencia a 20.1. Tétel 3. pontja alapján épp azt jelenti, hogy teljesül az alábbi oszthatóság:

\frac{m}{(a,m)}|s_2-s_1

Az oszthatóság 16.1. Definíciója alapján ez azt jelenti, hogy létezik olyan $k$ egész szám, amelyre teljesül az alábbi egyenlet:

k\cdot \frac{m}{(a,m)}=s_2-s_1

Mindkét oldalhoz $s_1$ -et adva megkapjuk a tételben szereplő képletet $s_2$ -re:

s_2=s_1+k\cdot \frac{m}{(a,m)}

Mostmár csak a $t_2$ -t kellene valahogy kifejezni $t_1$ -ből. Azt ugye tudjuk, hogy az $x=s_1$ , $y=t_1$ számpár, valamint az $x=s_2$ , $y=t_2$ számpár is megoldása az $ax+my=b$ egyenletnek, azaz:

\begin{aligned}as_1+mt_1&=b \\ as_2+mt_2&=b\end{aligned}

A második egyenletből az elsőt kivonva az alábbit kapjuk:

a(s_2-s_1)+m(t_2-t_1)=0

Az $s_2$ helyére a fentebb megkapott képletet behelyettesíthetjük:

a(\underbrace{s_1+k\cdot \frac{m}{(a,m)}}_{=s_2}-s_1)+m(t_2-t_1)=0

Azaz:

\cancel{as_1}+ak\cdot \frac{m}{(a,m)}-\cancel{as_1}+m(t_2-t_1)=0

A tétel szövege alapján $\frac{m}{(a,m)}\cdot (a,m)=m$ , ezért mindkét oldalt az $(a,m)$ kitüntetett közös osztóval megszorozva ezt kapjuk:

akm+m\cdot (a,m)\cdot (t_2-t_1)=0

Mivel $m\neq 0$ , ezért a 15.4. Tétel alapján az egyenlet mindkét oldalát lehet egyszerűsíteni vele:

ak+(a,m)\cdot (t_2-t_1)=0

Mindkét oldalból $ak$ -t levonva ezt kapjuk:

(a,m)\cdot (t_2-t_1)=-ak

A tétel szövege alapján $\frac{a}{(a,m)}\cdot (a,m)=a$ , így:

(a,m)\cdot (t_2-t_1)=-k\cdot \underbrace{\frac{a}{(a,m)}\cdot (a,m)}_{=a}

t_2-t_1=-k\cdot \frac{a}{(a,m)}

Mindkét oldalhoz $t_1$ -et adva megkapjuk a tételben szereplő képletet $t_2$ -re:

t_2=t_1-k\cdot \frac{a}{(a,m)}

Ezzel a tétel mindhárom állítását igazoltuk az $m\gt 0$ esetben. Erre viszonylag könnyen visszavezethetjük az $m\lt 0$ esetet, amennyiben kihasználjuk azt a tényt, hogy a 15.12. Definíció utáni megjegyzés alapján ekkor $-m\gt 0$ . Ennek technikai részleteit az alábbiakban ismertetjük:

m\lt 0

eset

Az 1. állítás az $m\lt 0$ esetben: Mivel ekkor tehát $-m\gt 0$ , ezért az $ax+(-m)y=b$ egyenlet egy megoldását az 1. állítás eddigi bizonyítása alapján kiszámíthatjuk a kibővített euklidészi algoritmus segítségével. Tegyük fel, hogy eredményként az $x=s$ , $y=t$ számpárt kapjuk, azaz teljesül az alábbi:

as+(-m)t=b

A 15.1. Tétel 3. pontja alapján az egyenlet baloldala átírható a következőképpen:

as+m(-t)=b

Azaz lényegében megkaptuk az eredeti $ax+my=b$ egyenlet egy megoldását:

\begin{aligned} x&=s \\ y&=-t \end{aligned}

A 2. állítás az $m\lt 0$ esetben: Tegyük fel, hogy az $x=s$ , $y=t$ számpár megoldása az $ax+my=b$ egyenletnek. Ekkor az előbbivel megegyező gondolatmenet alapján az $x=s$ , $y=-t$ számpár viszont megoldása az $ax+(-m)y=b$ egyenletnek.

Mivel $-m\gt 0$ , ezért a 2. állítás eddigi bizonyítása alapján tetszőleges $k$ egész szám esetén az alábbi számpár is megoldása az $ax+(-m)y=b$ egyenletnek:

\begin{aligned} x&=s+k\cdot \frac{-m}{(a,-m)}=s-k\cdot \frac{m}{(a,-m)} \\ y&=-t-k\cdot \frac{a}{(a,-m)} \end{aligned}

A 16.8. Tétel 1. pontja alapján $m$ és az ellentettje egymás asszociáltjai – azaz pontosan ugyanazok az osztóik és a többszöröseik –, emiatt teljesül az $(a,-m)=(a,m)$ egyenlőség, vagyis az $ax+(-m)y=b$ egyenlet iménti megoldása átírható így:

\begin{aligned}x&=s-k\cdot \frac{m}{(a,m)} \\ y&=-t-k\cdot \frac{a}{(a,m)}\end{aligned}

Ekkor azonban az 1. állítás $m\lt 0$ esetre adott bizonyítása alapján az alábbi számpár megoldása az eredeti $ax+my=b$ egyenletnek:

\begin{aligned} x&=s-k\cdot \frac{m}{(a,m)} \\ y&=-(-t-k\cdot \frac{a}{(a,m)})=t+k\cdot \frac{a}{(a,m)} \end{aligned}

Ha tehát kiválasztunk egy tetszőleges $l$ egész számot, akkor az iménti gondolatmenetet a $k=-l$ helyettesítéssel végigjátszva az eredeti $ax+my=b$ egyenlet egy $x=s$ , $y=t$ megoldásából valóban egy újabb megoldást kapunk a tételben szereplő képlettel:

\begin{aligned} x&=s+l\cdot \frac{m}{(a,m)} \\ y&=t-l\cdot \frac{a}{(a,m)} \end{aligned}

Végül a 3. állítás az $m\lt 0$ esetben: Tegyük fel, hogy az $x=s_1$ , $y=t_1$ számpár és az $x=s_2$ , $y=t_2$ számpár két tetszőleges megoldása az $ax+my=b$ egyenletnek. Ekkor az 1. állítás $m\lt 0$ esetre adott bizonyítása alapján az $x=s_1$ , $y=-t_1$ és az $x=s_2$ , $y=-t_2$ számpárok megoldásai az $ax+(-m)y=b$ egyenletnek.

Mivel $-m\gt 0$ , ezért a 3. állítás eddigi bizonyítása alapján létezik olyan $k$ egész szám, amelyre teljesülnek az alábbiak:

\begin{aligned}s_2&=s_1+k\cdot \frac{-m}{(a,-m)}=s_1-k\cdot \frac{m}{(a,-m)} \\ -t_2&=-t_1-k\cdot \frac{a}{(a,-m)}\end{aligned}

A második egyenlet mindkét oldalának ellentettjét véve, továbbá ismét alkalmazva a 16.8. Tétel 1. pontja alapján fennálló $(a,-m)=(a,m)$ egyenlőséget ezt kapjuk:

\begin{aligned} s_2&=s_1-k\cdot \frac{m}{(a,m)} \\ t_2&=t_1+k\cdot \frac{a}{(a,m)} \end{aligned}

Az $l=-k$ választással élve tehát valóban találtunk olyan egész számot, amely esetén az eredeti $ax+my=b$ egyenlet bármely két $x=s_1$ , $y=t_1$ és $x=s_2$ , $y=t_2$ megoldásai között fennáll a tételben szereplő alábbi összefüggés:

\begin{aligned} s_2&=s_1+l\cdot \frac{m}{(a,m)} \\ t_2&=t_1-l\cdot \frac{a}{(a,m)} \end{aligned}

∎

Iratkozz fel a hírlevelünkre