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.
, where 
. Verify by direct substitution that 
satisfies the quadratic equation 
and deduce that the value of is 
.
. Show that 
, show that the value of 
is 
.
be vertices of regular pentagon inscribed in a circle whose radius is 
and center is at 
. Find all possible values of 
are integers whose greatest common divisor is 1. Let 
be a set of integers with the following properties:
, 
.
(not necessarily distinct), 
.
, if 
, then 
. must be equal to the set of all integers.
.
, there exist indices 
such that 
is divisible by .
, find the minimum possible value of 
.
be a quadrilateral circumscribed about a circle, whose interior and exterior angles are at least 60 degrees. Prove that![\[
\frac{1}{3}|AB^3 - AD^3| \le |BC^3 - CD^3| \le 3|AB^3 - AD^3|.
\]](http://latex.artofproblemsolving.com/5/5/e/55ee0fba8392ee81b7b37da45d99755ea6d6754a.png)
such that 
for all 
with parallel sides 
and 
, assume that there exist points 
on line 
outside segment , and 
inside segment 
such that 
. Denote by 
the point of intersection of and 
, and by 
the point of intersection of and . Let 
be the midpoint of segment , assume it does not lie on line . Prove that belongs to the circumcircle of 
if and only if belongs to the circumcircle of 
.
with an area of 
, with 
. If 
, Hence find the value of 
.
, let 
. Find the smallest such that 
.
where 
and 
defined as
is given by
denotes the number of points of intersection between the curves
as
is
Number of subsets of 
whose sum of elements is divisible by 
![$f(x) \in \mathbb{F}_p[x] - \{0\}$](http://latex.artofproblemsolving.com/f/6/4/f64f3f1429a6b9392a90365d58cd3675c94309c4.png)
let 
denote its multiplicity at 
so 
for some ![$g(x) \in \mathbb{F}_p[x]$](http://latex.artofproblemsolving.com/0/e/b/0eb87f8c2b36ee7477413a22a212c0f97abd1957.png)
with 
. If 
mod , then 
by the product rule. We are asked to compute 
.![$f_n := \sum_{k=0}^{p-1} k^n x^k \in \mathbb{F}_p[x]$](http://latex.artofproblemsolving.com/2/0/d/20da9a0fe29a78cc742daa7aa47e4a02e8862e15.png)
. Then 
using the fact that 
in ![$\mathbb{F}_p[x]$](http://latex.artofproblemsolving.com/e/5/a/e5a21492095c9116b100e2f7626a70cc26834e82.png)
. Since 
it follows that 
for 
. In particular 
.
, which is way neater. Here's a solution that repeats the above, i.e. 
and as usual we find the smallest with 
. Finding derivative term wise, get
(some explanation needed as 
could go to 0. We can now write the above in terms of the following polynomial:
and
Now for 
each term 
(primitive root argument), which means the sum will be 
for 
. For 
, only 
is left and
but 
is the coefficient of the monic polynomial 
, hence equal 1, so 
for .
, we have that![\[
(*) \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell}a_k = 0.
\]](http://latex.artofproblemsolving.com/e/e/c/eecc79ec6fa7030f90ce952e575b269b890fce1d.png)
Indeed, the above sum can be written as![\[
\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} - \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell}.
\]](http://latex.artofproblemsolving.com/f/6/9/f692e16f90d4a3037127cc0ed9072766cd1f4f31.png)
But we have that![\[
\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} + \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell} = \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0.
\]](http://latex.artofproblemsolving.com/9/3/4/934fa7207cc14043cc9c53588c32a89d06788c4c.png)
To see this, take some 
with 
, which is possible as 
, to see that![\[
\sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = \sum_{k\in \mathbb{F}_p^{\times}}(\alpha k)^{\ell} \implies (1 - \alpha^{\ell})\sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0 \implies \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0.
\]](http://latex.artofproblemsolving.com/2/7/7/277dce0ce833132f26b5a65ecfb491991d1db38e.png)
Thus, we have that![\[
\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} - \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell} = 2\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} = \sum_{m\in \mathbb{F}_p^{\times}}m^{2\ell} = 0,
\]](http://latex.artofproblemsolving.com/2/a/f/2afcb8000fe3594fec4dd7bda01741cff084576b.png)
as 
, so we can use the trick of taking some with 
as above, thus establishing 
.![\[
\sum_{k = 1}^{p - 1}a_kx^k.
\]](http://latex.artofproblemsolving.com/3/9/6/396bf7db0ab965bedfef966ff32716814bfc9d74.png)
Note that this polynomial always vanishes at 
by taking with 
. Suppose we take 
derivatives of this expression and evaluate the result at 
. The result will be![\[
\sum_{k = 1}^{p - 1}k(k - 1)\cdots k(k - \ell + 1)a_k.
\]](http://latex.artofproblemsolving.com/4/3/9/4399c0ed0849c089ec06d1f8f8d789245664b13c.png)
But we can expand out 
as some polynomial in 
with integer coefficients and degree 
. Thus, as long as 
, this expression will vanish by repeatedly applying (*). Thus, 
divides our polynomial for . To see that 
does not divide our polynomial, it suffices to show that![\[
\sum_{k\in \mathbb{F}_p^{\times}}k^{\frac{p - 1}{2}}a_k \neq 0,
\]](http://latex.artofproblemsolving.com/4/3/9/43907045efe3ac712ade8349f4cb9073336a865e.png)
by expanding out 
as a polynomial in and applying to all . But this sum is just![\[
\sum_{k\in \mathbb{F}_p^{\times}}k^{p - 1} = p - 1\neq 0. \text{ }\square
\]](http://latex.artofproblemsolving.com/b/2/a/b2ac288a6687e1cb8e4c1183f6af29d735ef02d1.png)
and denote 
. Then 
. For 
, the multiplicity of 
in 
is 
.
th moment of 
for 
is . There are a few different reasons this is true: (number theory) plug in a primitive root and use geometric series, (group theory) the sum is a multiple of the sum of a subgroup with zero sum, (algebra) use Newton sums on the polynomial 
. as a root has degree 
, the sum of the polynomial over is .
th derivative; we get![\[
q^{(j)}(1)=\sum_{a\in\mathbb{F}_p}a^{\frac{p-1}{2}}a^{\underline{j}}
\]](http://latex.artofproblemsolving.com/1/1/c/11c73e7c442ea433e0f761131379f94f4bfc3c57.png)
where 
is the falling factorial. When 
, this is by the corollary. When 
, the corollary implies that![\[
q^{(j)}(1)=\sum_{a\in\mathbb{F}_p}a^{p-1}=-1.
\]](http://latex.artofproblemsolving.com/4/a/2/4a29600ea727d2835ba75bea8def1af7bb25186f.png)
So the first 
derivatives of 
at (a root of ) are , so has multiplicity 
in .
. Let 
denote the th derivative of 
. We have the following well known lemma.
. Then 
if and only if 
for all 
. in the form ![\[q(x)=b_0+b_1(x-1)+b_2(x-1)^2+\cdots+b_{p-1}(x-1)^{p-1}.\]](http://latex.artofproblemsolving.com/c/9/d/c9d3361ee17038dda6bdf14e2be652028b32b349.png)
In this setting, it's clear that if and only if 
for all . Differentiating times, we see that 
, and since 
, we thus have 
, so the result follows. 
![\[q^{(m)}(1)=\sum_{k=m}^{p-1}k^{\frac{p-1}{2}}k(k-1)\cdots(k-m+1)=\sum_{k=0}^{p-1}k^{\frac{p-1}{2}}k(k-1)\cdots(k-m+1).\]](http://latex.artofproblemsolving.com/c/2/c/c2c87e590c58c3bdd4ed014a8420d02fda84c0d8.png)
To evaluate this, we have the following useful lemma.
, we have ![\[\sum_{k=0}^{p-1}k^r=0.\]](http://latex.artofproblemsolving.com/a/b/2/ab2013a6cb27c81c12c48265ce99f41753f9e927.png)
Recall that we are working over .
be a primitive root mod . Then, the sum is ![\[\sum_{\ell=0}^{p-2}(g^\ell)^r=\sum_{\ell=0}^{p-2}=\frac{(g^r)^{p-1}-1}{g^r-1}=0,\]](http://latex.artofproblemsolving.com/f/b/b/fbb17c033ef9b33d5bb0f5087a3899223de523aa.png)
which works since 
, due to 
. for 
. It also implies that ![\[q^{\left(\frac{p-1}{2}\right)}(1)=\sum_{k=0}^{p-1} k^{p-1}=p-1\ne 0,\]](http://latex.artofproblemsolving.com/b/d/d/bdd7391f24dddcdad3265776484390ac697c10c4.png)
so the maximal such that is 
by lemma 1.
. The rest is calculus: the formula for a geometric sum, the fact that 
applied to 
gives 
, and the fact that if a multiplicity of a root is not zero in our field then it decreases by 1 when you differentiate. Nothing else is needed for the proof.
can be written as 
. Starting with 
and its multiplicity 
, keep applying until you reach and its multiplicity.
as claimed.
, and 
. Suppose is such that 
, \dots, 
has as a root, but 
does not have as a root. Then is the multiplicity of in .
will have multiplicity of one less than in 
. ![\[ q_n(1) = \sum_{k=1}^{p-1} k^n \left( \frac kp \right) = \sum_{k \text{ qr}} k^n - \underbrace{2 \sum_{k=1}^{p-1} k^n}_{=0 \text{ for } n < p-1} \]](http://latex.artofproblemsolving.com/4/5/7/457aecd2ddad136f776ddd63b41734bcef79e89d.png)
Let be a primitive root modulo . The first sum then equals ![\[ g^0 + g^{2n} + g^{4n} + \dots + g^{(p-3) n} \]](http://latex.artofproblemsolving.com/2/6/d/26d3188991610e724115d4027f57a63aa4f2dfda.png)
which equals if 
but 
otherwise. as claimed.
and let 
Additionally, define 
inductively by 
and 
To show that the sums on top evaluate to 
induct from left to right; the base case follows from the fact that the number of nonzero QRs and QNRs are equal.th sum from the left. By the inductive hypothesis, we may shift to obtain 
Therefore, since 
is a polynomial of degree 
it suffices to show that 
precisely when 
so we are done.
. Notice that including all terms with negative powers that evaluate to zero, the th derivative of is equal to 
In particular, for 
, we can always split this into sums of the form 
for some 
and 
. All these sums evaluate to zero modulo , hence 
.
, the leading term has exponent , and the sum 
evaluates to 
, and hence the process terminates. It follows by the definition of derivative that the multiplicity of in is .
.
such that
, we can explictly write 
as
we have
over 
vanishes mod unless 
.
, everything is degree less than , and the constant terms are the same, so everything vanishes. However, when , the first sum has a non-vanishing component 
, so it will not be zero as everything else vanishes. Thus, fails and we are done.
. so that 
. Then notice we can write 
as a sum of 
. In particular to preserve degrees the last term is added once. Thus the first time 
is the same as the first time 
. However, the idea is that we can rewrite this as 
which equals 
so if this is 
then we must have 
so 
. In fact for this we get 
as desired.
times. We are left with ![\[P(x) = \sum_{k = 1}^{p - 1}\frac1{k}x^k\]](http://latex.artofproblemsolving.com/7/3/8/73820e0e41295b91e9b80fbbd2440789e239aea8.png)
. Plugging in 
we get that the sum is diviisble by 
Differentiate one more time and we get ![\[\sum_{k = 1}^{p - 1}x^k = \frac{x^k - 1}{x - 1}\]](http://latex.artofproblemsolving.com/5/0/f/50ff7e0712b4141ca548defe74287312bccc26eb.png)
which obviously has 0 powers of This implies that there are exactly 
factors of 
in the original expression.
.
![$q(x) \in \mathbb{F}_p[x]$](http://latex.artofproblemsolving.com/2/4/e/24e574b86f85cc81ad02b34d6d4ec576a53a95ae.png)
be given by 
where 
mod 
divides 
in the problem is irrelevant. If you replace it by another positive integer 
then the answer is simply 
.
.
is a non-zero constant.
.
denotes congruence modulo 
if 
and 
for the set of residues and nonresidues modulo 
.
derivative of ![\[
q^{(n)}(1) = \sum_{r\in\text{QR}}\frac{r!}{(r-n)!} -\sum_{b\in\text{QNR}}\frac{s!}{(s-n)!}.
\]](http://latex.artofproblemsolving.com/0/2/1/021fa2df6d57a642373e43754119cfffc6421352.png)
We show that this is zero for 
by a showing the lemma:
for polynomials of degree less than ![\[
\sum_{r\in\text{QR}} r^n = \sum_{s\in\text{QNR}} s^n = 0
\]](http://latex.artofproblemsolving.com/b/3/4/b34a9f7b610397a13dd1af91b1c794e5741b66e5.png)
.
.
for a primitive root 
,
,
.
.
.
derivatives is simply the sum of an 
.
.
.
.
such that
.
when the denominator 
.
,
and 
for 
.
when 
or when 
.
.
for 
,
.
,