Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer
From Number
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.