youproof.orgDeep Math. Human Access.

Bizonyítás

Tekintsük az alábbi lineáris kongruenciát:

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

Amennyiben ennek a lineáris kongruenciának létezne megoldása, akkor a 20.13. Tétel értelmében teljesülne az (a,m)∣1(a,m)|1 oszthatóság. Minthogy az 11 egész szám a Z\Z gyűrű egységeleme, így ez az oszthatóság a 16.5. Tétel miatt csak abban az esetben teljesülhetne, ha (a,m)(a,m) egység lenne. Ez viszont a 17.10. Definíció utáni megjegyzés alapján azt jelentené, hogy aa relatív prím mm-hez.

Márpedig amennyiben létezik a tételben szereplő pozitív kk kitevő, akkor a fenti lineáris kongruenciának létezik megoldása. Ha például k>1k\gt 1, akkor a tételben szereplő kongruencia a 18.8. Tétel 3. pontja miatt így írható fel:

a⋅ak−1⏟=x≡1(modm)a\cdot \underbrace{a^{k-1}}_{=x}\equiv 1\pmod m

Ebben az esetben tehát x=ak−1x=a^{k-1} lesz a megoldás.

Ha pedig a k=1k=1, akkor pedig a kongruencia így írható fel:

a⋅1⏟=x≡1(modm)a\cdot \underbrace{1}_{=x}\equiv 1\pmod m

Ebben az esetben tehát x=1x=1 lesz a megoldás.

Minthogy minden pozitív esetet lefedtünk, ezért a bizonyítás elején felvázolt gondolatmenet alapján aa valóban relatív prím mm-hez, amennyiben a kritériumnak megfelelő kk kitevő létezik.

∎