AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
be the number of complex numbers 
with the properties that 
and 
is a real number. Find the remainder when is divided by 
.
of 
, let 
be the sum of the elements of , with 
defined to be 
. If is chosen at random among all subsets of 
, the probability that is divisible by 
is 
, where 
and 
are relatively prime positive integers. Find .
with 
prime and ![\[a^p+b^p=p!.\]](http://latex.artofproblemsolving.com/f/e/b/feb27894b1f6497559eeb094cfe92256bc26688e.png)
be the incenter of triangle 
. Let 
, 
, and 
be the orthocenters of triangles 
, 
, and 
, respectively. Prove that the lines through , , and , parallel to 
, 
, and 
, respectively, are concurrent.
be the least positive integer for which 
is divisible by 
. Find the number of positive divisors of .
and 
have a common tangent that meets in 
and in 
. The two circles intersect at 
and where is closer to 
than . Line 
meets circle a second time in 
. Prove that 
bisects angle 
.
define a sequence of zeros and ones to be balanced if it contains zeros and ones. Two balanced sequences 
and 
are neighbors if you can move one of the 
symbols of to another position to form . For instance, when 
, the balanced sequences 
and 
are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set 
of at most 
balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in .
be a prime number and 
. Prove that![\[\left| p^m - (p - 2)! \right| > p^2.\]](http://latex.artofproblemsolving.com/2/1/c/21ca8bb6e5727d48b18b7ec3b127029c4c97694f.png)
Proposed by Miloš Milićev
, 
, with 
, 
. Prove that there exists 
such that for every 
![\[
f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.
\]](http://latex.artofproblemsolving.com/0/f/c/0fc36d9264eb7e103128c489aeae521a859c1fd4.png)
(For and , the notation 
represents 
. )
are non-negative real numbers and 
Prove that
such that 
is an integer for every positive integer 
fail: Just take 
and get 
is divisible by 
which implies 
This can only happen if is even. work: Substitute 
in place for in the problem; we then must prove that 
is an integer for all positive integers Call -good if satisfies this condition. Letting 
denote the number of not necessarily distinct prime factors of 
we will prove that all positive integers are -good by induction on 
The base case is trivial since if 
then 
which vacuously works. such that 
Let the prime factorization of be 
where 
are distinct primes and 
such that 
We will show that 
for all 
which finishes the inductive step by CRT.
so 
If 
then 
as well since 
Thus 
has a modular inverse modulo 
so we can say 
because is even. Hence the terms in this product for which 
contribute nothing to the binomial coefficient.
then we have 
Reindexing the product in terms of 
we get 
Therefore, plugging back into our sum gives 
By the inductive hypothesis, the sum on the right-hand side is divisible by 
so the entire sum is divisible by 
This completes our inductive step. are -good, and we are done.
" is 
.
we get 
so clearly is even. is even.
, then 
divides![\[
\sum_{i=0}^n\binom{n}{i}^k.
\]](http://latex.artofproblemsolving.com/2/9/e/29ef574279744f8e99496f7ec1a84b6b2550e5e6.png)
Proof. We proceed by induction on 
with the base case 
trivial.
. Let 
and let us work in 
. Note that if 
is even, 
exists so![\[
\binom{n}{r+1}=\frac{n-r}{r+1}\binom{n}{r}=\frac{2^\alpha m-(r+1)}{r+1}\binom{n}{r}=-\binom{n}{r}.
\]](http://latex.artofproblemsolving.com/a/b/d/abd2cc8dc5612dffb45ca2822f622f487ef31943.png)
We prove that 
for 
by induction on with the base case 
trivial.. We have
completing the induction step.
Since 
, by the induction hypothesis with 
, 
divides![\[
\sum_{r=0}^{n'}\binom{n'}{r}^k.
\]](http://latex.artofproblemsolving.com/5/1/b/51b7c7546b7a7185c3b7be2d20aabc8debbf820f.png)
Thus![\[
\sum_{i=0}^n\binom{n}{i}^k=2\sum_{r=0}^{n'}\binom{n'}{r}^k=0,
\]](http://latex.artofproblemsolving.com/5/7/f/57f07e0144c77a1846ac0753ba534ae4571b3e30.png)
as desired. 
case is the same except there is no 
in the proof. Since all prime powers dividing 
divide 
, divides . case correctly (I wrote a Claim 2 that was basically identical to Claim 1 but modified for odd ). Also by dropping the ^k, I did not induct on in Claim 1 because the last summation (wrongly) becomes directly.
for any arbitrary 
and didn't mention CRT? (I defined p-adic notation)
? I was in a hurry...
, find all positive integers such that this expression is a positive integer”
is a power of 
and all even positive integers otherwise
doesn't work, and 
works?
. To show that odd doesn't work, just look at . divides ![\[\sum_{i=0}^n \binom ni ^{2k}.\]](http://latex.artofproblemsolving.com/8/4/1/84139da2890840ac8fcb775b99ff1949182e57f8.png)
Pick a prime dividing , and let 
so that 
is the maximal power of dividing . Let 
with 
The key claim is as follows:
, we have that ![\[\sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k} \equiv p\sum_{i=0}^{\left\lfloor \frac{n}{p^{a+1}}\right\rfloor} \binom{n}{ip^{a+1}}^{2k}\bmod{p^{e-a}}\]](http://latex.artofproblemsolving.com/6/4/e/64e09c4d93130ccbac6a28690d36d4998540b31b.png)
![\[\binom{n}{0}^2, \binom{n}{p^a}^2, \dots, \binom{n}{(mp^{e-a}-1)p^a}^2.\]](http://latex.artofproblemsolving.com/e/0/9/e0917119b3286520109182ff9ecadcfb11b0d65b.png)
We claim that these values can be blocked into consecutive groups of such that the values in each block are equal modulo 
. Specifically, for 
, we claim that ![\[\binom{n}{ip^a} \equiv \binom{n}{(i+1)p^a} \pmod {p^{e-a}}.\]](http://latex.artofproblemsolving.com/b/3/b/b3be2f22ec29244f0062d3092a9fd47bbb0416ec.png)
Indeed, we have that
But for every 
, 
since . Therefore 
, so the entire product is equal to 
; thus the subclaim is true. Therefore we have that
and the claim is proven.![\[p^{e-a} \mid \sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k}\]](http://latex.artofproblemsolving.com/3/e/f/3ef54510be325f6a2cc9e38897d4bdfb0bb283b5.png)
for all 
. Taking 
gives that ![\[p^e \mid \sum_{i=0}^{n} \binom ni^k\]](http://latex.artofproblemsolving.com/2/6/9/2690bac952cb36989e8fa4576042c9e5bfd75a74.png)
for any prime power dividing . This means that ![\[\frac 1{n+1} \sum_{i=0}^n \binom ni^{2k}\]](http://latex.artofproblemsolving.com/9/8/9/989d213c9ec12273fc610b7739378dd28c7876be.png)
is an integer for any 
, so we are done.
(prime exponents are 1)
. Odd fail at .
and set 
. The main idea is that 
Then ![\[\sum_{i=0}^{pm-1}\binom{pm-1}i^k\equiv p\sum_{i=0}^{m-1}\binom{m-1}i^k\pmod{p^{s+1}}\]](http://latex.artofproblemsolving.com/a/8/e/a8ee4173684952aca3735bb1a1bc63a8db2c27a8.png)
so inducting on 
works.
.
for the sum in the problem.
is necessary. Choose . We need 
, which requires to be even.
for prime , since 
. Hence 
, and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to 
by an induction.
. When 
, we have ![\[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]](http://latex.artofproblemsolving.com/d/4/0/d405c93989cb8c5954041c054416c6e8be3ede52.png)
When 
, the 
terms of 
in order are, modulo , 
The point is that has five copies of 
, modulo . is a prime power which fully divides . Then ![\[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]](http://latex.artofproblemsolving.com/5/b/9/5b9bf0fdf09bc4cc62ba09107a7fdfa9f1252d18.png)
Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases 
first.
, since 
, we have ![\[ \binom{n}{i} = \frac{n(n-1) \dots (n-i+1)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \frac{(-1)(-2) \dots (-i)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \pm 1 \pmod{p^e}. \]](http://latex.artofproblemsolving.com/7/2/4/72446f7a23991dbd82dee8b7979f07b4b2efb0aa.png)
we have 
the analogous reasoning gives 
![\[ \binom ni = \prod_{0 \le j \le i} \frac{n-(j-1)}{j} \]](http://latex.artofproblemsolving.com/4/0/2/40265f398831b8703194076e28dccc1a58c1a94f.png)
then the fractions for 
are all 
. So only considers those with 
; in that case one obtains the claimed 
exactly (even without having to take modulo ). 
is a prime power which fully divides , then ![\[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]](http://latex.artofproblemsolving.com/2/7/5/2755a27d0a39a5f9cd5bfcafde0e955c5f86f484.png)
by grouping the terms (for 
) into consecutive ranges of length (by the value of 
).
. Realized this with 2 hours left and had to start over. 25AMO5 gave me the exact same feeling as 24JMO4. It took another 1:15 to solve correctly - easily the most stressful hour of my life. I measured my heart rate with roughly an hour left and it was at 50 beats / 20 seconds = 150 BPM.
., odd dies to ., let 
for 
, note that![\[\binom{n}{i}^{2m}=\binom{n}{0}^{2m}+\left(\binom{n}{1}^{2m}-\binom{n}{0}^{2m}\right)+\left(\binom{n}{2}^{2m}-\binom{n}{1}^{2m}\right)+\dots+\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/e/5/2/e52aea9ca81731dfbf3248ba89782270fa7606ea.png)
Now, summing this up over all 
, we have![\[\sum_{i=0}^{n}\binom{n}{i}^{2m}=(n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/4/2/4/424f73676e5567cfa5ad7780b81ae65f72947122.png)
![\[(n+1)\mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/a/b/d/abd2716339b8461b603b54a8d005136d98c6ebfa.png)
for all . However, note that since 
is even, we have that![\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right) \mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]](http://latex.artofproblemsolving.com/4/d/3/4d3d39f943654cf05ca324b0a0c4bff928f9aafa.png)
But we also have that![\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right)=(n+1-i)\binom{n+1}{i}=(n+1-i)\cdot \frac{(n+1)!}{(n+1-i)!i!}=(n+1)\cdot \frac{n!}{(n-i)!i!},\]](http://latex.artofproblemsolving.com/8/5/7/857929600c73ec3912ace293d5641cd2d936b066.png)
which is just 
. This is clearly divisible by , proving thatfor all .
, this means that![\[(n+1)\mid \sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/6/0/f/60f1c9ed14f96c9a010c1d74f1b44ac52d72bdff.png)
so![\[(n+1)\mid (n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right)=\sum_{i=0}^{n}\binom{n}{i}^{2m},\]](http://latex.artofproblemsolving.com/0/e/3/0e38b432759426919204494110c3382e85f4ad3c.png)
as desired. Therefore all even work, completing our proof.
. for the sum in the problem.
is necessary. Choose . We need , which requires to be even. for prime , since . Hence , and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to by an induction.. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo . is a prime power which fully divides . Then Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases first.
, since , we have we have the analogous reasoning gives then the fractions for are all . So only considers those with ; in that case one obtains the claimed exactly (even without having to take modulo ). is a prime power which fully divides , then by grouping the terms (for ) into consecutive ranges of length (by the value of ).
. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo .
, necessity follows from setting . Henceforth assume is even. be a prime power. Then 
.
, 
. Now we induct on 
. Suppose . Then 
where is some integer polynomials. Raising both sides to the power of , we have 
, as desired., prime , and nonnegative integer ,![\[p^e\mid\sum_{i=0}^{mp^e-1}\binom{mp^e-1}i^k.\]](http://latex.artofproblemsolving.com/f/9/2/f92881a8c87422cc07fad6a1bb55f4ea8b1ccc00.png)
. If 
, this is trivial. Now suppose it holds for . Working modulo 
, we have![\[(1-x)^{mp^{e+1}-1}=\frac{(1-x)^{mp^{e+1}}}{1-x}=\frac{(1+(-x)^p)^{mp^e}}{1-x}=\frac{1+(-x)^p}{1-x}(1+(-x)^p)^{mp^e-1}=(1+(-x)^p)^{mp^e-1}\sum_{i=0}^{p-1}x^i.\]](http://latex.artofproblemsolving.com/6/e/2/6e24dd0428cac6181d17e04c34a47131832b56ac.png)
Thus by comparing coefficients, 
for 
, 
. Therefore, modulo ,![\[\sum_{i=0}^{mp^{e+1}-1}\binom{mp^{e+1}-1}{i}^k=\sum_{q=0}^{mp^e-1}\sum_{r=0}^{p-1}\binom{mp^e-1}{q}=p\sum_{q=0}^{mp^e-1}\binom{mp^e-1}{q}.\]](http://latex.artofproblemsolving.com/4/1/6/416976281de08bc64838ff9bd3e1a6f892b1a9f0.png)
By the inductive hypothesis, the last sum is a multiple of , hence the first sum is a multiple of .
, then 
for any 
.
. Define 
and 
where 
and is maximal. Then 
.
, where 
. By maximality of , 
. Obviously 
, and we must have 
. Thus 
, all 
, and the desired follows by applying the Lemma. 
is odd is easy, so we assume is even and show the desired conclusion. ones lined up in a row. Then on step , multiply the central 
terms by 
. Obviously, we eventually construct the sequence of all binomial coefficients, and after step , the sequence will be
be the sum of the th powers of these terms after step . As a result, 
. We claim that is invariant throughout the process.
. Now define and where and is maximal. Further, let 
. By the Corollary, . Thus, we may set 
. Now
where division by was allowed because 
. Further, it is obvious that 
, so in conclusion, 
. 
is even as gives 
. Now, we show that all even work. Let .
is a prime power such that 
, then
th slot" as the fraction 
. Considering just the slots that are multiples of ,
, then the th slot is
so if the exponent is even, the slots that are not multiples of do not affect the residue mod at all, which shows the claim.
. Then, if , then by the above claim,
![$$\equiv p \left [ {\lfloor n/p \rfloor \choose 0}^{2m}+{\lfloor n/p \rfloor \choose 1}^{2m}+\dots+{\lfloor n/p \rfloor \choose \lfloor n/p \rfloor}^{2m} \right ] \pmod{p^r}$$](http://latex.artofproblemsolving.com/e/0/e/e0e5151a5440ee3e485bf33a2fa92fd2a2253d84.png)
's in the base representation of to show that implies 
. If there is one trailing , then clearly the above implies 
. Then, if has trailing 's, then 
has 
trailing 's. Thus, if 
, then , as desired.
implies , we are done.
if is a power of and all even otherwise.
, and let 
. Notice that by definition we have 
. Since , we have 
if and 
otherwise, so for each term, either both the numerator are divisible by , or neither are. Let be the number of terms in the denominator that are not divisible by ., we have 
, so 
. For each term such that , we can divide out a from both the numerator and the denominator. Notice that what's left is simply 
. Thus, we conclude that ![\[\boxed{\binom ni \equiv (-1)^M \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}}.\]](http://latex.artofproblemsolving.com/e/0/f/e0f2a107e53c8631fd3cf1210ade103d8fd64009.png)
even works for all : For 
, we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv p \equiv 0 \pmod p.\]](http://latex.artofproblemsolving.com/4/d/f/4df990e36b11b2a0f285995c194ed186b12ad2d6.png)
where 
, and suppose that 
satisfies the induction hypothesis for the prime . Clearly 
. Then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv p\sum_{i=0}^d \binom di^k \pmod {p^a}\]](http://latex.artofproblemsolving.com/5/9/4/594fb854a4626f0577e795c410495c3bd69db64b.png)
By the induction hypothesis, 
divides the inner binomial sum, so since we are multiplying it by , 
must divide 
. odd fails for 
: For , we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv 1 \pmod p.\]](http://latex.artofproblemsolving.com/2/8/0/280473e428505c0c672beb4b3b11e6a6bd0b5af0.png)
where , and suppose that satisfies the induction hypothesis for the prime . Since 
is even, there exists one more 
than 
for each block of such that 
remains constant. Then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv \sum_{i=0}^d \binom di^k \pmod {p^a}.\]](http://latex.artofproblemsolving.com/a/1/7/a178742010900bf910f7d1745ee31203de2ddfda.png)
By the induction hypothesis, does not divide this sum, so does not divide it either. odd works for a power of : Let 
. For 
, clearly odd work as 
. Now suppose odd works for 
. If we let 
, then we have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \pmod{2^{d+1}}.\]](http://latex.artofproblemsolving.com/0/f/f/0fff79199fa08d23fdd0637082ce55d76826612e.png)
such that remains constant, there is exactly one odd and one even . Thus, the sum simply vanishes 
. work for all primes , it follows by CRT that all even work. For not a power of , there exists an odd prime such that , which can be easily used to show that all odd fail.
We want to find all such that 
for all positive integers 
. Clearly, letting 
, we have![\[3\mid F_k(n,i)=1^k+2^k+1^k\]](http://latex.artofproblemsolving.com/8/d/f/8dfd2f126b81d6d01b3d76c271424f11deea5584.png)
which forces to be even. is even, . Let 
. First, we prove a claim.
for all 
.
is constant given that 
is constant. Therefore,![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\pmod {p^a}\]](http://latex.artofproblemsolving.com/b/3/a/b3a0d05cd82fa8c799929ed4c859a749601e2e1f.png)
We now continue to our second claim.
for all 
.
. Note that if 
this simply says 
which is trivially true. Now assume![\[f_k(n/p,i)\equiv f_k(n,ip)\equiv f_k(n,ip+p-1)\pmod {p^{a-1}}\]](http://latex.artofproblemsolving.com/6/6/f/66fd05865092ffade91f1d4eb3205daea1935a3e.png)
and we have
Which completes the induction step.
![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\equiv pF_k(n/p)\pmod {p^a}\]](http://latex.artofproblemsolving.com/2/6/8/26831e9aa39a05983a55035269e08c68ac9027d4.png)
so if 
then 
. By induction we are done.
is odd then fails, now if is even then from CRT all we need is to prove that 
.
) and some positive integer 
such that 
that:![\[ \binom{m \cdot p^{\ell}-1}{xp+y}=\left( \frac{(m \cdot p^{\ell}-1) \cdots (m \cdot p^{\ell}-p+1)(m \cdot p^{\ell}-p-1) \cdots )}{1 \cdots (p-1)(p+1) \cdots} \right) \cdot \frac{(mp^{\ell-1}-1) \cdots (mp^{\ell-1}-x)}{1 \cdots x} \equiv \pm \binom{m \cdot p^{\ell-1}-1}{x} \pmod{p^{\ell}} \]](http://latex.artofproblemsolving.com/7/8/5/7851252f0cde588fbcee11b8d01e91883dbb213d.png)
So now using this notice that we have 
so we can induct down and throw CRT until we get a degenerate case of the divisibility prompt in which case it is a trivial result thus we are done 
.
.
. To show that evens work, we will induct by taking mod 
, then CRT finishes.
.
. When 
it's obvious.
individually. Note that 
. Therefore, if 
, then both the numerator and denominator of 
are relatively prime, therefore it's 
. But since is even 
and it does nothing. So just ignore all with .
to 
we see that we multiply by 
, and this fraction is when and are relatively prime. So that eliminates all odd cases in general no matter which u picked as long as is prime (i just said n=2 because it takes less explanation). Because if it's odd then 
and it breaks but we need . and aren't relatively prime? from to make it easier because CRT duh that we picked and then it's easy to see we can use induction after shrink the binomial coefficient by on the top and bottom and aren't relatively prime, im simple minded lmao
.. Then we need 
which tells us should be even.
, then 
.. Base case is trivial.
works, let's prove 
works. Notice that 
It implies that 
Thus 
So it remains to prove that 
But still by the fact above 
And so we need to prove that 
And that is our induction hypothesis. The induction is done.
is divisible by every prime power of , it is divisible by and hence 
is an integer.
, using the fact that 
is an integer. Motivated by this observation, I tried evaluating the sum for other values of , but made no progress. Is it possible to solve the problem in this way?
, using the fact that is an integer. Motivated by this observation, I tried evaluating the sum for other values of , but made no progress. Is it possible to solve the problem in this way?
.
,or what we trying to show here :
,then applying our inductive hypothesis .
?
such that 
the equality hold for 
or 
or any
such that 
.
is a counterexample.
is a counterexample
.
is 
when ![\[n + 1 = {p_1}^{e_1} {p_2}^{e_2} \dots {p_m}^{e_m}\]](http://latex.artofproblemsolving.com/0/7/2/072b7b27e9b848aa52f090cae04c2e626f1e0745.png)
,![\[\sum_{i=0}^n \binom{n}{i}^k \equiv 0 \pmod{{p_j}^{e_j}}\]](http://latex.artofproblemsolving.com/4/7/b/47b249d90866951daffcc690a613580753a16d5f.png)
and let 
,
for convenience. We equivalently show that,![\[\sum_{i=0}^{cp^e - 1} \binom{cp^e - 1}{i}^k \equiv 0 \pmod{p^e} \text{ } \forall c, e \in Z^{+}, \text{ prime } p\]](http://latex.artofproblemsolving.com/e/7/0/e70b87cd706c076659737ef7894f9eb4c5eb2181.png)
.
.![\[\binom{cp - 1}{0}^k \equiv \binom{cp - 1}{1}^k \equiv \dots \equiv \binom{cp - 1}{p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/b/e/5/be57d1808f2d338dabf42dbd10f687a913c2875e.png)
![\[\binom{cp - 1}{p}^k \equiv \binom{cp - 1}{p + 1}^k \equiv \dots \equiv \binom{cp - 1}{2p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/1/2/4/12473d0589cf7ce16ae369f4cb7ad47ac840945c.png)
![\[\binom{cp - 1}{2p}^k \equiv \dots \equiv \binom{cp - 1}{3p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/7/5/f/75f83b068c379c7b1b74e5f4d54a4d44859a9262.png)
![\[\dots\]](http://latex.artofproblemsolving.com/1/6/7/16762e47f22f53e2431935f211fa82570b46b6cb.png)
.
,
and 
so,
![\[\iff (-m - 1)^k \equiv (m+1)^k \pmod{p}\]](http://latex.artofproblemsolving.com/d/9/0/d9081f5f4c24440ec653d2c7c12ce7aef2e0f29e.png)
when 
.![\[\binom{cp - 1}{0}^k + \binom{cp - 1}{1}^k + \dots + \binom{cp - 1}{p - 1}^k \equiv p \binom{cp - 1}{0} \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/6/3/9/639c1c04909eec39a20399fa49976322b126ac4f.png)
![\[\binom{cp - 1}{p}^k + \binom{cp - 1}{p + 1}^k + \dots + \binom{cp - 1}{2p - 1}^k \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/8/b/2/8b2b6f369c3ee0dd36ecc9779c58826468dc32d4.png)
for 
.![\[\binom{cp^e - 1}{0}^k \equiv \binom{cp^e - 1}{1}^k \equiv \dots \equiv \binom{cp^e - 1}{p - 1}^k \pmod{p^e}\]](http://latex.artofproblemsolving.com/2/9/7/29796414db0736f91d253d135ec1d575352f150e.png)
![\[\binom{c^ep - 1}{p}^k \equiv \dots \equiv \binom{cp^e - 1}{2p - 1}^k \pmod{p^e}\]](http://latex.artofproblemsolving.com/5/6/6/5663c861c24e7ea2d1ffe5be2d2eb47afc99351d.png)
is still true when ![\[\sum_{d = 0}^{c p^{e-1} - 1} \binom{c p^e - 1}{dp}^k = \frac1p \sum_{d=0}^n \binom{cp^e - 1}{d}^k \equiv 0 \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/a/f/b/afbeb0d30087f7c107581d4a5e3b64ad4bcdd22d.png)
![\[\binom{c p^e - 1}{dp}^k \equiv \binom{c p^{e-1} - 1}{d}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/1/6/3/163e50724176a67f6cefd150406f5f99aa0d81a3.png)
.
.
.![\[\binom{c p^e - 1}{dp}^k \equiv \dots \equiv \binom{c p^e - 1}{(d+1)p - 1}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/2/7/2/272a4129b591aa0cff79714f3923cb1f21adf9d3.png)
![\[ \frac{ \binom{c p^e - 1}{(d+1)p}^k}{ \binom{c p^e - 1}{(d+1)p - 1}^k} \equiv \left( \frac{cp^e - (d+1)p}{(d+1)p} \right)^k \]](http://latex.artofproblemsolving.com/2/8/4/2842111ae65017069ea95132191affc600351a32.png)
![\[\equiv \left( \frac{cp^{e-1} - (d+1)}{d+1} \right)^k \equiv \frac{\binom{cp^{e-1}- 1}{d+1}^k}{\binom{cp^{e-1}- 1}{d}^k} \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/0/1/4/014d5c7eda7b52d0fdeec607818f68057c55a78e.png)
we have 
as desired.![\[\sum_{d = 0}^{c p^{e-1} - 1} \binom{c p^e - 1}{dp}^k \equiv \sum_{d=0}^{c p^{e-1} - 1} \binom{cp^{e-1} - 1}{d}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/4/5/3/4531c8d747bc33161477b85a07e529ff85d873bf.png)
![\[\sum_{i=0}^n \binom{n}{i}^k \equiv 0 \pmod{n+1}\]](http://latex.artofproblemsolving.com/2/d/0/2d048f281c4a0e47cb11a4e9510a12a6827e0bb2.png)
gives the integer 
.
which has roots
Let
From Newton's identities,![$$s_{k} = (-1)^{k-1}k[x^{k-1}]P + \sum_{i=1}^{k-1} (-1)^is_{k-i}[x^i]P.$$](http://latex.artofproblemsolving.com/e/6/f/e6f84a3fd0237d7d5bd1db526637a8854f0fc061.png)
However, ![$[x^i]P = 0$](http://latex.artofproblemsolving.com/f/1/b/f1b8d40ace3297179d867f0694eb92cd623dbf6a.png)
for odd ![$$s_{2k} = 0 + \sum_{i=1}^{k-1} s_{2k-2i}[x^{2i}]P\equiv 0\pmod{n+1}$$](http://latex.artofproblemsolving.com/0/d/3/0d3ccf4a6aee60d9a49561e546584b99f445d255.png)
by the inductive hypothesis. Thus, all even