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

Statement

Suppose $a$ is an integer, $n$ is a natural number, and $Φ_{n}$ denotes the cyclotomic polynomial for the primitive $n^{t h}$ roots of unity. Suppose $p$ is a prime divisor of $Φ_{n} (a)$ . Then, either $p$ is congruent to $1$ modulo $n$ , or we can write $n = c d$ , where $p$ divides $c$ , and $p$ is congruent to $1$ modulo $d$ .

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

$p$ divides $n$ .
$p$ is congruent to $1$ modulo $n$ .

Proof

Given: An integer $a$ , a natural number $n$ . A prime divisor $p$ of $Φ_{n} (a)$ .

To prove: $p$ divides $n$ or we can write $n = c d$ such that $p$ divides $c$ and $p$ is congruent to $1$ modulo $d$ .

Proof: Since $Φ_{n} (a) | a^{n} - 1$ , $a$ and $p$ are relatively prime and the order of $a$ modulo $p$ divides $n$ .

Let $d$ be the order of $a$ modulo $p$ . Then, $c$ divides $n$ . Let $c = n / d$ . Write:

$a^{n} - 1 = (a^{d} - 1) (a^{n - d} + a^{n - 2 d} + \dots + 1)$ .

We now consider two cases:

Case 1: $d = n$ . In this case, the order of $a$ mod $p$ equals $n$ . But by Fermat's little theorem, the order of $a$ mod $p$ divides $p - 1$ . Thus, $p$ is congruent to $1$ modulo $n$ .
Case 2: $d < n$ . In this case, no primitive $n^{t h}$ root of unity is a $d^{t h}$ root of unity. Now, $Φ_{n} (x)$ divides $(x^{n} - 1) / (x^{d} - 1)$ (one way of seeing this is that $Φ_{n} (x)$ is the product of linear factors for primitive $n^{t h}$ roots of unity, while $x^{n} - 1) / (x^{d} - 1)$ is the product of linear factors for $n^{t h}$ roots that aren't $d^{t h}$ roots. In particular, $Φ_{n} (a)$ divides $(a^{n} - 1) / (a^{d} - 1) = (a^{n - d} + \dots + 1)$ . Each of the monomials in the right side is a power of $a^{d}$ , hence is $1$ mod $p$ , and there are $c$ terms. Thus, $p$ divides $c$ . Also, the order of $a$ mod $p$ divides $p - 1$ , so $p$ is $1$ modulo $d$ . This completes the proof.