Tuesday, May 23, 2006

Modular Arithmetic and Unique Mappings

Today, I talk about a result using modular arithmetic that I use in the properties of cyclotomic integers.

Lemma 1: For a given odd prime λ, each value i, 2*i, 3*i, ... (λ-1)*i maps to a distinct value of 1,2,3,...,(λ-1) modulo λ


(1) Let a,b be any integer between 1 and λ-1 where a ≠ b

(2) Let i be any integer between 1 and λ - 1.

(3) Assume that a*i ≡ b*i (mod λ) where a,b are distinct.

(4) So λ divides a*i - b*i and there exists c such that λc = ai-bi = i(a-b)

(5) By Euclid's Lemma, λ divides either i or λ divides a-b.

(6) We know that λ doesn't divide i since i is between 1 and λ -1.

(7) So λ divides a-b

(8) But this means that a-b=0 since a,b are between 1 and λ - 1 and if a,b are distinct then abs(a-b) is between 1 and λ-2 which is not divisible by λ

(9) So we have a contradiction and we reject our assumption in (3).


No comments :