youproof.orgDeep Math. Human Access.

Bizonyítás

A d_p\equiv d\pmod{p-1} kongruencia a 20.1. Tétel 3. pontja alapján az alábbi oszthatóság teljesülését jelenti:

p-1|d_p-d

Ez az oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan k egész szám, amelyre teljesül az alábbi egyenlet:

k(p-1)=d_p-d

Az egyenlet mindkét oldalához d-t adva az alábbi kifejezést kapjuk d_p-re:

d_p=k(p-1)+d

Ez alapján az y^d\equiv y^{d_p}\pmod p kongruencia így írható fel:

y^d\equiv y^{\overbrace{k(p-1)+d}^{=d_p}}\pmod p

Ez a hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján az alábbi alakra hozható:

y^d\equiv (y^{p-1})^k \cdot y^d\pmod p

Amennyiben y relatív prím p-hez, akkor alkalmazható a kis Fermat-tétel, amely alapján a fenti kongruencia jobboldalán szereplő y^{p-1} tényező 1-gyel kongruens modulo p:

y^d\equiv 1^k \cdot y^d\pmod p

Így tehát a kongruencia jobboldala a 20.2. Tétel 4. és 6. pontja alapján valóban y^d-vel kongruens modulo p.

Amennyiben y nem relatív prím p-hez, akkor a 21.4. Lemma alapján teljesül a p|y oszthatóság. Ilyenkor tehát ugyancsak teljesül a fenti kongruencia, hiszen mindkét oldal 0-val kongruens modulo p.

∎