[/quote]
,
of 
touch 
at 
,
,
denote the line tangent to 
.
such that 
.
of 
.
be a cubic polynomial given by 
,
are integers and 
.
for infinitely many pairs 
of integers with 
.
has an integer root.
.
and determine all values of 
such that the minimum value is achived.
cities. The airline Starways wants to establish some one-way flights between pairs of cities in such a way that each city has exactly one flight out of it. Find the smallest positive integer 
such that no matter how Starways establishes its flights, the cities can always be partitioned into 
flights.
distinct circles in a plane, with radius 
.
circles, which form a set 
,
satisfy:
.
with incentre 
,
and 
by the midpoints of 
and 
respectively, and 
and 
be the feet of the altitudes from 
and 
the line being tangent tot he circumcircle of triangle 
,
the reflection of 
.
by the intersection of 
and 
be the intersection of 
and 
analogously. If 
is the intersection of 
and 
,
.
and 
.
.
and 
intersect at point 
,
is the point on segment 
such that 
.
is isosceles.
such that 
such that:
.
of positive integers with 
satisfying 
is
be a positive integer and let 
and 
,
and 
,
iff 
Y by anantmudgal09, rightways, Vietjung, adityaguharoy, Idio-logy, RedFireTruck, ImSh95, mathematicsy, megarnie, Mahmood.sy, Stuart111, Adventure10, Mango247, zhihanpeng, LP088
Let 
be a function satisfying
for all integers 
and 
. Show that there exist positive integers 
and 
such that 
for all integers .
Ankan Bhattacharya
be a function satisfying
for all integers 
and 
. Show that there exist positive integers 
and 
such that 
for all integers .Ankan Bhattacharya
satisfying
for all 
dividing some 
,
such that 
is maximal. Then there is some 
for all 
for all 
for any prime power 
.
and 
,
which proves the claim. 
But then
Thus, taking 
and 
for sufficiently large 
for some bounded function 
.
.
and assume that 
.
we have 
which is what we wanted to prove.
be a prime. Set 
is maximal, so that for all ![$$\nu_p\big(f(y)\big)=\min\big[\nu_p\big(f(x)\big),\,\nu_p(x-y)\big].$$](http://latex.artofproblemsolving.com/b/9/1/b912044599539fdbd5839619c8160faa5c05fa95.png)
It is immediate that all 
have maximal 
,
By the Chinese Remainder Theorem, there exists negative 
obeying 
,
and 
yields 
,
denote the assertion, as usual. Note that if 
is such a function, then 
works, too, so WLOG assume 
.
gives![\[\gcd(C, f(x)) = \gcd(C, x) \quad (\heartsuit)\]](http://latex.artofproblemsolving.com/3/c/4/3c413bb1adcbf12132e91337c53c044c72d46442.png)
so in particular if 
then 
which implies 
by maximality. Now let 
.
,
for some 
with 
by 
.
.
satisfying
and let 
so that 
and 
.
,![\[\gcd(f(x), f(y)) = \gcd(f(x), x-y) = f(x)\]](http://latex.artofproblemsolving.com/e/6/2/e620840a465ede69ea559cd868d701eda628d8a6.png)
implying 
and thus 
.
,
for all 
be the set of primes not exceeding 
.
,
and let 
.
,
.
.
of both sides and recall 
;
the latter being possible by Chinese remainder theorem. Then, from the claim we have 
for every 
,
and 
are examples satisfying the gcd equation (the latter always being strictly positive). Hence the hypothesis 
is essentially unique: every other pair is obtained by shifting 
the function 
Let 
with 
and 
Let 
so we need to show 
or 
(because 
)
or 
which is same as 
)
and 
. Now if 
then from 
we get 
and 
but 
so 
Then because 
we get 
which is wanted.
and choose 
is maximal. Then from the condition, 
so we have that 
(i.e, 
is maximized) if 
or 
.
Taking 
and 
,
as desired. 
![\[ \min(\nu_p(f(x)), \nu_p(f(y))) = \min(\nu_p(f(x)), \nu_p(x-y)). \]](http://latex.artofproblemsolving.com/0/9/a/09af19c9658a8ab8e4eb62301d75c36260d6df80.png)
Since 
such that 
is maximal, and call this value 
.![\[ \nu_p(f(y)) = \min(C_p, \nu_p(x_{p,max}-y)) = \min(C_p, \nu_p(y-x_{p,max}). \]](http://latex.artofproblemsolving.com/e/6/5/e65bc0474f004105100f0e09fcacd6cf2cf2edc3.png)
What we want is to find integers ![\[ \nu_p(f(y)) = \min(\nu_p(n), \nu_p(m+y)). \]](http://latex.artofproblemsolving.com/0/f/d/0fd6772dc6b4226a2ad1a15bd0af58ad7918d4c7.png)
So taking 
and 
works. But we want this single values for 
(since this constant value divides 
for all integers 
and 
works. So from now on assume 
The main claim is as follows-
.
for all 
.
,
,
such that 
for all 
be the integers such that 
is maximum as 
.
,
,
with 
,
Thus, we can form such a 
is maximum, and 
,
for all 
and 
with 
sufficiently large (so that 
)
is maximal. Then for any ![\[ \nu_p(f(y)) = \nu_p(x - y). \]](http://latex.artofproblemsolving.com/e/a/5/ea5ff8f156b4980c2350f5c6460ccfa38ec7ea12.png)
Taking 
and 
,
satisfy the desired. Realize that plugging in 
is the set of primes under 
be the maximum possible value 
,
and substituting 
,![\[\min \left(v_p(f(x_p)), v_p(f(t))\right) = \min \left(v_p(f(x_p)), v_p(x_p-t)\right)\]](http://latex.artofproblemsolving.com/9/b/3/9b3b1ece56c3ce79ee0bb027b8e88b167ed4ce6a.png)
![\[\implies v_p(f(t)) = \min(e_p, v_p(x_p-t)).\]](http://latex.artofproblemsolving.com/c/2/9/c29fb0c7e96a00d56942e790dcc81372c1743f69.png)
![\[m = -x_p \pmod{p^{e_p}} \quad \forall \quad p \in S, \qquad n = \prod_{p \in S} p^{e_p},\]](http://latex.artofproblemsolving.com/e/5/1/e5161e291a2b5bacf399145d894145d555431cea.png)
![\[v_p(\gcd(n, x+m)) = \min(v_p(n), v_p(x+m)) = \min(e_p, v_p(x-x_p)) = v_p(f(x))\]](http://latex.artofproblemsolving.com/3/6/5/3653fdbbd6cf40450be11854c2c839657f3d18e5.png)
and 
Consider 
such that 
is maximal. Also let 
.
Now a hint told me to use CRT because I'm bad. To finish note that we want to find 
over all primes 
over all 
for all 
our choices of 
such that 
is max for some given prime p. Let 
,
.
,
such 
for all integers 
such that 
is maximized. Note that if we fix 
,
for every positive integer 
for some integer 
is 
.
where 
is the maximal power of 
contained in 
be maximized for any prime 
.
for all 
,
.
By CRT we know such a positive integer 
,
denote the largest power of 
for some 
.
are congruent mod 
be integers for which 
,
.![\[\min(\nu_p(f(x)), \nu_p(f(y))) \geq k > \nu_p(x - y) = \min(\nu_p(f(x)), \nu_p(x - y))),\]](http://latex.artofproblemsolving.com/2/f/9/2f91579a9489da2820f77ea9591c8bd795feb9bb.png)
so our assumption was wrong. ![$a_p \in [0, P_p - 1]$](http://latex.artofproblemsolving.com/e/3/4/e3432d16c96a4b0daca1d44c5dadd5241f96326a.png)
for which all solutions of 
satisfy 
.
such that 
for all 
is a valid choice of 
.
and 
,![\[\nu_p(\gcd(m + x, n)) = \min(\nu_p(m + x), \nu_p(n)) = \min(\nu_p(x - a_p), \nu_p(n)) = \ell = \nu_p(f(x))\]](http://latex.artofproblemsolving.com/a/9/d/a9dd4a7cc14a56175377106910a7ff04731446cb.png)
from the fact that 
.
for all primes 
,
was fine. But after looking at hints, I realized this raises issues when some prime power dividing 
isn't actually in the range of 
,
,
We basically want to always have
.
and 
by CRT and we are done!
and 
be the maximum value it attains. We claim that 
and note that 
can be found by directly using the given equation. Note that 
Now note that with the given values of 
so we are done.
,
,
,
.
is maximized 
for each prime 
So by CRT there exists a negative value of 
such that for each prime 
is maximized. Now if 
then
So 
is the maximum value of 
for all 
as we have 
so 
.
such that 
.
but we have 
so this is just Bézout's identity.
and 
.
by definition, hence 
,
for all 
,
from where the choices 
and 
finish the problem.
![\[v_p(n) = \text{max}\{v_p(x)\}\]](http://latex.artofproblemsolving.com/6/8/e/68e21e5d8d5092c4c81039dbfb4eda47b31b9c97.png)
over all integers 
for all 
is finite for all 
.![\[\text{min}\{v_p(a-b), v_p(a)\} = \text{min}\{v_p(a), v_p(b)\}\]](http://latex.artofproblemsolving.com/b/6/c/b6ced51323cd2b3f84d2f55d938b7ea96b0dc103.png)
is 
,
and 
so 
,
.
,![\[\text{min}\{v_p(p^d(a' \cdot p^{c -d} - b')), c\} = \text{min}\{c, d\}\]](http://latex.artofproblemsolving.com/e/5/7/e57a2fe9802b5583a02d99d6e7ba21e328881ede.png)
which is equivalent to 
,
,![\[\text{min}\{v_p(p^d(a' - b')), d\} = \text{min}\{d, d\}\]](http://latex.artofproblemsolving.com/d/f/4/df4687a1654457638ff221d6942d74de021eb9df.png)
which is equivalent to 
,![\[\text{min}\{v_p(p^c(a' - b' \cdot p^{d-c})), c\} = \text{min}\{c, d\}\]](http://latex.artofproblemsolving.com/8/b/e/8be6920bbca7b4ab5dec0b69b6d722fa51e8df8d.png)
which is equivalent to 
,![\[\text{min}\{v_p(n), v_p(m + x), v_p(n), v_p(m + y)\} = \text{min}\{v_p(n), v_p(m + x), v_p(x - y)\}\]](http://latex.artofproblemsolving.com/8/8/2/8826fab498447b74b334644ca30e050f2f0209b4.png)
for all primes ![\[\text{min}\{v_p(m + x), v_p(m + y)\} = \text{min}\{v_p(m + x), v_p(x - y)\}\]](http://latex.artofproblemsolving.com/c/e/e/ceee9b3b141c1c2df3b01206bc2b37c9dd461207.png)
Setting 
,
denote the assertion
for all k.
where 
if 
for all 
since there must exist and solution to 
belongs in our set. We can take other values of 
and let 
.
.
.![\[\gcd(f(\ell+n),f(n))=\gcd(f(\ell+n),\ell) = f(\ell+n)\]](http://latex.artofproblemsolving.com/2/e/f/2efbc563f2ea7a7c5d3db779da4137a160bfc759.png)
which implies that 
.![\[\gcd(f(n),f(\ell+n))=\gcd(f(n),-\ell)=f(n)\]](http://latex.artofproblemsolving.com/d/9/7/d97ab668c9e5f0033cd1d78324825581171bc54c.png)
which implies that 
which in conjunction with the prior result implies that 
and extend the function to all of 
be the set of all primes dividing 
be the positive integer such that 
is maximal under the restricted domain.
,![\[\nu_{p_i}(f(x))=\min\{\nu_{p_i}(x-M_{_i}),\nu_{p_i}(f(M_{p_i}))\}\]](http://latex.artofproblemsolving.com/4/a/1/4a1e617d6bd590f2e9a27862b90478f1016fb5c8.png)
by the given condition,![\[\nu_p(f(x))=\min\{\nu_p(f(x)),\nu_p(f(M_i))\} = \min\{\nu_p(f(x),\nu_p{(x-M_i)})\}\]](http://latex.artofproblemsolving.com/d/4/3/d4331014509dda5b5b4e2edce324c90a8b5d26fe.png)
which implies that 
so the claim holds. Else, 
and in this case the given condition implies,![\[\nu_p(f(x)) = \min\{\nu_p(f(M_i)),\nu_p(f(x))\}= \min\{\nu_p(f(M_i)),\nu_p(M_i-x)\}\]](http://latex.artofproblemsolving.com/c/b/1/cb14a0c84de045f4438b0524898dc7f177158e4a.png)
clearly 
is impossible so it follows that 
and hence 
which finishes the proof of the claim.![\[\nu_{p_i}(M_i) = \max\{\nu_{p_i}(M_1),\nu_{p_i}(M_2), \dots , \nu_{p_i}(M_a)\} = \nu_{p_i}(\text{lcm}(M_1,M_2,\dots , M_a))\]](http://latex.artofproblemsolving.com/a/c/d/acd187e89fd83eb28116dd3b5b2be8a06d1a14c5.png)
Now, let 
across all 
and 
.
.![\[\nu_{p_i}(M_{p_i}-x) = \nu_{p_i}(x-M_{p_i}+(M_{p_i}+T)) = \nu_{p_i}(x+T)\]](http://latex.artofproblemsolving.com/8/8/6/88614eec065aacc0452e3112e807d3dcc85374eb.png)
as 
by nature of construction. And when 
we similarly have,![\[\nu_{p_i}(x-M_i+M_{p_i}+T) = \nu_{p_i}(M_i+T) > \nu_{p_i}(M_i)\]](http://latex.artofproblemsolving.com/4/e/c/4ec76ff9445608f331d81ee4a6a31f2fafe4863a.png)
as 
.
we have,![\[\min\{\nu_{p_i}(M_{p_i}-x),\nu_{p_i}(f(M_{p_i}) = \min\{\nu_{p_i}(x+T),\nu_{p_i}(f(M_{p_i}))\}\}\]](http://latex.artofproblemsolving.com/e/3/9/e39dc35afe278082a797b4c1c6ded935804c6036.png)
Now, by the Chinese Remainder Theorem we can pick 
which satisfies the prescribed congruence for each prime 
we provides us with a positive integer ![\[\nu_{p_i}(f(x))= \min\{\nu_{p_i}(x+T),\nu_{p_i}(\text{lcm}(f(M_1),f(M_2),\dots , f(M_a)))\}\]](http://latex.artofproblemsolving.com/8/7/d/87d8bb71ab48fb067079ca79d2b76e44afbb89b1.png)
which summing across all primes ![\[f(x) = \gcd(x+T,L)\]](http://latex.artofproblemsolving.com/5/5/c/55c43087f35dcd50c606cb844e7c306321cca981.png)
where 
are fixed positive constants as desired.
be all primes 
.
be 
and such a 
(where 
is the assertion) we get ![\[\nu_{p_i}(f(x))=\min(e_i,\nu_{p_i}(f(x))=\min(e_i,\nu_{p_i} (x-a_i))\]](http://latex.artofproblemsolving.com/3/8/8/3887c8ed9cc3f2908d32de5ff5dabb6f03f64b1f.png)
Now by CRT choose ![\[-m \equiv a_i+p_i^{e_i} \pmod {p_i^{e_i+1}} \iff \nu_{p_i}(m+a_i)=e_i\]](http://latex.artofproblemsolving.com/e/2/a/e2aba1808dd34790fc928c5fb0e88ea3b36b4200.png)
.
unless 
.
Let 
.
then 
,
.
then 
,
.
then 
,
And hence ![\[\nu_{p_i}(f(x))=\min(\nu_{p_i}(x+m),\nu_{p_i}(n)) \iff f(x)=\gcd(x+m,n)\]](http://latex.artofproblemsolving.com/4/d/c/4dc3b10eda0adb9719404f65d2b28b2ad6136ef1.png)
As required.
