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.
integers are such that 
is prime and 
. Prove that there exists a positive integer 
such that 
.
attaining all positive values and positive numbers 
are given. Numbers 
satisfy
for every 
. Prove that there exists a positive integer 
satisfying 
.
+1 w
is described on a circle 
, and is not a trapezius inscribed in a circle. Let the tangency points of and 
be 
respectively. A circle with a center 
, different from is tangent to the segement 
and lines 
. A circle with center 
, different from is tangent to segment 
and lines 
. A circle with center 
, different from is tangent to segment 
and lines . A circle with center 
, different from is tangent to segment 
and lines . Prove that the lines 
are concurrent.
define 
be the product of first 
primes. Determine if there exists positive integers 
with the following property :![\[ m?=n(n+1)(n+2)(n+3) \]](http://latex.artofproblemsolving.com/4/5/c/45cb4a00f9395b8c6edb08a343c3bbd664916a4d.png)
be reals such that 
and 
Prove that
Let be reals such that and 
Prove that
Let be reals such that and 
Prove that
and a set 
consisting of 
disting positive integers smaller than 
are given. Prove that there exists a positive integer 
that can be written in the form 
, for 
in at least 
different ways.
and colors are given. We will say that a set of 
points on a plane is 
, if it contains exactly 2 points of each color and if lines connecting every two points of the same color are pairwise distinct. Find, in terms of the least integer such that: in every set of 
points of a plane, no three of which are collinear, consisting of points of every color there exists a subset.
?
be real numbers such that![\[a+b+c+d=-2\]](http://latex.artofproblemsolving.com/c/7/3/c73dff68dcdfbe4f6b6b2f52b378548e47193a16.png)
![\[ab+ac+ad+bc+bd+cd=0\]](http://latex.artofproblemsolving.com/9/f/4/9f450dcb150229ee76e3debdaceadddb4e451458.png)
is not greater than 
.
and distinct positive integers 
are given. Does there exist a polynomial ![$p(x)\in\Bbb{Z}[x]$](http://latex.artofproblemsolving.com/5/1/a/51a23efd70e495d2fe516b642f0a6e71e5875ba2.png)
of degree 
that satisfies the following conditions?
of positive integers such that
, and let be the order of 
modulo 
. Since divides 
, it must also divide 
. But as has order modulo , 
has to be a power of modulo (that is, the congruence 
is solvable). We conclude that is a power of modulo all sufficiently large primes. It is then a well-known result of A. Schinzel (proven easily with the Chebotarev density theorem) that must be a power of , which is the assertion of our problem.
be a set that intersects all (infinite) integer arithmetic progressions. If, for all 
, the set of prime divisors of 
is a subset of those of 
, then is a power of .
so read my problem in the FORUM, and try to use it!
Let's not be harsh with each other here, shall we? 
Perhaps you have already finished the proof from here, but anyway, here it goes:
, the 
take the form![\[
x_n = c_1\alpha_1^n + c_2\alpha_2^n + \cdots + c_s\alpha_s^n,
\]](http://latex.artofproblemsolving.com/0/4/7/04743752eab812abd56d628d82b8bc79d8b78782.png)
are pairwise different non-zero complex numbers, and the 
are (non-zero) constants. Hence, for every 
, we have the identity![\[
b^n - 1 = (a^n - 1) x_n = \sum c_i(a\alpha_i)^n - \sum c_i \alpha_i^n,
\]](http://latex.artofproblemsolving.com/4/6/c/46cb36c0590e4fa77a9e3bfa49bb502e397929db.png)
![\[ (*) \quad
b^n - 1^n - \sum c_i(a\alpha_i)^n + \sum c_i \alpha_i^n = 0 \quad \forall \, n>n_0.
\]](http://latex.artofproblemsolving.com/3/b/7/3b79321dc149e44d5b55b74d2f49c639286bf62f.png)
are pairwise different non-zero complex numbers and 
are constants satisfying 
for all , then 
. are assumed to be non-zero and 
, (*) implies that there is an 
such that 
, and there is a 
such that 
(otherwise, the coefficients of 
and of 
are 
and 
, respectively, and we get a contradiction with the above assertion). Furthermore, because the 
are pairwise different, every with 
must appear as some 
, and also conversely: each 
with 
must appear as some 
. We conclude that the following sets coincide:![\[
\big\{ \alpha_i \mid i \neq i_0 \big\} \equiv \big\{ a\alpha_j \mid j \neq j_0 \big\}.
\]](http://latex.artofproblemsolving.com/d/d/6/dd6bf6c247de9e7364f28a83e70da9c7873f64e5.png)
, it is easy to conclude from here that 
. Hence, 
is a power of (actually, it is 
), as claimed. QED
. With this post, let us end the off-topic, and continue posting regarding this indeed marvelous problem 
, there exist 
such that 
. For 
, for example, it is easily seen that if does not have the form 
, then there exists a prime such that 
, and taking 
contradicts 
. Try generalizing this idea for any .
was given at ROM TST /Taiwan TST 2006 (and you can guess that also somewhere else), it's natural to ask for the following generalisation, which is done by the same method:![$p,q \in \mathbb{Z}[X]$](http://latex.artofproblemsolving.com/f/9/6/f963c5991d9db42406d6dfa81653778c09e942e0.png)
with 
for all sufficiently big , then 
,
we have that for n sufficiently large 
, 
this implies that 
"
we have that for n sufficiently large , this implies that "
be any positive integer. We have
meaning that 
. is arbitrary and 
, it must be .
is solvable. We conclude that is a power of modulo all sufficiently large primes. It is then a well-known result of A. Schinzel (proven easily with the Chebotarev density theorem) that must be a power of .
, so it is solvable for every positive integer such that 
for a positive integer 
such that 
so there is a nonnegative integer 
such that 
but since 
, then we have 
that is our thesis.
, so it is solvable for every positive integer such that 
with 
and 
yields a 
with 
? An example such as 
show that the first two propositions do not imply the third: we have 
, but 
is not solvable.
is solvable for all coprime to any given 
, then is a power of .
-theory groups of algebraic number fields see http://arxiv.org/abs/0809.1991 and the references given there.
divides for infinitely many integers , then is a power of " is proved in the paper http://www.emis.de/journals/JTNB/2005-1/pages423-435.pdf
must be a power of , which is the assertion of our problem.
.
then 
. So (maybe a hard skill?) 
for large .
all solutions to![\[b^{\text{ord}_{p^k}(a)}\equiv 1\pmod {p^k}\]](http://latex.artofproblemsolving.com/9/c/e/9ce14ffdecd8c4edc62dad9b3404b5e101eca6fd.png)
are exponents of .
for primitive root 
and 
, then![\[f\cdot \text{ord}_{p^k}(a)=f\cdot \frac{p^k-1}{\gcd(e,p^k-1)}\]](http://latex.artofproblemsolving.com/6/c/8/6c8d82c0da0693673f6afcd4169ee7ba33a4086d.png)
is an integer, hence 
is necessary and sufficient, and yet this is equivalent to having 
for some . satisfies the equation in Step 2, there's always some 
which is divisible by . I find this hard to motivate, but it anyway implies![\[a^n-1\mid \prod_{e=0}^{n-1}(b-a^e)\]](http://latex.artofproblemsolving.com/6/4/a/64a57aace4f86e56e56a06c15f01ef1838ad9708.png)
where 
analysis is trivial (since 
are both odd). (Possible motivation: since will be divisible by and the product of the prime powers forms the odd part of , we have the LHS. But 
varies, so we should multiply together to get the RHS. I think you just have to push it and hope for the best.), and the RHS is fixed if we decrease , we might as well try to multiply together a bunch of irreducible polynomials (hopefully this step becomes more natural as I improve). So let's take the cyclotomic polynomials 
for 
. We should get![\[\prod_{t=1}^n \Phi_t(a)^{\lfloor \frac{n}{t}\rfloor}\mid \prod_{e=0}^{n-1}(b-a^e)\]](http://latex.artofproblemsolving.com/b/e/c/bec024a278cf24a23980de0b0479ad9333abacef.png)
and now the degrees match, and yet the RHS should be divided further by 
from Step 1. Hence the LHS has "larger" degree (grows faster) so the expression in the RHS is 
, meaning is a power of .
be integers such that for all 
we have 
. Then is a natural power of .
should grow like sum of 
for 
.
be distinct rationals, and let 
be real numbers. Then if there exists a sequence of integers 
so that ![$\lim_{k \to \infty} [ s_k - (c_1 x_1^k + c_2 x_2^k + \ldots + c_n x_n^k)] = 0$](http://latex.artofproblemsolving.com/5/7/3/5737c31956041ce16af14e360c401945ff56b653.png)
, then each 
with absolute value not less than 1 must be an integer.
for all 
. Let 
, and let 
. We induct on . When 
, let 
. Then
, so 
. But 
is always an integer, so we find that 
for all sufficiently large . Hence, for some and all nonnegative , 
, But 
is always a nonzero integer for sufficiently large (since 
is unbounded and 
converges), so we must have ., then it is also true for 
. Let 
. Then
Hence,![\[ \lim_{k \to \infty} \left [ (q_{n+1} s_{k+1} - p_{n+1} s_k ) -\sum_{i=1}^n (q_{n+1} x_i c_i - p_{n+1} c_i) x_i^k \right ] = \lim_{k \to \infty} \left [ q_{n+1} d_{k+1} - p_{n+1} d_k \right] = 0\]](http://latex.artofproblemsolving.com/3/3/e/33e26a399f7cc55289457949224c6a1daf254c3f.png)
,
and 
, we may apply the inductive hypothesis to find that each , 
, is an integer. By symmetry (e.g., by isolating 
instead of 
), we may conclude that is an integer as well.![\[x_n = \frac{b^n-1}{a^n-1} = \sum_{i=1}^{\log_a(b)}\left(\frac{b}{a^i}\right)^n + \mathcal{O}(\frac{b^n}{a^{n\log_a(b)}})- \frac{1}{a^n-1}\]](http://latex.artofproblemsolving.com/1/9/3/19388fbb6fe59dd0faaaa4a4ec0bb378f57cfb97.png)
so, we can use the lemma to conclude that![\[\frac{b^n-1}{a^n-1} = \sum_{i=1}^{\log_a(b)}\left(\frac{b}{a^i}\right)^n\]](http://latex.artofproblemsolving.com/8/0/9/809bb874117718305e4d22338bd71f512b382dfd.png)
and in particular 
, writing 
, we have that it is also true that 
for all . So we are done.
is the sum of some geometric progressions with ratio 
, then it will also satisfy a linear recurrence 
with the coeffiecients being of the integer polynomial 
. Say that the linear recurrence is![\[c_{j}y_{n + j} + c_{j-1}y_{n + (j-1)} + \cdots + c_0y_n\]](http://latex.artofproblemsolving.com/0/b/8/0b806d8b04420c715e821155d83704b866cda57c.png)
,
because eacher term in the parathensis tends to , we will have that will satisfy a linear recurrence and we are done in a similar way due to the lemma.
for 
, with 
, then we can show by induction that ![\[x^{(i)}_n = \frac{c_ib^n + c_{i-1}a^{n(i-1) + \cdots + c_{1}a^n + c_0}}{(a^{n+i-1} - 1)\cdots(a^n-1)}\]](http://latex.artofproblemsolving.com/7/4/1/74138d083af62dd99cee21e1d8b2092a53455b49.png)
for some contanst 
, so as soon as we reach a index with 
, we will have that 
, from where we can again conclude that , and we are done in a similar fashion to the first solution. and 
, then 
, this result can be shown by a very cunning usage of Gallagher's Sieve be a finite set of integers and 
a finite set of prime powers, let 
be a number such that 
if we have 
where 
. Then![\[|S| \le \frac{\sum_{p \in P} \Lambda(p) - \log 2X}{\sum_{p \in P}\frac{\Lambda(p)}{m_p} - \log 2X}\]](http://latex.artofproblemsolving.com/9/f/e/9fe5b91d7c94a63cddbef1e6570f57dc89423f06.png)
.
, and 
for some for every power of prime . Show that is a power of .
and 
are l.d (this is 
for some and 
). and are l.i. The idea is that there are a lot of number that are of the form 
smaller than some 
, but by Gallagher's that set is also small.
, then its cardinality is bounded below by 
.
to be the set of power of primes divisors of 
, then let order of in and also 
. Prove a technical lemma that states 
, then apply Gallagher's Sieve, this you get a contradiction, and it is possible to finish by standard number theory.
and 
Prove that
satisfying![\[\begin{aligned}
\begin{cases}
a+b+c+d=0,\\
a^2+b^2+c^2+d^2=12,\\
abcd=-3.\\
\end{cases}
\end{aligned}\]](http://latex.artofproblemsolving.com/8/b/1/8b1923e0303c0aa79332ee4540ee1885a9cf3f08.png)
then 
but how can we get 
?
?
was rather arbitrary.
one can get that 
.
This implies
Now some degree bounding would suffice, as 
so we can take out a bunch of 
actually has degree
Let 
then this sum is 
which is equal to the degree on RHS. However, observe that RHS is divided by 
for some constant C, while the left hand side generally has smaller growth (sometimes you take out prime factors, but they seem rather small) so we are done.