Elementary Lemmas

Lemma 1:

If:

gcd(e,f)=1
e divides k
f divides k

Then:

ef divides k

Proof:

(1) Assume that ef does not divide k.

(2) Then, there must exist a prime p and a power c such that p^c divides ef but p^c does not divide k.

(3) Since gcd(e,f)=1, it follows that p^c must entirely divide e or p^c must entirely divide f.

(4) Let's assume that p^c divides e. [We can make a parallel argument if p^c divides f.

(5) But then we have a contradiction since e divides k implies that p^c divides k.

(6) So we reject our assumption in step #1.

QED

Lemma 2:

If a ≥ b and b ≥ a, then a = b

Proof:

(1) a ≥ b

(2) So it follows that a = b or a is greater than b.

(3) But a is not greater than b since b ≥ a.

(4) So then it follows that a = b.

QED

Corollary 2.1:

If a,b are positive and a divides b and b divides a, then a = b

Proof:

(1) If a divides b, then b ≥ a.

(2) If b divides a, then a ≥ b

(3) Since a ≥ b and b ≥ a, we can use Lemma 2 above to conclude that a= b.

QED

Lemma 3:

if gcd(e,f)=1 and e divides af

then:

e divides a

Proof:

(1) Assume that e does not divide a.

(2) Then, there exists a prime p such that p^c divides e but does not divide a.

(3) Since p^c divides e, it follows that p^c must divide af.

(4) Using Euclid's Lemma (see Lemma 2, here), we know that if p divides af, then it divides a or it divides f. But it cannot divide f since gcd(e,f)=1 so it divides a.

(5) But then p^c must divide a since no p can divide f. This contradicts step #2.

(6) Therefore, we reject our assumption in step #1.

QED

Cyclotomic Equation

Lemma 1:

Let ζ = the n-th root of unity where ζ ≠ 1

Then:

1 + ζ + ζ² + ... + ζ^n-1 = 0

Proof:

(1) Since ζⁿ = 1, we have:

1 + ζ + ζ² + ... + ζ^n-1 = ζ(1 + ζ + ζ² + ... + ζ^n-1)

(2) Now ζ ≠ 0 [since 0ⁿ ≠ 1] and ζ ≠ 1

(3) Let x = 1 + ζ + ζ² + ... + ζ^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 + ζ + ζ² + ... + ζ^n-1 =0

QED

Corollary 1.1:

if ζ is a primitive n-th root of unity, then:

a = (-a) ζ + (-a)ζ² + ... + (-a)ζ^n-1

Proof:

(1) From Lemma 1 above:

-1 = ζ + ζ² + ... + ζ^n-1

(2) So, a = (-a)(ζ + ζ² + ... + ζ^n-1 ) = (-a) ζ + (-a)ζ² + ... + (-a)ζ^n-1

QED

Lemma 2:

if i ≡ j (mod q)

and

ζ is a primitive qth root of unity

Then:

ζⁱ = ζ^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:

ζⁱ*(ζ^q)^r = ζ^j*(ζ^q)^s

(3) Since ζ^q = 1, we have:

ζⁱ*1^r = ζ^j*1^s

which means that:

ζⁱ = ζ^j

QED