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}$

  • 1
    $\begingroup$ @user8268 That seems to contradict $\sum\limits_{k=0}^{p-1}\omega^k = \dfrac{\omega^p - 1}{\omega-1} = 0$. $\endgroup$ – Daniel Fischer Sep 26 '13 at 19:45
  • $\begingroup$ @DanielFisher I'm officially stupid $\endgroup$ – 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.

  • 1
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer Sep 27 '13 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.