# 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.