Sunday, July 16, 2006

Modular Arithmetic: Additional Lemma

Lemma 1: if a ≡ b (mod p), then apn-1 ≡ bpn-1 (mod pn)

Proof:

(1) a ≡ b (mod p)

(2) So, there exists c such that pc = a - b

(3) So that a = pc + b

(4) So, apn-1 ≡ (pc+b)pn-1 ≡ pnc + bpn-1 ≡ bpn-1 (mod pn)

QED