youproof.orgDeep Math. Human Access.

Bizonyítás

Az ak≡bk(modm)ak\equiv bk\pmod m kongruencia a 20.1. Tétel 3. pontja alapján akkor és csak akkor teljesül, ha fennáll az m∣ak−bkm|ak-bk, azaz a disztributivitási szabály miatt az alábbi oszthatóság:

m∣(a−b)cm|(a-b)c

Ugye md\frac{m}{d}-vel jelöltük azt az egész számot, amelyet a dd kitüntetett közös osztóval megszorozva az mm modulust kapjuk. Ehhez hasonlóan jelöljük kd\frac{k}{d}-vel azt az egész számot, amelyet ugyancsak dd-vel megszorozva a kk egész számot kapjuk. Azaz:

m=md⋅dk=kd⋅d\begin{aligned} m&=\frac{m}{d}\cdot d \\ k&=\frac{k}{d}\cdot d \end{aligned}

Nyilván az md\frac{m}{d} és a kd\frac{k}{d} egész számok léteznek, hiszen dd osztója mm-nek is és kk-nak is, mivel ő épp kettejük kitüntetett közös osztója. Ezek után a fenti oszthatóság így néz ki:

md⋅d⏟=m∣(a−b)kd⋅d⏟=k\underbrace{\frac{m}{d}\cdot d}_{=m}|(a-b)\underbrace{\frac{k}{d}\cdot d}_{=k}

A 17.8. Tétel alapján egy integritástartományban – mint amilyen a 15.6. Tétel alapján az egész számok Z\Z gyűrűje is – egy oszthatóság mindkét oldalát szabad egyszerűsíteni bármilyen nemnulla elemmel. A d≠0d\neq 0 feltétel teljesül, hiszen ő nem más, mint kk és mm kitüntetett közös osztója, amely az m≠0m\neq 0 feltétel és a 16.2. Tétel 4. pontja miatt biztosan nem lehet 00. A fenti oszthatóság tehát az egyszerűsítési szabály miatt pontosan akkor teljesül, amikor teljesül az alábbi oszthatóság:

md∣(a−b)kd\frac{m}{d}|(a-b)\frac{k}{d}

Nézzük most meg, hogy mit tudunk elmondani a (kd,md)(\frac{k}{d},\frac{m}{d}) kitüntetett közös osztóról. Azt ugye tudjuk, hogy (k,m)=d(k,m)=d, így tehát igaz az alábbi:

(kd⋅d⏟=k,md⋅d⏟=m)=d(\underbrace{\frac{k}{d}\cdot d}_{=k},\underbrace{\frac{m}{d}\cdot d}_{=m})=d

A 17.9. Tétel miatt teljesül az alábbi asszociáltság:

(kd⋅d,md⋅d)⏟=d∼d⋅(kd,md)\underbrace{(\frac{k}{d}\cdot d,\frac{m}{d}\cdot d)}_{=d}\sim d\cdot (\frac{k}{d},\frac{m}{d})

Minthogy a 16.10. Tétel alapján egy integritástartományban egy elem asszociáltjai pontosan az egységszeresei, emiatt a (kd,md)(\frac{k}{d},\frac{m}{d}) kitüntetett közös osztó szükségképpen egység kell legyen. Ez a 17.10. Definíció utáni megjegyzés alapján pontosan azt jelenti, hogy a kd\frac{k}{d} és az md\frac{m}{d} egész számok egymáshoz relatív prímek. Mindeközben azonban – ahogyan fentebb már láttuk – teljesül az alábbi oszthatóság:

md∣(a−b)kd\frac{m}{d}|(a-b)\frac{k}{d}

Mármost ez az oszthatóság egyrészt a 16.2. Tétel 7. pontja miatt akkor, másrészt pedig – mivel md\frac{m}{d} relatív prím kd\frac{k}{d}-hez – a 17.11. Tétel miatt csak akkor teljesül, amikor teljesül az alábbi oszthatóság is:

md∣(a−b)\frac{m}{d}|(a-b)

Ez viszont a 20.1. Tétel 3. pontja alapján pontosan azt jelenti, hogy – a tétel állításának megfelelően – teljesül az alábbi kongruencia:

a≡b(modmd)a\equiv b\pmod{\frac{m}{d}}

A bizonyítás során minden lépésben "akkor és csak akkor"-típusú állításokat használtunk, ezért a teljes gondolatmenet megfordítható. A tételben szereplő két kongruencia tehát egyszerre teljesül, vagy nem teljesül.

∎