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 λ
Proof:
(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).
QED
Tuesday, May 23, 2006
Monday, May 22, 2006
modular arithmetic and functions
Today, I want to go over a single lemma which I use in my analysis of cyclotomic integers.
Lemma 1:
if α,β are integers such α ≡ β (mod γ) and f(x) = xn + a1xn-1 + ... + an
then f(α) ≡ f(β) (mod γ)
Proof:
(1) f(α) - f(β) = [(α)n - (β)n] + [a1(α)n-1 - a1(β)n-1] + ... + [an-1α - an-1β] + [an - an]
(2) Now, since α ≡ β (mod γ), we also have:
(α)2 ≡ (β)2 (mod γ)
all the way up to:
(α)n-1 ≡ (β)n-1 (mod γ)
and:
(α)n ≡ (β)n (mod γ)
(3) So this means that γ divides all parts of
[(α)n - (β)n] + [a1(αn-1 - βn-1)] + ... + [an-1(α - β)]
(4) Which means that γ divides f(α) - f(β)
QED
Lemma 1:
if α,β are integers such α ≡ β (mod γ) and f(x) = xn + a1xn-1 + ... + an
then f(α) ≡ f(β) (mod γ)
Proof:
(1) f(α) - f(β) = [(α)n - (β)n] + [a1(α)n-1 - a1(β)n-1] + ... + [an-1α - an-1β] + [an - an]
(2) Now, since α ≡ β (mod γ), we also have:
(α)2 ≡ (β)2 (mod γ)
all the way up to:
(α)n-1 ≡ (β)n-1 (mod γ)
and:
(α)n ≡ (β)n (mod γ)
(3) So this means that γ divides all parts of
[(α)n - (β)n] + [a1(αn-1 - βn-1)] + ... + [an-1(α - β)]
(4) Which means that γ divides f(α) - f(β)
QED
Subscribe to:
Posts
(
Atom
)