AoPS Academy
be a function satisfying the following conditions for all 
:![\[
\begin{cases}
f(n+1) > f(n) \\
f(f(n)) = 2n + 2
\end{cases}
\]](http://latex.artofproblemsolving.com/0/4/7/047e28c9d899d7de443ae40ac2c756fda851fafb.png)
Find the value of 
.
is the foot of the altitude from 
of triangle 
. On the lines 
and 
points 
and 
are marked such that the circumcircles of triangles 
and 
are tangent, call this circles 
and 
respectively. Tangent lines to circles and at and intersect at 
.
.
be an acute, scalene triangle, and let 
, 
, and 
be the midpoints of 
, 
, and 
, respectively. Let the perpendicular bisectors of and 
intersect ray 
in points 
and 
respectively, and let lines 
and 
intersect in point 
, inside of triangle . Prove that points 
, , , and all lie on one circle.
be a parallelogram with 
. A circle tangent to sides 
, 
, and 
intersects diagonal 
at points 
and 
with 
, as shown. Suppose that 
, 
, and 
. Then the area of can be expressed in the form 
, where 
and 
are positive integers, and is not divisible by the square of any prime. Find 
.
and 
intersect at points and . Line 
is tangent to and at and 
, respectively, with line closer to point than to . Circle 
passes through and intersecting again at 
and intersecting again at 
. The three points 
, , 
are collinear, 
, 
, and 
. Find 
.
, we know that lines and 
intersect at 
, lines and 
intersect at 
, and lines 
and 
intersect at 
. Suppose that the circumcircle of 
intersects line 
at and , and the circumcircle of 
intersects line at and , where 
and 
are collinear in that order. Prove that if lines 
and 
intersect at 
, then 
.
and 
are written on a blackboard, where 
and 
are relatively prime positive integers. At any point, Evan may pick two of the numbers 
and 
written on the board and write either their arithmetic mean 
or their harmonic mean 
on the board as well. Find all pairs 
such that Evan can write 1 on the board in finitely many steps.![\[ \dots, \; P_{-3}, \; P_{-2},\; P_{-1},\; P_0,\; P_1,\; P_2,\; P_3,\; \dots \]](http://latex.artofproblemsolving.com/a/c/c/acc097f524dc9fe9bd85e8eb659ea4a75aec475d.png)
in the plane with the following property: For any three distinct integers 
and 
, points 
, 
, and 
are collinear if and only if 
.
has no solutions in integers 
, 
, and 
.
are a solution and work mod 19. 
and 
so
,
, either 
or 
. Neither of these values is a square mod 19, so there is no solution and we are done.
. Since it worked, I didn't realize it was wrong at the time.
in the first system are those. Plugging them in gives corresponding values for , but plugging them in to the second equation produces no viable solutions for 
.
in a modular congruence , then you want to choose an such that 
. In this case, 
, so we choose 
because 
, and 
.
, it's less obvious.
in a modular congruence , then you want to choose an such that . In this case, , so we choose because , and ., it's less obvious.
is a perfect cube. In addition, 147 is odd, so both of those terms are even, so they must be divisible by 8. However, it is easy to check that neither one is (
).
by Fermat, so we have a contradiction.
" must denote a minus one. We now have:
for some a. This is a contradiction to Mihailescu's Theorem so we're done.
? 
and 
and then CRT them and show that the resulting 
congruences don't work?
has no solutions in integers , , and .
will easily solve the question since then 
which is clearly bigger than 
so it will give us a contradiction and well proving that is just by checking modulo 7 in the second equation
?
. Now you get that there exists nonnegative integers 
for which 
, which when solving the diophantine equation gives you some little solutions for (
) and also the corresponding values of , which are not very hard to check off using the second equation and small modulos(like 7 and 9).
?
where 
is an odd prime, then 
-th powers give exactly 
non-zero remainders mod .
, so ninth powers give only a few remainders (0,1,-1) and appears only in , so it is reasonable to take mod 19.
with 
, which must occur if 
. Remark that 
because 
fails. Observe that the only prime factors of 
are 
and 
. Observe that 
because 
if 
and 
does not divide any of 
. Remark that 
if and only if 
. Moreover,![\[\gcd(x+1,x^2-x+1) = \gcd(x+1,(-1)^2-(-1)+1) = \gcd(x+1,3),\]](http://latex.artofproblemsolving.com/6/c/7/6c760503ad4938608efc65cbeee42e691e88fc69.png)
so if did not divide 
it would have to be 
, as 
would be at least 
and therefore divisible by because it is not divisible by . This is absurd, so . By the gcd condition, we can write 
and 
for some integers 
and 
. Write![\[3\cdot 7^q = (3^p-1)^2 - (3^p-1)+1 = 3^{2p}-3^{p+1}+3.\]](http://latex.artofproblemsolving.com/a/f/7/af78c18802276e29ff7740921afa80819b2b7720.png)
This implies 
. Assume for now that 
. It is clear that 
because otherwise 
, absurd. But we also have 
by LTE. Thus 
. Remark that 
has derivative 
, so it is decreasing if 
. Moreover, the inequality does not hold at 
because we would have to have 
otherwise, which would be true if and only if 
. But in fact 
, so indeed the result does not hold for . For 
manually check, noting that at we get 
. Thus 
, so 
, meaning 
. This yields the one solution of 
. However, we did not consider the situation in which is negative or zero (in which case 
works). In that case, let 
and observe that for essentially the same reasons as before, 
must either have 
(which is a solution) or 
and 
. By the same machinations as before, we get 
. Again, we have . This time we remark that either (which yields no solution) or 
, meaning that 
. That is, 
. Again, 
by the argument from before, so 
because would be absurd. Again, note that 
cannot be in 
because then 
, absurd. If 
we get so 
and we do not have 
. Thus the possible values of are 
.
. It is clear that 
, so![\[z^9\equiv 157^{147}\equiv 22^{147}\equiv 22^3\equiv (-5)^3 \equiv -125\equiv 10\pmod{27}.\]](http://latex.artofproblemsolving.com/9/4/3/9431a216990a311aece9e639560b48bbb04f1ed0.png)
Since 
is not a -th power modulo 
, we are done.
? are all odd. (by subtracting the first equation by the second)
So 
and 
.
are even integers.
is not, which is a contradiction.
, so ![\[(x^3+y)(x^3+y+2)+z^9=147^{157}+157^{147}\]](http://latex.artofproblemsolving.com/8/1/b/81b0bad458be189f7d6fc50714b62988d84fb5ce.png)
. First, we have 
and 
.
.
.
.
. This is a contradiction because is not a QR mod .
.
. 
is not QR mod .
.
. 
is not QR mod .
We work in modulo . Note that 
(mod ) and 
(mod ). are 
, so the corresponding residues of are 
, since isn’t divisible by . Then we must have 
have corresponding possible residues of 
, yielding corresponding residues of 
as 
.
mod are 
, so we must have 
equivalent to 
mod , but since none of these are nonic residues, there are no integer solutions to our system, as desired.
. We can take both sides mod . We know that 
since 
. The right side can be found pretty easily mod 19: 
The quadratic residues mod 19 are 
. We can see that adding 
to any of these will not yield , so it is impossible.
We take mod 19. By FLT, the right side becomes 
, and we can compute 
so 
Therefore, we then have 
Since 
, we have 
. However, neither of 
are quadratic residues mod 19, so there are no solutions and we are done.
and 
.
and 
, which can be verified as 
. Also, 
and 
, 
and 
, then taking the second equation 
gives contradiction.
, 
and 
. Now we case bash for , with the powers of in each one of them and powers of taken 
.
and 
.
and 
. But this contradicts 
.
and 
.
and 
. But this contradicts .
and 
..
and 
..
and 
..
and 
.
and 
. But this contradicts .
and 
.
and 
. This works.
and 
..
and 
..
and 
..
and 
..
and 
..
and 
.
and 
. But this contradicts .
and 
.
and . But this contradicts .
and 
..
and 
..
and 
..
and 
..
and to check .
and 
. Now put this in the initial second equation and we now get a contradiction 
YAYY!!
.
.
, then 
.
, 
, it is not true.
. Adding the two equations, 
Now as 
, we must have 
. But none of these are quadratic residues.
but none of these are quadratic residues, contradiction, so there are no solutions.
![\[(x^3+1)(x^3+y)=147^{157}\]](http://latex.artofproblemsolving.com/7/2/5/72520ef6a9f252cf29e066312ea45d8dcfdb3dd0.png)
![\[(y+1)(x^3+y)+z^9=157^{147}.\]](http://latex.artofproblemsolving.com/5/6/3/563c5234b2bc5d0f7080df2921321e3d432e5843.png)
Since the latter is odd and and are integers, we have that must be even (because must be odd), meaning that 
. Since 
, we have that![\[(x^3+1)(x^3+y)=147^{157}\equiv x^3+y \equiv 1+y \equiv 3 \mod 8 \iff y\equiv 2\mod8.\]](http://latex.artofproblemsolving.com/b/2/8/b281285ac5cb57d4b560a67085b6c4a770599953.png)
Finally, note that 
. Since both and are mod 
, we have that is mod . Since![\[(y+1)(x^3+y)+z^9=157^{147} \iff (y+1)(x^3+y)+z^9\equiv5 \mod8 \iff 1+z^9\equiv 5\mod8,\]](http://latex.artofproblemsolving.com/0/6/b/06bfdde2ccc62173955f5eabb99f057bad754247.png)
this gives us that 
, which is impossible. This is because the equation implies that is even, however, if was even, that would mean that would be 
mod , a contradiction. Therefore there are no integer solutions to this system of equations, finishing the problem.
![\[(x^3+y+1)^2 + z^9 = 147^{157}+157^{147}+1\]](http://latex.artofproblemsolving.com/9/5/d/95d53b08bc9d94efecafab89a7967c8a23b29ea8.png)
![\[\implies (x^3+y^2+1)^2 \equiv \{13,14,15\} \pmod{19}.\]](http://latex.artofproblemsolving.com/1/b/b/1bb2782cc8b0573fdf945b7b532174979a28111b.png)
. 
to both sides to get
.
![\[(x^3 + y + 1)^2 + z^9 = 147^{157} + 157^{147} + 1\]](http://latex.artofproblemsolving.com/2/5/5/255f8babdde7f723fa8d63531076b506dad7d75f.png)
Taking the expression modulo results in![\[(x^3 + y + 1)^2 + z^9 \equiv 14\pmod{19}\]](http://latex.artofproblemsolving.com/5/a/6/5a68a0bf82a12e63e232c3a885e6612fb8916c6d.png)
Notice that All QRs of 
modulo 
are 
, , and .![\[(x^3 + y + 1)^2 + z^9 \equiv \{13, 14, 15\}\pmod{19}\]](http://latex.artofproblemsolving.com/1/7/d/17d65c908badf981ad3339b3b5e06f6988796eca.png)
None of these being a QR, so there are no solutions.
, in which case we can restrict to 
. Then we can calculate by hand the QR of which is 
. Then we can calculate that 
and 
. So we need 
which is clearly not possible.
and 
, but you also have 
left over. Thus, can we combine this into one expression? Yes! Let's try 
. Now, what modulo do we take? After testing classics such as 
, let's pick one such that 
is divisible by by FLT. Let's pick base !
. Thus, we get 
which is not possible.
to both sides gives 
but 
there are no solutions.
However, 
so it follows that 
However, none of these are quadratic residues mod 
so we are done. QED
.
.![\[\sum ab +\sum ab^2 \le 6\]](http://latex.artofproblemsolving.com/9/f/6/9f632ab1e6df5029bcd4416eb06623123ad2cd8c.png)
,
.
so we are done.
![\[(x^3+y+1)^2 = 147^{157}+157^{147}+1-z^9.\]](http://latex.artofproblemsolving.com/9/8/6/98655d1fcd1f6111de42f856328f52edd6d18ea7.png)
.
,
.
.