youproof.orgDeep Math. Human Access.

Bizonyítás

Az [a]m[a]_m maradékosztály a 20.6. Definíció alapján pontosan akkor redukált, ha invertálható, azaz létezik pontosan egy olyan X=[x]mX=[x]_m maradékosztály, amelyre teljesül az alábbi:

[a]m⊙X=[a]m⊙[x]m=[a⋅x]m=[1]m[a]_m\odot X=[a]_m\odot [x]_m=[a\cdot x]_m=[1]_m

Ez pontosan az alábbi lineáris kongruencia egyértelmű megoldhatóságát jelenti:

ax≡1(modm)ax\equiv 1\pmod m

Ez viszont a 20.13. Tétel szerint akkor és csak akkor oldható meg, ha teljesül az (a,m)∣1(a,m)|1 oszthatóság. Ez a 16.5. Tétel alapján azt jelenti, hogy az (a,m)(a,m) kitüntetett közös osztó egység, ami a 17.10. Definíció utáni megjegyzés szerint épp azt jelenti, hogy aa relatív prím az mm modulushoz, azaz

(a,m)∼1(a,m)\sim 1

Válasszuk a pozitív egységet kitüntetett közös osztónak, azaz legyen (a,m)=1(a,m)=1. Ebben az esetben a lineáris kongruencia megoldásainak száma a 20.14. Tétel értelmében 11, azaz a megoldás egyértelmű.

Most igazoljuk a tétel másik állítását, miszerint bármely maradékosztály összes elemének asszociáltság erejéig ugyanaz az mm modulussal vett kitüntetett közös osztója. Az [a]m=[b]m[a]_m=[b]_m egyenlőség azt jelenti, hogy aa ugyanabban a maradékosztályban van, mint bb. Így tehát a 20.4. Tétel alapján a bb egész szám felírható az alábbi alakban valamilyen alkalmas k1k_1 egész szám segítségével:

b=k1m+ab=k_1m+a

Mivel az (a,m)(a,m) kitüntetett közös osztó osztója aa-nak és mm-nek, ezért a 16.2. Tétel 7. és 6. pontja miatt osztója k1m+a=bk_1m+a=b-nek is. Így tehát (a,m)(a,m) közös osztója bb-nek és mm-nek, vagyis a 17.4. Definíció alapján osztója ezek kitüntetett közös osztójának, azaz teljesül az (a,m)∣(b,m)(a,m)|(b,m) oszthatóság.

Ugyanígy a 20.4. Tétel alapján az aa egész szám is felírható az alábbi alakban valamilyen alkalmas k2k_2 egész szám segítségével:

a=k2m+ba=k_2m+b

Ebből az előző gondolatmenetet megismételve azt fogjuk kapni, hogy teljesül a (b,m)∣(a,m)(b,m)|(a,m) oszthatóság. Minthogy mindkét irányban fennáll az oszthatóság (a,m)(a,m) és (b,m)(b,m) között, ezért a 16.9. Tétel miatt:

(a,m)∼(b,m)(a,m)\sim (b,m)

Speciálisan ha aa relatív prím mm-hez, akkor (a,m)(a,m) egység, és így az asszociáltság miatt (b,m)(b,m) is egység, azaz bb is relatív prím mm-hez.

∎