Proof.

According to Definition A-8.1 in §A-8.1, the roots of ${\mathrm{\Phi }}_M(x)$ are $e^{2\mathit{𝑘𝜋𝑖}∕M}=e^{2\mathit{𝑘𝜋𝑖}∕(2n)}=e^{\mathit{𝑘𝜋𝑖}∕n}$ where $0\le k<M=2n$ and $\mathsf{\text{𝗀𝖼𝖽}}(k,M=2n)=1$, thus $k=\{1,3,5,\cdots ,2n-1\}$. If we let $\omega =e^{\mathit{𝑖𝜋}∕n}$, then the roots of ${\mathrm{\Phi }}_M(x)$ are $\omega ,{\omega }^3,{\omega }^5,\cdots ,{\omega }^{2n-1}$. □

Proof. $$

1.

The roots of $x^n-1$ are all the $n$-th roots of unity. Thus, $x^n-1=(x-{\omega }^0)(x-{\omega }^1)...(x-{\omega }^{n-1})$, where $\zeta ={\omega }^k$.

2.

Theorem A-7.2.3 states that each $n$-th root of unity (${\omega }^k$) is a primitive $d$-th root of unity for some $d$ that divides $n$. In other words, each $n$-th root of unity belongs to some $P(d)$ where $d\mid n$. Meanwhile, by definition, ${\mathrm{\Phi }}_d(x)={\mathrm{\Pi }}_{\zeta \in P(d)}(x-\zeta )$. Therefore, $x^n-1$ is the product of all ${\mathrm{\Phi }}_d(x)$ such that $d\mid n$.

□

Proof. $$

1.

We prove by induction. When $n=1$, ${\mathrm{\Phi }}_1(x)=x-1$, where each coefficient is an integer.

2.

Let $x^n-1=f(x)\cdot g(x)=({\mathrm{\Sigma }}_{i=0}^p{a}_i{x}^i)({\mathrm{\Sigma }}_{j=0}^q{b}_j{x}^j)$. As an induction hypothesis 1, we will prove that if $f(x)$ has only integer coefficients, then $g(x)$ will also have only integer coefficients. Given our target equation is $x^n-1$, we know that $a_p{x}^p\cdot b_q{x}^q=x^n$, and thus $a_p{b}_q=1$, which means $a_p=\pm 1$ (as we hypothesized that $f(x)$ has only integer coefficients). We also know that $a_0{b}_0=-1$. All the other coefficients should be 0. Thus, for any $r<q$, the coefficients are either: (i) $a_p{b}_r+a_{p-1}{b}_{r+1}+...+a_{p-q+r}{b}_q=0$; or (ii) $a_p{b}_r+a_{p-1}{b}_{r+1}+...+a_0{b}_{r+p}=0$. Both case (i) and (ii) represent $f(x)\cdot g(x)$’s computed coefficient of some $x^i$ where $0<i<n$. Now, we propose another induction hypothesis 2, which is that $b_q,...b_{r+1}$ are all integers.

3.

In the case of (i), $a_p{b}_r=-(a_{p-1}{b}_{r+1}+...+a_{p-q+r}{b}_q)$, and dividing both sides by $a_p$ (which is either $1$ or $-1$), $b_r=\pm (a_{p-1}{b}_{r+1}+...+a_{p-q+r}{b}_q)$, as every $a_i$ is an integer based on our hypothesis. By induction hypothesis 1 and 2, $b_r$ is an integer. The same is true in the case of (ii).

4.

We set $b_q$ (an integer coefficient) as the starting point for induction hypothesis 2. Then, according to induction proof 2, all of $b_j$ for $0\le j\le q$ are integers.

5.

Now, we set ${\mathrm{\Phi }}_1(x)$ (an integer coefficient polynomial) as the starting point for induction hypothesis 1. Let $x^n-1={\mathrm{\Phi }}_{d_1}(x){\mathrm{\Phi }}_{d_2}(x)...{\mathrm{\Phi }}_{d_k}(x){\mathrm{\Phi }}_n(x)$, where each $d_i\mid n$ (Theorem A-8.2.2). We know that ${\mathrm{\Phi }}_{d_1}(x){\mathrm{\Phi }}_{d_2}(x)\cdots {\mathrm{\Phi }}_{d_k}(x)$ forms an integer coefficient polynomial. We treat ${\mathrm{\Phi }}_{d_1}(x){\mathrm{\Phi }}_{d_2}(x)\cdots {\mathrm{\Phi }}_{d_k}(x)$ as $f(x)$, and ${\mathrm{\Phi }}_n(x)$ as $g(x)$. Then, according to step 4’s induction proof, ${\mathrm{\Phi }}_n(x)$ is an integer coefficient polynomial (also note that ${\mathrm{\Phi }}_n(x)$ is monic, whose the highest degree’s coefficient is 1).

6.

As we marginally increase $n$ to $n+1$ to compute $x^{n+1}-1={\mathrm{\Phi }}_{d_1^{\prime }}(x){\mathrm{\Phi }}_{d_2^{\prime }}(x)...{\mathrm{\Phi }}_{d_k^{\prime }}(x){\mathrm{\Phi }}_{n+1}(x)$ (where each $d_i^{\prime }\mid (n+1)$), we know that ${\mathrm{\Phi }}_{d_1^{\prime }}(x){\mathrm{\Phi }}_{d_2^{\prime }}(x)\cdots {\mathrm{\Phi }}_{d_k^{\prime }}(x)$ is a monic polynomial, as proved by the previous induction step. Thus, ${\mathrm{\Phi }}_{n+1}(x)$ is also monic.

□

Proof. $$

1.

Theorem A-4.2.3 states that given $k\mid n$, ${\text{ord}}_{𝔽}(a)=\mathit{𝑘𝑛}$ if and only if ${\text{ord}}_{𝔽}(a^k)=n$. This means that for $\zeta \in ℂ$, ${\text{ord}}_{ℂ}(\zeta )=\mathit{𝑛𝑘}$ if and only if ${\text{ord}}_{ℂ}({\zeta }^k)=n$. In other words, $\zeta$ is a primitive $\mathit{𝑛𝑘}$-th root of unity if and only if ${\zeta }^k$ is the primitive $n$-th root of unity. This implies that $\zeta$ is a root of ${\mathrm{\Phi }}_{\mathit{𝑛𝑘}}(x)$ if and only if ${\zeta }^k$ is a root of ${\mathrm{\Phi }}_n(x)$.

2.

Let ${\mathrm{\Phi }}_{\mathit{𝑛𝑘}}(x)=(x-{\zeta }_1)(x-{\zeta }_2)...(x-{\zeta }_p)$, where $P(\mathit{𝑛𝑘})$ has $p$ primitive $\mathit{𝑛𝑘}$-th roots of unity.

3.

${\mathrm{\Phi }}_n(x)=(x-{\zeta }_1^k)(x-{\zeta }_2^k)...(x-{\zeta }_p^k)$. Note that raising each element of $P(\mathit{𝑛𝑘})$ to the $k$-th power yields an element of $P(n)$, thus mapping $P(\mathit{𝑛𝑘})$ onto $P(n)$ (by the result of step 2). Now, it’s also true that ${\mathrm{\Phi }}_n(y)=(y-{\zeta }_1^k)(y-{\zeta }_2^k)...(y-{\zeta }_p^k)$, where $y=x^k$. In this case, $x=\{{\zeta }_1,{\zeta }_2,...{\zeta }_p\}$.

4.

${\mathrm{\Phi }}_{\mathit{𝑛𝑘}}(x)$ and ${\mathrm{\Phi }}_n(y)={\mathrm{\Phi }}_n(x^k)$ have the same roots with the same coefficients. Therefore, ${\mathrm{\Phi }}_{\mathit{𝑛𝑘}}(x)={\mathrm{\Phi }}_n(y)={\mathrm{\Phi }}_n(x^k)$.

□