youproof.orgDeep Math. Human Access.

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}

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:

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:

Az 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}

∎