youproof.orgDeep Math. Human Access.

Bizonyítás

Az 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-bk, azaz a disztributivitási szabály miatt az alábbi oszthatóság:

m|(a-b)c

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

\begin{aligned} m&=\frac{m}{d}\cdot d \\ k&=\frac{k}{d}\cdot d \end{aligned}

Nyilván az \frac{m}{d} és a \frac{k}{d} egész számok léteznek, hiszen d osztója m-nek is és k-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:

\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 gyűrűje is – egy oszthatóság mindkét oldalát szabad egyszerűsíteni bármilyen nemnulla elemmel. A d\neq 0 feltétel teljesül, hiszen ő nem más, mint k és m kitüntetett közös osztója, amely az m\neq 0 feltétel és a 16.2. Tétel 4. pontja miatt biztosan nem lehet 0. 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:

\frac{m}{d}|(a-b)\frac{k}{d}

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

(\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:

\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 (\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 \frac{k}{d} és az \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:

\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 \frac{m}{d} relatív prím \frac{k}{d}-hez – a 17.11. Tétel miatt csak akkor teljesül, amikor teljesül az alábbi oszthatóság is:

\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\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.

∎