Lemma 1:
Let ζ = the n-th root of unity where ζ ≠ 1
Then:
1 + ζ + ζ2 + ... + ζn-1 = 0
Proof:
(1) Since ζn = 1, we have:
1 + ζ + ζ2 + ... + ζn-1 = ζ(1 + ζ + ζ2 + ... + ζn-1)
(2) Now ζ ≠ 0 [since 0n ≠ 1] and ζ ≠ 1
(3) Let x = 1 + ζ + ζ2 + ... + ζn-1
(4) Assume that x ≠ 0
(5) So, x = ζx [from step #1]
(6) Since we assume x ≠ 0, we can divide both sides by x to get 1 = ζ
(7) But this contradicts step #2 so we reject our assumption in step #3 and conclude that:
1 + ζ + ζ2 + ... + ζn-1 =0
QED
Corollary 1.1:
if ζ is a primitive n-th root of unity, then:
a = (-a) ζ + (-a)ζ2 + ... + (-a)ζn-1
Proof:
(1) From Lemma 1 above:
-1 = ζ + ζ2 + ... + ζn-1
(2) So, a = (-a)(ζ + ζ2 + ... + ζn-1 ) = (-a) ζ + (-a)ζ2 + ... + (-a)ζn-1
QED
Lemma 2:
if i ≡ j (mod q)
and
ζ is a primitive qth root of unity
Then:
ζi = ζj
Proof:
(1) i ≡ j (mod q) implies there exists integers r,s such that:
i +r*q = j + s*q
(2) So, it follows that:
ζi*(ζq)r = ζj*(ζq)s
(3) Since ζq = 1, we have:
ζi*1r = ζj*1s
which means that:
ζi = ζj
QED
No comments :
Post a Comment