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.
is written on the board. A move consists of adding either , 
or 
to the number written on the board, but only if the chosen number is coprime with the current number (for example, if the current number is 
, then in a move a player can't choose the number , but he can choose either or ). The player who first writes a perfect square on the board loses. Prove that one of the players has a winning strategy and determine who wins in the game.
of positive integers is called central if for every positive integer 
, the arithmetic mean of the first 
terms of the sequence is equal to .
of positive integers such that for every central sequence 
there are infinitely many positive integers with 
.
be a triangle. Let 
be a circle passing through 
intersecting 
at 
and 
at 
. Let 
be the intersection of 
and . Further, let 
and 
be the intersections of 
and 
with the tangent to 
at 
. Now, let 
be the second intersection of 
and . Then, prove that , , , 
and are concyclic.
+1 w
be a polynomial with integer coefficients such that 
, and let 
be an integer. Define 
and 
for all integers 
. Show that there are infinitely many positive integers such that 
.
table filled with natural numbers, we say it is a divisor table if:
-th row are exactly all the divisors of some natural number 
,
-th column are exactly all the divisors of some natural number 
,
for every 
.
is given. Determine the smallest natural number , divisible by , such that there exists an divisor table, or prove that such does not exist.
be an acute triangle with circumcenter 
. Points and are chosen on segments 
and 
such that 
. If is the midpoint of the arc 
and is the midpoint of the arc 
, prove that 
.
, 
, 
be non-negative real numbers, no two of which are zero. Prove that :
that, for all and positive real numbers 
, there is![\[\sum_{i=1}^n \frac{x_i^2}{\sum_{j=1}^i x_j}\geq C \ln n\left(\prod_{i=1}^n x_i\right)^{\frac{1}{n}}\]](http://latex.artofproblemsolving.com/4/8/b/48b9fc4af5a20de7fd9dfc45a74d5aa27e615e46.png)
squares with two game pieces. At the beginning, Alice’s piece is on the first square while Bob’s piece is on the last square. The figure shows the starting position for a strip of 
squares. can Bob ensure a win no matter how Alice plays? can Alice ensure a win no matter how Bob plays?
, 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.
such that 
coprime, 
and 
.
![\[
\text{Find all functions } f : \mathbb{R} \to \mathbb{R} \text{ such that:} \\
f(a^4 + a^2b^2 + b^4) = f\left((a^2 - f(ab) + b^2)(a^2 + f(ab) + b^2)\right)
\]](http://latex.artofproblemsolving.com/2/a/7/2a73a5e58eab4a994fbd83160fb79a0b00152951.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.