AoPS Academy
segments 
and 
are parallel. Angle bisectors of 
and 
meet at 
. Angle bisectors of 
and 
meet at 
. Prove that 
is cyclic
be an acute triangle with orthocenter 
and circumcenter 
. Let 
and 
be points on the line segments 
and respectively such that 
is a parallelogram. Prove that 
.
, let 
be the midpoint of side 
. Let the line perpendicular to at point 
intersect 
at 
. If 
is tangent to at 
, find 
.
Claim. 
must be a power of 
of , then 
by Fermat Christmas Theorem all prime divisors of 
are 
or 
, but 
as 
odd, nor 
, a contradiction. work.
, write 
Note that each term except for the first one, by Fermat Christmas Theorem have only prime divisors, so choose 
a primitive root 
then by Chinese Remainder Theorem exists 
such that 
then 
, and 
, as 
are relative primes we would have that 
, as desired.
.
be the largest odd prime divisor of . For the sake of contradiction, assume 
. Fermat's Christmas Theorem states that the factors of are either 
or . Since 
divides 
, all the factors of are either or . Then, as![\[2^d-1 \equiv 3 \pmod{4},\]](http://latex.artofproblemsolving.com/5/4/f/54f5dff62a4f63bed024f30a6ce72d12a9cc8925.png)
, contradicting our assumption that . work, induction with difference of squares easily works.
. The most convenient method to show each works is by setting 
. Our condition is reduced to proving there exists such an 
with![\[2^{2^b}-1 = 3\left(2^2+1\right)\left(2^{2^2}+1\right) \ldots \left(2^{2^{b-1}}-1\right) \mid 3(a^2+1) \mid (3a)^2+9.\]](http://latex.artofproblemsolving.com/2/e/e/2eeac9337ceff586541706fb210da5a2ba7b347c.png)
for each 
, there must exist such an .
is an odd prime divisor of . Then neither 2 or 3 are factors of 
, so Fermat's Christmas Theorem tells us we must have 
for all prime divisors of , contradiction. 
has to be an integer, the answer is obviously all positive integers ! (Just kidding! Real solution below) that can be expressed in the form of 
for some nonnegative integer .
divides 
, then it is either 
mod 
or it divides 
. Using this, I now claim that cannot have any prime factor that is larger than . FTSOC, assume that 
, where 
. This then implies that![\[2^p-1\mid 2^n-1,\]](http://latex.artofproblemsolving.com/e/d/a/eda90c21c3c4a6cb01fe8cc6db880ada410d47f1.png)
and since , we have that 
must be mod . Additionally, since is a prime 
, this means that is odd, implying that![\[2^p-1 \equiv 2-1\equiv 1\mod 3,\]](http://latex.artofproblemsolving.com/5/d/1/5d1ee74d2fdce0d56cbfac309f36244aaa733df9.png)
so if is mod , some other prime 
divides , a contradiction to the Christmas Theorem statement. Therefore cannot have any prime factor , meaning that must be in the form of in order for to have a multiple in the form of ., has a multiple of the form . I will prove this using induction. Suppose that 
for 
has a multiple of the form . This implies that 
is a quadratic residue mod . Now, note that![\[2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1),\]](http://latex.artofproblemsolving.com/1/5/1/15136002c41964a7369adb640fa7ef42a1eaf4f9.png)
and that 
. Therefore, since we already know that is a quadratic residue mod , we just need to prove that is also a quadratic residue mod . Since the two modulos are relatively prime, by CRT, this will also prove that is a quadratic residue mod 
, meaning that a multiple of in the form of .![\[(2^{2^{k-1}})^2 \equiv -1 \mod (2^{2^{k}}+1) \iff (3*2^{2^{k-1}})^2 \equiv -9 \mod (2^{2^{k}}+1),\]](http://latex.artofproblemsolving.com/c/8/5/c85dc1558b9b225829a43284cbf03e40b160ab29.png)
which proves that is indeed a quadratic residue mod 
. Therefore, if there exists a multiple of in the form of 
, then there exists a multiple of 
in the form of 
!
and the external case 
. The latter is covered by 
and the former also by . Therefore, there exists a multiple of in the form of if and only if is a power of , finishing the problem.
for some nonnegative integer 
.
, we have that 
. We also have that 
, which implies that must have some prime divisor 
, and 
. Since we require 
, this prime must also divide . However, we can then apply Fermat's Christmas theorem on to show that any prime dividing is either 
or 
, contradiction. Any even that is not a power of will have some odd factor 
, and since 
we get the same contradiction. works. 
gives 
, which clearly works. We will now prove that for positive , is the product of and some (not necessarily distinct) primes that are 
. We will use induction to do this, with base case 
and 
. For the inductive step, we notice that 
, so we just need to prove that 
only has prime factors that are . This is true by applying Fermat's Christmas Theorem, so the induction is complete.. We can factor into powers of distinct primes, and consider each prime power separately. For the factor of , just select 
. For the other primes, which must have , we need to show that there exists a value of 
such that 
. It is well-known that there exists a primitive root with order 
. Since we know 
is an integer, we can let 
so that 
. Then we just multiply by to get a working value for . Then by applying CRT on all of the separate prime powers, we know that there will exist a value of such that is divisible by all of the prime powers together, and we are done.
where is a nonnegative integer. We first introduce the following lemma., every prime divisor of is either or congruent to 
if and only if is a power of ., and let be a prime divisor of . We have 
so letting 
, it follows that 
so 
for 
. If 
, then 
or ; otherwise, 
, so we must have 
or . of is either or congruent to , then must be a power of . For the sake of contradiction, suppose is not a power of . Then, 
where 
is a nonnegative integer and 
is an odd integer greater than . We know that 
but 
, so every prime dividing 
is congruent to . It is then clear that 
so 
, a contradiction, giving the lemma. 
is a prime divisor of . The given condition implies that 
so either 
or 
It follows that 
, but is an arbitrary prime dividing , so every prime dividing is congruent to . Applying the lemma finishes, since if is a power of , we have as a quadratic residue modulo every prime divisor of (or divisible by the prime divisor ), and the construction of follows from using the Chinese Remainder Theorem on the prime divisors of . 
of the form 
. is either equal to or congruent to 
. is odd, it is trivial to observe that 
for 
so it follows that the required must be of the form . We now show that these indeed work.
. Now we need to show that 
or that 
is divisible by 
and 
. Since they are both coprime, the result follows by 
(This probably requires some care but good enough for a comeback I suppose).
where is a positive integer. We will use the following lemma:
and 
, then 
and 
. has at most one prime factor that is modulo , which is . Suppose now that there is some prime number , . Clearly ![\[2^p-1\mid 2^n-1\mid m^2+9\]](http://latex.artofproblemsolving.com/d/c/2/dc2358b05920902badb00013c9ac8510e0a2fbb6.png)
Notice now that 
so it must have a prime factor that is modulo . This also can't be since 
(because is odd), hence we get a contradiction. for some positive integer . We prove that all such work. in since from LTE 
so we can just take 
. modulo of is .![\[2^{2^k}-1=(2+1)\left(2^2+1\right)\dots\left(2^{2^{k-1}}+1\right)\]](http://latex.artofproblemsolving.com/d/4/2/d422649c5ab6224e407a7d8f5013ed2748c7d819.png)
Besides the first factor, all of them are of the form 
so they can't have a prime factor . 
(note that from the above we have 
) we have 
so doesn't affect us. Now note ![\[\left(\dfrac{-9}{q}\right)=\left(\dfrac{-1}{q}\right) \cdot \left(\dfrac{9}{q}\right)=1\]](http://latex.artofproblemsolving.com/7/e/6/7e6d422051f3fb1bf55aaa042bd3f728e2538709.png)
So there is some such that 
. Therefore, by CRT we can find the desired . 
. Assume 
since 
trivially holds.
divided 
so that 
divides 
and so 
Since is odd, we have that is not divisible by 
and so we can further reduce this to 
i.e. divides 
We know by orders that 
only has prime divisors equivalent to 
so all divisors of are equivalent to 
But 
for 
yielding a contradiction.
We will construct such a number inductively, with the base case 
holding with 
Now assume that we have a number such that 
Since 
and 
we just need to find a number such that 
, from which we are done by the Chinese Remainder Theorem. Clearly 
is not divisible by so we can reduce this to 
where the 
are primes and 
such that 
for all 
By the Chinese Remainder Theorem, it suffices to show that 
has a solution modulo 
for all Notice that has a primitive root, and 
is divisible by 
which readily implies that 
is a quadratic residue. Combining all these congruences gives us our desired 
such that 
has a multiple of the form are powers of two, which we have confirmed to work.
for some odd 
. If 
for some , then 
. Since 
, we have 
. Since 
, it follows that is a quadratic residue modulo for some prime divisor such that 
, a contradiction. Hence, if is not a power of , then has no multiple of the form . is a quadratic residue modulo 
for some nonnegative integer 
. note that 
. Then is a quadratic residue modulo 
. By induction, it follows that is a quadratic residue modulo for all , so that has a multiple of the form . is given by 
of the form for some non-negative integer . When the result is clear so we deal with in what follows. First we shall show that all the claimed solutions indeed work.
and in particular, Lifting the Exponent Lemma tells us that 
. Thus, we can write![\[2^n-1=3 \cdot p_1^{a_1}\cdot p_2^{a_2}\cdots p_r^{a^r}\]](http://latex.artofproblemsolving.com/3/5/0/3508d9571832ceca72f13a80e6415a22d3f9af34.png)
for distinct odd primes 
. We first claim the following.
are .![\[2^{2^k}-1=(2-1)(2+1)(2^2+1)\dots (2^{2^{k-1}}+1)\]](http://latex.artofproblemsolving.com/2/9/e/29eab6e88dba55c9a0f33d2339add84d7f29409b.png)
Since each index of beyond the second factor is even, none of these factors are divisible by 3. Further, if 
(and 
) divides one of these terms, then 
for some 
. However, this is a clear contradiction by Fermat's Christmas Theorem implying that the left-hand expression has no primes factors as claimed.
. Further, for each prime 
we have,![\[(-9)^{\frac{p_i-1}{2}} \equiv (-1)^{\frac{p_i-1}{2}}\cdot 9^{\frac{p_i-1}{2}} \equiv (-1)^{\frac{p_i-1}{2}} \equiv 1 \pmod{p_i}\]](http://latex.artofproblemsolving.com/a/6/e/a6ec57ee4d77080783580dc47b9a652c18a7245d.png)
since 
as noted above. Thus, is a QR 
. Thus, for each prime there exists some positive integer 
for which 
. We now resort to induction.
such that 
for some 
. We note that,![\[(x_{im}+kp^m)^2+9\]](http://latex.artofproblemsolving.com/2/6/8/2687042dba4775fd68c3dc9b2f328ec65fa00114.png)
is injective 
and in the set 
as ranges from 
to 
. Thus, one of these values for gives a new positive integer 
such that 
., we conclude that there must exist some positive integer 
such that 
for all 
. We apply CRT on 
to construct a suitable value for and finish. work, say 
and 
. Thus,![\[2^p-1\mid 2^n-1 \mid m^2+9\]](http://latex.artofproblemsolving.com/c/2/5/c2535640a41623504c5b7e4cba530a1d29fd98a6.png)
Since the left-hand side is and thus, some prime factor of , 
exists. However, by Fermat's Christmas Theorem this is a clear contradiction as we must have 
.
don't work so must be a power of 2. Such can be shown to work using CRT combined with LTE to show 
can't be too large.
has an odd prime divisor d , such that : 
, thus: has an odd prime divisor p![$p \equiv 1[4]$](http://latex.artofproblemsolving.com/6/2/b/62b88ce3f662a1c69652c9cdcce32f56a57fdfa5.png)
![$p|a^2+9\implies a^2\iff -9[p]$](http://latex.artofproblemsolving.com/4/2/8/428e01964b4f18fe4202ed0f8fe399dddf20c3c0.png)
![$p\iff 3[4]$](http://latex.artofproblemsolving.com/e/0/6/e06fc0bf0f487beade7c0ef48c559348f6c87143.png)
, then:
(not a quadratic residu mod p)![$3|2^d-1\implies 2^d\equiv 1[3]$](http://latex.artofproblemsolving.com/c/6/d/c6daee50dd1361ab2f563914eedd14ef8a35cc2c.png)
is a power of 2
![$\exists a\in \mathbb{N}:a^2\equiv -9[2^{2^{k}}-1]$](http://latex.artofproblemsolving.com/4/f/2/4f2524e2d62780030083f3189313445e2b6988b7.png)
![$a^2\equiv -9[2^{2^k}-1]$](http://latex.artofproblemsolving.com/7/c/3/7c33e4780f5e3fce1a0441d849c5533202e88fa2.png)
![$\exists b\in \mathbb{N}:b\equiv a_1[2^{2^k}+1]$](http://latex.artofproblemsolving.com/b/1/3/b1318013954f78b9c436fd5dba47c32c23e00eba.png)
and ![$b\equiv a[2^{2^k}-1]$](http://latex.artofproblemsolving.com/c/7/b/c7b80ab2c3b6cca9abb897ac129b30f1841fb1e5.png)
![$\implies b^2\equiv a^2\equiv -9[2^{2^k}-1]$](http://latex.artofproblemsolving.com/5/b/1/5b16a4e298f82a671ef7caadd9ed859e41f61b81.png)
et ![$b^2\equiv a_1^2\equiv -9[2^{2^k}+1]$](http://latex.artofproblemsolving.com/a/5/7/a575fa297ddaeea1c1f3b772ed9c98b401bb43ed.png)
![$\exists b\in \mathbb{N}:b^2\equiv -9[2^{2^{k+1}}-1]$](http://latex.artofproblemsolving.com/6/4/5/6454a5a2d93b6265ba93f136a799a9108c4fbafd.png)
iff is a power of 2
I claim that an integer has a multiple of the form if and only if none of 's prime factors, other than , are 
, and 
that has a multiple of the form must be of that form. By Fermat's Christmas theorem, we have that all of the prime divisors of must be 
or is 2. Now, assume that 
Thus, any multiple of divides 27. However, 
Thus, this direction is now proved. of this form has a multiple that can be written as 
By using the Jacobi Symbol, we can use quadratic reprocity to show that there exists an such that 
and thus we are done.
satisfies the conditions of 
For all the prime factors to be 
or we claim that is a power of 2. This can be seen by using orders.
by 
our expression has at most one power of 3. Thus, the answer is 
for 
and 
.
is a divisor of 
.
s.t. 
.
is of the form 
,
,
,
,
.
(because 
)
(because 
)
,
has only divisors of the form 
,
s.t. 
.
,
.
,
.
.![\[ \left(\frac{-9}p\right) = \left(\frac{-3}p\right)\left(\frac{3}p\right) \]](http://latex.artofproblemsolving.com/6/8/2/68201627cf80be4f664d9e41e6314c9d54764340.png)
,
,
.
with 
and 
.
which is impossible for 
because then 
would have at least one prime divisor 
and it is well known that 
and ![\[ (2^2+1)(2^4+1)\ldots (2^{2^k}-1)\mid 3(r^2+1) \]](http://latex.artofproblemsolving.com/f/1/d/f1d9fb4f9c6e42a823a7503e434772fdd2d68705.png)
![\[ (2^2+1)(2^4+1)\ldots (2^{2^k}-1)\mid (r^2+1) \]](http://latex.artofproblemsolving.com/7/7/1/7713443826e8403df5012b6784d9e3ab7a8117c3.png)
.
and it is well known that 
iff 
or 
.
iff it is a q.r. 
for some 
,
Clearly, all its prime factors must be of the form 
or 
Since 
the factors cannot all be 
so there must be at least one prime factor of the form 
divides 
Let 
Assume for sake of contradiction that 
Then 
So we obtain 
and 
However, by FLT, we must have 
a contradiction. Therefore, 
divides 
for 
for some integer 
,
,
.
has a prime factor of the form 
for some integer 
.![\[\begin{cases}X\equiv x_1\pmod{p_1^{\alpha_1}}\\ \cdots\\X\equiv x_n\pmod{p_n^{\alpha_n}}\end{cases}\]](http://latex.artofproblemsolving.com/8/b/d/8bd804394640ff944a9ab9102186bffa90ac02f3.png)
Where 
.
suffices.
for some non-negative integer 
We must find values of 
Now, suppose for sake of contradiction that 
Then 
So consider a prime factor of 
![\[\left( \frac{-9}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{9}{p} \right) = (-1)^{\frac{p-1}{2}}\left( \frac{3}{p}\right) ^2 = (-1)^{\frac{p-1}{2}}.
\]](http://latex.artofproblemsolving.com/d/a/2/da2f62a4f435be86aa27c6473e8e7b35451e935a.png)
Hence, 
must be even, so 
However, since 
so all prime factors of 
which is impossible since 
and the only prime factor of 
is 
From above, we see that 
From the well-known fact* that all quadratic residues of 
for some positive integer 
There there exists an integer 
such that 
Then consider 
It suffices to show that there exists a value of 
such that this value is 
We have![\[kp^n+r+2abp^n+b^2p^{2n} = p^n(2ab+k)+b^2p^{2n}.
\]](http://latex.artofproblemsolving.com/6/3/1/63115ffb5a8db1597785df02e97816445ad5f26b.png)
Clearly, there exists 
so we are done. (This results also follows directly from Hensel's Lemma.)
,
.
,
is always equal to 
must also be equal to 
.
satisfies the condition. Assume also 
.
.
.
.
,
.
!
other than 
and this follows at once by Euler's criterion and composite quadratic residue law.
then 
is a factor of 
other than 
it must also divide 
.
inducting backwards we see that the highest power of 
,
)
hence 
)
so that the highest power of 
.
where 
and 
,
and so 
.
giving 
,
,
.
.
denote the Legendre symbol.
.
since 
only for 
,
implies that 
.
for 
,
,
,
or equivalently 
,
,
.
,
,
Moreover, if 
,
,
.
which proves the claim.
,