AoPS Academy
be a triangle with orthocenter 
and let 
be the midpoint of 
Suppose that 
and 
are distinct points on the circle with diameter 
different from 
such that lies on line 
Prove that the orthocenter of 
lies on the circumcircle of 
such that if 
and 
are distinct rational numbers satisfying 
or 
, then 
? Justify your answer.
and the leaf to the right with 
. It seems to work.
for some 
where 
for all 
. From now on this will be denoted as ![$ [a_0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/1/c/4/1c47e13850fd92c24cf30707900dc53e12c32418.png)
.
, let 
. Then let 
and for all 
let 
. I claim that this 
satisfies the desired properties. To prove this, consider two rational numbers 
.
If 
then by definition 
as desired.
If 
and 
then by definition as desired since 
.
If and 
then to prove that it suffices to show that 
. Let ![$ -x = [a_0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/1/0/e/10e2dcb8e4ad502ecb43d7e1c2744f3995658d81.png)
. Then ![$ y = [a_0 + 1; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/2/c/e/2ce601c354188bdad5e03d9833f5a0efd26eb275.png)
and so 
as desired.
If and 
we can let ![$ y = [0; 1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/e/6/b/e6b1ac208f52b35a47ba274b63b6aede8c05b3b5.png)
so that ![$ x = [0; a_2 + 1, a_3, \dots, a_m] $](http://latex.artofproblemsolving.com/5/c/a/5ca981e9723d9f4c0ee0a619a2f05b17f18fee09.png)
so 
and 
which implies that as desired.
If 
, we can assume WLOG that 
. Then letting ![$ x = [0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/f/a/4/fa41f1dfed52008255c6fe47ad8f150591dc820c.png)
we have that ![$ y = [a_1; a_2, a_3, \dots, a_m] $](http://latex.artofproblemsolving.com/1/6/6/166a8243036f6a8f2362c13f93282945d869aff5.png)
so 
and 
which implies that as desired.
. Anyway, here's my solution: For two integers 
, let 
denote the number of steps taken in the Euclidean Algorithm to find 
. In other words, if we let 
and write the system of equations 
then 
where 
. Then we claim that the following function works-
for 
and 
for 
for 
with , 
when 
. For 
and 
, this easily follows from the definition, so we can ignore these cases. WLOG assume 
and suppose 
for some 
with 
. Then from property 3 of our function, we have 
and 
. Since 
so it suffices to show that 
for 
.
for , and first suppose 
. We have 
But, as 
, so the first step of our Euclidean Algorithm while finding 
will be 
. So 
. Also, using 
, we get 
. Thus, we have 
Thus, for 
we have . Finally, if 
then 
and 
. Since 
, then the previous result gives 
. Combined with the above equalities, we get . Thus, the result is true for all 
.
for 
. For 
, the result is true by definition. And for 
, by the above result, we have 
which directly gives the desired property.
when 
. Since 
(proved before), so it suffices to show the result for positive . Also, WLOG we can take 
, and write with 
and 
. Then 
But, while finding 
we simply start from the second step in the Euclidean Algorithm to find . So we have 
. This gives us 
Thus, we have as desired. 
is that 
, which we can manually enforce at the end. Thus, we assume that the inputs to 
are nonzero rationals.
where 
and 
. We set ![\[s(x) = \begin{cases}1 &\text{if } (a^{-1}\mod b)\le b/2 \\ -1 &\text{if } (a^{-1}\mod b)>b/2.\end{cases}\]](http://latex.artofproblemsolving.com/2/7/e/27e64eb277458c6bc8cbe17ca29ebb109bc722d2.png)
From this definition, it is clear that 
and 
, so it suffices to show that 
. Since we know is odd, it suffices in fact to show for .
are relatively prime positive integers, then ![\[a\cdot(a^{-1}\mod b) + b\cdot(b^{-1}\mod a) = ab+1.\]](http://latex.artofproblemsolving.com/b/5/a/b5a225156975a80139966b83b5c971e5a88c9bbc.png)
be the left side of the above equation, we see that 
and 
, so 
since .![\[a+b\le T\le a(b-1)+b(a-1)<2ab,\]](http://latex.artofproblemsolving.com/6/c/e/6ce6d2e84ed2e9ff81a63c24ce53b9e60861da84.png)
so we must in fact have 
, as desired. 
if and only if 
, which implies that 
..
on the positive rational numbers to be the number of terms in the continued fraction of . Then let 
and . Then, clearly . If 
and 
then 
and therefore 
, so 
.
. WLOG, 
. If 
then ![$x=[0;1,a,\dots]$](http://latex.artofproblemsolving.com/d/3/e/d3ef3f221323abf5c6356691c994845c9be62918.png)
and ![$y=[0;1+a,\dots]$](http://latex.artofproblemsolving.com/3/9/7/397e02bb78e1b1f429fefe70e1cc92de4f6bd7bd.png)
where the 
is the same. If then 
so they have the same number of terms in the continued fraction, thus 
as desired.
directly.
. For any we have![\[s(x)=-s(-x)=s(x+1)\]](http://latex.artofproblemsolving.com/3/2/9/3290f550427475170362f031c558fd9666b859ce.png)
and we also have 
. Hence for any 
we have 
.
(starting from the smallest), we now choose 
for 
starting from and relatively prime to 
according to the following rules:
then 
.
then 
. and the conditions hold. Importantly our selection of outputs satisfies 
as well. (The only restriction on is which clearly holds.)
then WLOG with . From the first rule in the previous section we are fine.
cannot hold. If then write 
and 
. Then![\[s(x)=-s(1/x)=-s(1/x-1)=-s(b/a)\]](http://latex.artofproblemsolving.com/1/c/a/1caf3a4fbffbd73479bcd305c2ea6fb18a4daadf.png)
![\[s(y)=-s(1/y)=-s(1/y-1)=-s(a/b)\]](http://latex.artofproblemsolving.com/3/c/6/3c68f657f66c8a332250c67b4a232a5945f615a8.png)
thus . for positive .
and are distinct, negative and satisfy we are okay: 
. and are distinct and satisfy we are okay by definition. and WLOG is negative while is positive, then![\[s(y)=s(y-1)=-s(1-y)=-s(x)\]](http://latex.artofproblemsolving.com/6/8/b/68be493bd6889d204c9d6942ed7daac1e44801c2.png)
and we are okay.
for coprime nonzero inputs as follows: let 
for all 
. Then we define recursively![\[
f(a+b,b) = f(a,a+b) = f(a,b).
\]](http://latex.artofproblemsolving.com/8/c/e/8ceba577222d7c91c373379932ec1491f1b7773d.png)
This is well defined as 
is defined on input by Euclidean algorithm, and 
is defined uniquely by whichever of 
is smaller.
follows since 
recursively with the Euclidean algorithm. Furthermore, for 
, 
. to negative coprime inputs by defining 
. By and by the definition, it follows that for 
![\[
f(a, b) = f(a+b, b), f(b, a) = f(b, a+b)
\]](http://latex.artofproblemsolving.com/4/d/9/4d926a668585ac7af2668c27070453b5c09e9fbc.png)
holds for all 
. We finally define 
for coprime . Then 
holds over the extension for the same reasons, 
holds by definition, and 
holds since![\[
f(b-a,b) = f(-a,b) = -f(a,b)
\]](http://latex.artofproblemsolving.com/d/1/3/d1370636d2818f96924dd00e3dd6a4fa66ebfda5.png)
so we are done.
.
.
Where 
.
from 
.
is a number of subfractions in the continuous fraction representing 
if we use 
contradiction.
and ![$x=[a_0;a_1,\ldots,a_m]$](http://latex.artofproblemsolving.com/5/6/e/56ed080618e6b06c10a5648cf6102fbcd6fea56c.png)
.
and 
.
,
,
,
and 
,
,
.
to be the minimum repeated applications of 
until an integer is obtained, and 
if ![\[\{s(0) = -1,\ s(x) = (-1)^{g(x)}|\ x > 0,\ s(x) = (-1)^{g(-x) + 1}|\ x < 0\}\ \forall\ x\ \in\ \mathbb{Q}\]](http://latex.artofproblemsolving.com/7/6/3/7639d6b32b78dd339446b8411afa6547cabb97b9.png)
.
,
,
,
.
,
,
,
as well. Finally, we will show that for any 
.
,
is equal to 
and the other is 
,
,
![$[0, 1]$](http://latex.artofproblemsolving.com/a/b/1/ab178d831a786b92cb4c9ddc2d33578223036f98.png)
.
,
.
,
,
,
,
and the other is greater than 
Therefore, we can express 
.
.
.
,
,
,