Lemma 1: For every cyclotomic prime h(α), there exists a rational prime p such that h(α) divides p.

Proof:

(1) Let h(α) be a cyclotomic prime. [See here for a review of cyclotomic primes]

(2) We know that Nh(α) is a rational integer. [See Lemma 5, here]

(3) By the Fundamental Theorem of Arithmetic, Nh(α) consists of a set of rational primes: p

_{1}*...*p

_{n}.

(4) Since h(α) is a cyclotomic prime, it must divide one of these primes p

_{i}. [See Definition 4, here]

QED

Lemma 2: Every cyclotomic integer g(α) is congruent mod h(α) to a cyclotomic integer of the form a

_{1}α

^{f-1}+ a

_{2}α

^{f-2}+ ... + a

_{f}where a

_{i}are positive integers less than a prime integer p.

Proof:

(1) From a previous result, we know that every cyclotomic integer g(α) can be expressed in the following form:

g(α) = g

_{1}(η)α

^{f-1}+ g

_{2}(η)α

^{f-2}+ ... + g

_{f}(η)

where g

_{i}(η) are cyclotomic integers made up of periods of length f. [See Corollary 3.1, here]

(2) Each cyclotomic integer g

_{i}(η) is congruent mod h(α) to an integer g

_{i}(u) where g

_{i}(u) denotes the integer obtained by substituting

**u**

_{1}for η

_{1}, u

_{2}for η

_{2}, etc. [See Corollary 2.1, here]

(3) We know that there exists a rational prime p such that h(α) divides p. [See Lemma 1 above]

(4) We can assume that g

_{i}(u) is between 0 and p-1 since:

(a) Assume that g

_{i}(u) ≥ p.

(b) There exists a value i such that g

_{i}(u) ≡ i (mod p) and i is between 0 and p-1.

(c) But then g

_{i}(u) ≡ i (mod h(α)) since h(α) divides p.

(d) So, we can conclude that g

_{i}(η) ≡ i (mod h(α))

(5) So that putting it all together, we have:

g(α) = g

_{1}(η)α

^{f-1}+ g

_{2}(η)α

^{f-2}+ ... + g

_{f}(η) ≡ g

_{1}(u)α

^{f-1}+ g

_{2}(u)α

^{f-2}+ ... + g

_{f}(u) ≡

≡ a

_{1}α

^{f-1}+ a

_{2}α

^{f-2}+ ... + a

_{f}(mod h(α))

where a

_{i}is between 0 and p-1.

QED

Corollary 2.1: Every cyclotomic integer g(α) is congruent mod h(α) to 1 of p

^{f}specific cyclotomic integers.

Proof:

(1) From Lemma 2 above, every integer g(α) satisfies the equation below:

g(α) ≡ a

_{1}α

^{f-1}+ a

_{2}α

^{f-2}+ ... + a

_{f}(mod h(α)) where a

_{i}is between 0 and p-1.

(2) Now the conclusion follows from noting that each of the f different integers can take p different values which gives us: p

^{f}different values.

QED

Definition 1: Additive group

An additive group is a group defined around the operation of addition. [See here for a review of the concept of a group]

Example: Z

_{9}is an additive group

Z

_{9}= { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

It is clear that it has all the properties of a group:

(1) Closure: addition of any two integers modulo 9 results in another integer modulo 9.

(2) Identity: 0 is the identity.

(3) Inverse: For any integer, 9-i is the inverse. For example, 1 + 8 = 0 modulo 9.

(4) Associativity: For any a,b,c ∈ Z

_{9}, we see that:

a + (b + c) = (a + b) + c

Lemma 3: The additive group of cyclotomic integers mod p has p

^{λ-1}elements.

Proof:

(1) Let λ be an odd prime and let α be a root of unity such that α

^{λ}= 1 but for all positive integers i less than λ, α

^{i}≠ 1. [See here for review of roots of unity]

(2) All cyclotomic integers based on λ can be put into this form:

a

_{0}+ a

_{1}α + a

_{2}α

^{2}+ ... + a

_{λ-1}α

^{λ-1}

where a

_{i}are all integers [See Lemma 1 here]

(3) Since we are talking about values modulo p, we can assume that a

_{i}is between 0 and p-1.

(4) This means that there are λ-1 elements that can take values of 0 to p-1.

(5) If we count all possible values, this leads us to λ - 1 multiples:

[0..p-1]*[0..p-1]*...*[0..p-1] = p

^{λ-1}

QED

Lemma 4: if h(α) is a cyclotomic prime that divides a rational prime p, then the additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p.

Proof:

(1) We know that the set of cyclotomic integers mod p under '+' is an abelian group since:

(a) It is closed on the operation of '+'

(b) 0 mod p is the identity element.

(c) For any cyclotomic integer ≡ r (mod p), the inverse element is p-r.

(d) '+' is clearly associative in nature.

(e) It is abelian since '+' is commutative.

(2) We can make the same arguments to show that the cyclotomic integers mod h(α) is an abelian group on the operation of addition.

(3) To complete this proof, we only need to show that the set of cyclotomic integers mod h(α) is a subset of the cyclotomic integers mod p.

(4) This is the case since:

(a) Let g(α) be a cyclotomic integer.

(b) Then, there exists r(α) such that g(α) ≡ r(α) (mod h(α)) so that r(α) ∈ additive group of cyclotomic integers mod h(α)

(c) Now we can assume r(α) has the following form (see Lemma 1, here):

a

_{0}+ a

_{1}α + ... + a

_{λ-1}α

^{λ-1}

(d) We can further assume that all a

_{i}are between 0 and p-1 since if a

_{i}is greater than p, then there exists a' such that a

_{i}≡ a' (mod p) where a' is less than p and further if a

_{i}≡ a' (mod p), then a

_{i}≡ a' (mod h(α)) because h(α) divides p.

(e) But if all a

_{i}are between 0 and p-1, then r(α) ∈ the additive group of cyclotomic integers mod p.

QED

Definition 2: Exponent of p mod λ

The exponent of p mod λ is the smallest positive integer whereby p

^{f}≡ 1 (mod λ)

Lemma 5: Let S be the set of cyclotomic integers of the form a

_{1}α

^{f-1}+ a

_{2}α

^{f-2}+ ... + a

_{f}where a

_{i}are positive integers less than p.

Two elements of S are congruent if and only if they are identical.

Proof:

(1) The number of incongruent elements mod h(α) is a power of p, say p

^{n}since:

(a) The additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p. [See Lemma 4 above]

(b) The additive group of cyclotomic integers mod p has p

^{λ-1}elements. [See Lemma 3 above]

(c) Since the additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p, the order of the first group must divide p

^{λ - 1}. [By Lagrange's Theorem, see here]

(d) Because p is prime, the number of elements in the additive group of cyclotomic integers mod h(α) must be a power of p.

(2) The number of incongruent cyclotomic integers mod h(α) is at least λ + 1 because 0, α, α

^{2}, ..., α

^{λ}=1 are all incongruent mod h(α) since:

(a) Any cyclotomic integer divisible by h(α) must have a norm divisible by p [since p = Nh(α), see Lemma 6 here, and since h(α) divides g(α) → Nh(α) divides Ng(α), see Lemma 6 here]

(b) On the other hand, monomials α

^{j}- 0 have norm = 1 [See Lemma 5, here]

(c) The binomials α

^{i}- α

^{j}(where i is not congruent to j mod λ) have a norm equal to N(α-1)=λ [See Lemma 6, here]

(d) Neither 1 nor λ is divisible by p, so none of these cyclotomic integers are divisible by h(α)

(3) The number of nonzero incongruent cyclotomic integers mod h(α) is divisible by λ since:

(a) If α, α

^{2}, ..., α

^{λ}=1 are all the nonzero cyclotomic integers mod h(α), then there are exactly λ of them.

(b) Assume that there exists a cyclotomic integer ψ(α) such that ψ(α) is not congruent to 0 mod h(α) and ψ(α) is not congruent to α

^{j}mod h(α) for j = 1,2, ..., λ.

(c) Then ψ(α)α, ψ(α)α

^{2}, ..., ψ(α)α

^{λ}= ψ(α) are all nonzero mod h(α) [because h(α) is prime] and distinct mod h(α) [because ψ(α)α

^{j}≡ ψ(α)α

^{k}would imply α

^{j}≡ α

^{k}) and distinct from α, α

^{2}, ..., α

^{λ}(because ψ(α)α

^{j}≡ α

^{i}would imply ψ(α) ≡ α

^{k})

(d) If this is all the all the possible nonzero cyclotomic integers congruent to h(α), then there are 2λ of them.

(e) Eventually, we run out of possibilities. Let us say that this happens after m such iterations of step (#3c).

(f) Then, there are mλ distinct nonzero cyclotomic integers mod h(α)

(4) From step #1, we get that the total number of nonzero distinct cyclotomic integers mod h(α) is p

^{n}- 1.

(5) So putting #4 with #3, we get:

mλ = p

^{n}- 1.

(6) This gives us that:

p

^{n}≡ 1 ( mod λ)

(7) Since f is the exponent of p mod λ, (see definition 2 above), we know that n ≥ f. [We know that f ≠ 0 since p

^{n}is greater than λ + 1. ]

(8) Thus, the number of p

^{n}of incongruent elements mod h(α) is at least p

^{f}.

QED

Corollary 5.1: To test for divisibility by h(α), it is not necessary to know h(α) but only the integers u

_{i}where i is between 1 and e and for which η

_{i}≡ u

_{i}(mod h(α)) for all i between 1 and e.

Proof:

(1) We know that a cyclotomic integer g(α) is divisible by h(α) if g(α) ≡ 0 (mod h(α))

(2) For any cyclotomic g(α), we know that it is congruent to a cyclotomic integer of the form a

_{1}α

^{f-1}+ a

_{2}α

^{f-2}+ ... + α

^{f}(mod h(α)) [See Lemma 2 above]

(3) We can now use Lemma 5 above to test for divisibility.

QED