# Divisibility involving root of unity

Let $p$ be a prime number and $\omega$ be a $p$-th root of unity. Suppose $a_0,a_1, \dots, a_{p-1}, b_0, b_1, \dots, b_{p-1}$ be integers such that $a_0 \omega^0+a_1 \omega^1+ \dots a_{p-1} \omega^{p-1}$ and $b_0 \omega^0 + b_1 \omega^1 + \dots b_{p-1} \omega^{p-1}$ are also integers

Prove that $(a_0 \omega^0+a_1 \omega^1+ \dots a_{p-1} \omega^{p-1})-(b_0 \omega^0 + b_1 \omega^1 + \dots b_{p-1} \omega^{p-1})$ is divisible by $p$ if and only if $p$ divides all of $a_0-b_0$, $a_1-b_1$, $\dots$, $a_{p-1}-b_{p-1}$

• @user8268 That seems to contradict $\sum\limits_{k=0}^{p-1}\omega^k = \dfrac{\omega^p - 1}{\omega-1} = 0$. – Daniel Fischer Sep 26 '13 at 19:45
• @DanielFisher I'm officially stupid – user8268 Sep 26 '13 at 20:03

## Irreducible polynomial over $\mathbb Z[X]$

Consider the factorization $X^p-1=(X-1)\Phi_p$ where $\Phi_p$ is the cyclotomic polynomial defined to contain all primitive $p$'th roots of unity over $\mathbb C$. Dividing both sides by $(X-1)$ we get $$\Phi_p=X^{p-1}+X^{p-2}+...+1$$ Since all cyclotomic polynomials are irreducible over $\mathbb Q[X]$ they are in particular irreducible over $\mathbb Z[X]$. So given $\omega\neq 1$ that is a $p$'th root of unity we then know that $\omega$ is a root of $\Phi_p$ and that if $\omega$ is a root of some other polynomial $f\in\mathbb Z[X]$ then $\Phi_p$ divides $f$.

## The coefficients of each subexpression

Now if $a_0\omega^0+a_1\omega^1+...+a_{p-1}\omega^{p-1}=k$ is an integer then $\omega$ is a root of $$f:=(a_0-k)+a_1 X+...+a_{p-1} X^{p-1}\in\mathbb Z[X]$$ so $\Phi_p$ divides $f$ in $\mathbb Z[X]$. Hence there must exist $s\in\mathbb Z$ so that $f=s\cdot\Phi_p$ showing that $$a_0-k=a_1=...=a_{p-1}=s$$ A similar argument shows that we must have some $t\in\mathbb Z$ so that $b_0-m=b_1=...=b_{p-1}=t$ in order to have $b_0\omega^0+b_1\omega^1+...+a_{p-1}\omega^{p-1}=m\in\mathbb Z$.

## The coefficients of the difference

With the above we see that \begin{align} &(a_0\omega^0+a_1\omega^1+...+a_{p-1}\omega^{p-1})-(b_0\omega^0+b_1\omega^1+...+a_{p-1}\omega^{p-1})\\ &=(s+k-(t+m))\omega^0+(s-t)\omega^1+...+(s-t)\omega^{p-1}\\ &=k-m \end{align} but this actually suggests that your statement we are trying to prove is wrong in the first place for this holds regardles of $s$ and $t$ so that you can always choose $k-m$ divisible by $p$ without having $a_i-b_i\equiv s-t=0$ mod $p$. This seems to me a contradiction to the statement we are trying to prove! Please correct me if I am mistaken.

• Sanity check, $p = 2$: $2+1\cdot(-1) = 1,\, 3 + 4\cdot(-1) = -1,\, 1-(-1) = 2$, but $2-3 = -1$ and $1-4 = -3$ are both odd. Okay, maybe for odd primes? $p = 3$: $\omega = -\frac12 + i\frac{\sqrt{3}}{2}$. To get an integer, you need $a_2 = a_1$ (unsurprisingly) and nothing else. $2 + \omega + \omega^2 = 1,\, 1 + 3\omega + 3\omega^2 = -2$, $1 - (-2) = 3$, but $a_0-b_0 = 2-1 = 1$ and $a_1 - b_1 = a_2 - b_2 = 1-3 = -2$ aren't divisible by $3$. Add to that that your argument seems correct, the condition is that $a_0 - a_1 \equiv b_0 - b_1 \pmod{p}$. – Daniel Fischer Sep 27 '13 at 10:30