Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer

Statement

Suppose is an integer, is a natural number, and denotes the cyclotomic polynomial for the primitive roots of unity. Suppose is a prime divisor of . Then, either is congruent to modulo , or we can write , where divides , and is congruent to modulo .

In particular, at least one of these two conditions must hold:

• divides .
• is congruent to modulo .

Proof

Given: An integer , a natural number . A prime divisor of .

To prove: divides or <we can write such that divides and is congruent to modulo .

Proof: Since , and are relatively prime and the order of modulo divides .

Let be the order of modulo . Then, divides . Let . Write:

.

We now consider two cases:

• Case 1: . In this case, the order of mod equals . But by Fermat's little theorem, the order of mod divides . Thus, is congruent to modulo .
• Case 2: . In this case, no primitive root of unity is a root of unity. Now, divides (one way of seeing this is that is the product of linear factors for primitive roots of unity, while is the product of linear factors for roots that aren't roots. In particular, divides . Each of the monomials in the right side is a power of , hence is mod , and there are terms. Thus, divides . Also, the order of mod divides , so is modulo . This completes the proof.