AoPS Academy
be an acute-angled triangle with circumcircle 
. A circle 
is internally tangent to at 
and also tangent to 
at 
. Let 
and 
intersect at 
and 
respectively. Let 
and 
be points on line such that 
is the midpoint of 
and 
is the midpoint of 
. Lines 
and 
meet at 
and intersect again at 
and 
respectively. The ray 
meets the circumcircle of triangle 
again at 
.
.
+1 w be a triangle and 
its circumcentre. A line tangent to the circumcircle of the triangle 
intersects sides at and at 
. Let 
be the image of under 
. Prove that the circumcircle of the triangle 
is tangent to the circumcircle of triangle .
be a semicircle with diameter and midpoint . Let be a point on different from and .
touches in a point , the segment 
in a point , and additionally the segment . The circle 
touches in a point and additionally the segments 
and .
and 
are perpendicular.
with no parallel sides is inscribed in a circle 
. Circles 
are inscribed in triangles 
, respectively. Common external tangents are drawn between 
and 
, and 
, and 
, and and , not containing any sides of quadrilateral . A quadrilateral whose consecutive sides lie on these four lines is inscribed in a circle 
. Prove that the lines joining the centers of and , and , and the centers of and all intersect at one point.
, 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.
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.