Very Difficult Roots of Unity Filter
by HKIS200543, Aug 16, 2017, 12:25 AM
Problem: (AMSP NT3) Let
be a prime and
,
positive integers. Prove that
divides
where 
Solution




![\[ \sum_{\substack{0 \leq k \leq n\\ p \mid k-s}} (-1)^k \binom{n}{k} \]](http://latex.artofproblemsolving.com/8/e/a/8eabe610e118b6b61a3e214c63d54fd822860afa.png)

Solution
Let
. We use the classical roots of unity filter.
Swapping sums and using the binomial theorem gives
We proceed with a bit of theory of the algebraic integers. Let
It is obvious that
Now let
. Then
. Expanding with the binomial theorem, we have
Subtracting one from each side and dividing by
we see
It follows that
. By Euclidean Division we write
for
. Then we can take
factors of
in our sum:
We may assume assume
is nonnegative or else add multiples of
. It thus suffices to show that
Denote this expression by
then write
Raising to the power of
, it follows that
. We recall
and thus
. We use the following lemma to show that this implies
divides
.
Lemma: Let
be an integer such that
. then
.
Proof: By hypothesis, we can find
such that
. It is a well known property of the minimal polynomial that there exists such a polynomial
with degree not exceeding
. We thus write
for some integers
. Then
However, the minimal polynomial of
has degree
, implying that the polynomial
is the zero polynomial. In particular the constant term is zero so
and the proof is complete. 
Returning to the problem, it follows that
and
. Thus
as desired and the proof is complete.

![\[ = \sum_{\substack{0 \leq k \leq n\\ p \mid k-s}} (-1)^k \binom{n}{k} = \frac{1}{p}\sum_{0 \leq k \leq n} \sum_{j=0}^{p-1} \omega^{(k-s)j} (-1)^k \binom{n}{k} \]](http://latex.artofproblemsolving.com/3/b/7/3b7a89b44a4134967a49d9db31ea46350d0f9345.png)
![\[ \frac{1}{p}\sum_{0 \leq k \leq n} \sum_{j=0}^{p-1} \omega^{(k-s)j} (-1)^k \binom{n}{k} =\frac{1}{p}\sum_{j=0}^{p-1} \sum_{k=0}^n(1- \omega^{(k-s)j} )^n.\]](http://latex.artofproblemsolving.com/a/f/2/af20e173508eaed6166096b047e2b81a7e905ede.png)
![$A= \{ f(\omega) \mid f \in \mathbb{Z}[X] \}$](http://latex.artofproblemsolving.com/7/c/2/7c2e66ca1709b9d8bb03316d4ded05505e3c81d3.png)



![\[ 1 = 1+ -px + \binom{p}{2} x^2 + \dots + px^{p-1} - x^p .\]](http://latex.artofproblemsolving.com/d/c/b/dcbf8e5a03ee9fa777379d7a82a21873f5811577.png)

![\[ 0= x^{p-1} + p(\text{stuff in $A$}). \]](http://latex.artofproblemsolving.com/c/2/1/c21cc133116e01ebaf11be4df10cf6587db67fab.png)





![\[\frac{1}{p}\sum_{j=0}^{p-1} (1-\omega^{-js})^n= \frac{1}{p}\sum_{j=0}^{p-1} x^{q(p-1)+r+1}\left(\sum_{l=0}^{-js-1} \omega^l \right) \]](http://latex.artofproblemsolving.com/7/6/b/76be230b6b255fd59e82b31cd4f49876a3f15419.png)


![\[ p^{q+1} \mid x^{q(p-1)+r+1}\sum_{j=0}^{p-1}\left(\sum_{l=0}^{-js-1} \omega^l \right) \in p^q.x.A. \]](http://latex.artofproblemsolving.com/0/d/2/0d2b2049296018fbe7b0694e9a90c48065d2fb06.png)

![\[ S=x^{q(p-1)+r+1}\sum_{j=0}^{p-1}\left(\sum_{l=0}^{j-1} \omega^l \right) = p^{q}x \cdot z \]](http://latex.artofproblemsolving.com/f/5/9/f59aa01668b5f26e7d3f7abafa07486cf43f4567.png)






Lemma: Let



Proof: By hypothesis, we can find
![$f \in \mathbb{Z}[X]$](http://latex.artofproblemsolving.com/5/4/f/54facbe33194718fef8ae34f1b3fa4ba94ca639b.png)



![\[ N = p^n (a_0 + a_1 \omega + \dots a_{p-2} + \omega^{p-2}) e\]](http://latex.artofproblemsolving.com/d/1/b/d1bda5b585965474669ff311b410c3ad6280bd46.png)

![\[ N- p^n (a_0 + a_1 \omega + \dots + a_{p-2} \omega^{p-2})=0 .\]](http://latex.artofproblemsolving.com/1/8/4/1845472a680a8287c2fc4e6b7670e62fb5a19aaa.png)





Returning to the problem, it follows that



This post has been edited 3 times. Last edited by HKIS200543, Aug 30, 2017, 10:37 AM