AoPS Academy
and 
Prove that
Let and 
Prove that
denotes the least natural such that
Find all naturals 
such that 
.
such that 
has no a non trivial solution i.e there is a solution 
which satisfy the relation, contradiction. is odd we have 
so
which has a solution 
so 
there are no odd solutions. Thus must be of the form 
. If 
we have at least a prime satisfying
And this has two roots so by 
we have at least 
distinct solutions for 
after considering the system of relatively primes
But this implies there is a non-trivial solution and we are done, this can't be a solution. So 
. is satisfying 
And since 
we have either 
or 
the first implies
And the later implies
So we are done, we showed all the solutions are 
.
clearly 
.
, with 
.
. Notice that every element of the set is strictly smaller than .
, the 
elements of 
are different., at most one of the elements of the tuple 
belongs .
we have exactly one element in . Then there exist 
such that either 
or 
.
.
is divisible by , then 
..
is divisible by , then 
. but the powers of .
, 
, and 
odd (the rest, case when is odd and is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences:![\[
\mathcal{C}_1 : \quad x\equiv 0\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv -1\pmod{m'}.
\]](http://latex.artofproblemsolving.com/4/0/6/40680e15d4ac0718ff9e3252a651434a96499f83.png)
![\[
\mathcal{C}_2 : \quad x\equiv -1\pmod{2^{\alpha+1}} \quad\text{and}\quad x\equiv 0\pmod{m'}.
\]](http://latex.artofproblemsolving.com/d/b/4/db4a864a7f32de0e4ba00ffa09780cb733d1e6be.png)
By the CRT, both 
and 
have a solution modulo 
. I claim it is the case that the smallest solution to one of them is less than or equal to . For that, let 
be the smallest positive solution to . In particular, 
. If 
, we are done. Otherwise, assume 
. We have![\[
2m>\ell m'>m \implies 2^{\alpha+1}>\ell >2^\alpha.
\]](http://latex.artofproblemsolving.com/b/a/d/bad5d9984d0f4b6dc102f8b72806827366859125.png)
Consider now the number![\[
x = \left(2^{\alpha+1}-\ell\right) m' = 2m - \ell m'.
\]](http://latex.artofproblemsolving.com/0/7/8/0780f68867c0d74aeb2a390329697f268d6ad3c5.png)
Clearly 
, and is divisible by 
. Furthermore, 
. Therefore, solves the congruence . This concludes the proof.
denotes the least natural such thatFind all naturals such that . is a power of . Let . We must have 
, hence 
or
. In both cases, 
, therefore all powers of don't satisfy. is not a power of . Let 
with 
odd. We prove now the following Claim, which gives the result.
be minimal such that 
and 
. Then, either 
or 
is 
.
, then we have 
, hence 
, therefore 
, hence we are done.
and 
. Then, we have 
and 
. Note that by CRT and the minimal condition we have 
therefore 
. In addition, 
hence we must have 
, since , and subsequently 
, is minimal.
, implying that either or 
is 
. Suppose 
.
, as desired. Similarly we conclude if 
. 
.
, , and odd (the rest, case when is odd and is a power of two are both quite trivial). For this case, I think my solution below is instructive and clear: Consider two congruences:By the CRT, both and have a solution modulo . I claim it is the case that the smallest solution to one of them is less than or equal to . For that, let be the smallest positive solution to . In particular, . If , we are done. Otherwise, assume . We haveConsider now the numberClearly , and is divisible by . Furthermore, . Therefore, solves the congruence . This concludes the proof.
?
for 
such that it is smaller than 
.
,
implies that 
so 
, contradiction!
, with being odd and larger than 
, 
. 
just put 
, it satisfies given condition. put 
or 
and we will find suitable 
.
or 
or 
,
and 
such that it is congruent to number that is smaller than 
will prove the lemma since we can just pick that number and it will satisfy all conditions. Now we reduce all numbers 
and look at the solution to 
, that solution will definitely exist because 
since m is odd. And if 
then we can just pick 
and it satisfies all conditions, proving our lemma.
denotes the least natural such thatFind all naturals such that .
for some 
then we have 
Now as 
so either 
or 
then we also have 
or 
Now as we need 
for any 
then we have 
or
hence 
or 
which is contradiction.
is the maximum of which divide or 
and so let 
for some odd 
.
where will satisfy the condition. such that 
and 
for prime 
such that 
for some 
we have 
or 
so either 
or 
as 
so we must need to prove 
for some 
and 
which is clearly true as by property of mods as 
so there will always exist exactly one 
so we are done. 
denotes the least natural such thatFind all naturals such that 
.
for positive integers and . We first show that these do work, and then we show that the others don't work. trivially works. Now we assume that is positive. For convenience, let 
. Then notice that the condition is basically just that no 
satisfy 
. Notice that for it to satisfy the equation, 
or 
, so that the numerator at least has an 
values 
. However, it is easy to see the division by causes both of these too fail, so we have showed that these solutions work.
works, so 
already strong enough to prove the claim. Now, to finish, we just show that any odd number multiply by any power of also does not work. This would be strong enough to prove the claim.
for whatever power of you are trying to multiply by(we have to add one to the because of the division by ). Then it is easy to see that the solutions for 
are just 
and 
exists because it is odd, coprime with modulus. Clearly, at least one of these 
(the two halves of the residue class each contain one of or 
, and notice there is no "single middle" issue because the number of elements in the 
residue class is even), so we are done.
such that 
We will show that there must exist such a such that
or vice versa. Because the two mods are relatively prime, we know there exists some 
such that this is true. If this , we are done. If 
, then consider the number 
. First, 
whilst 
and thus satisfies the ``vice versa" system of congruences. We also know that 
-- thus the claim is true as desired.
denotes the least natural such thatFind all naturals such that . for all .
, we must have 
and as 
, we must have either 
or 
, thus 
. note that works, thus definitely 
for any odd., there exists odd 
such that 
, where 
.
. Firstly note that if 
, then 
, which implies that 
. This essentially means that as varies, 
give different residues mod 
, similarly 
is injective over 
. and consider 
, which implies that 
. But note that this implies a contradictions as if 
, we get that 
as , which is impossible. But if 
for some odd , we get that 
, which contradicts that fact that is injective over . imply different values of , and, as we have 
different congruences, we obtain different odd values of , the claim follows. 
, where and is any odd number. By the claim, we get that for any odd , there exists odd such that , thus either 
or 
works, where both are smaller than , we are done.
except for the powers of 2, as well as 1. Clearly 1 works.
, and suppose for . Assume for the sake of the contradiction that there existed an even solution 
. Then 
, and 
. Clearly 
, and therefore cannot divide the sum. Now assume for the sake of contradiction that there existed an odd solution 
. Then 
and 
. Repeat.
for odd 
. Let 
. It is clear that one of 
and 
is less than . Let be this value. If 
, then 
is a valid solution since it is less than and 
which is clearly divisible by both and since 
. If 
, then 
is a valid solution by the same reasoning.
works except for when is a power of two and is greater than . works.
works, but this might not be the smallest, so we have ![\[ T_m \le m \implies m \ge T_m. \]](http://latex.artofproblemsolving.com/0/6/c/06c42d42303e3de1902e27b87ebaac058953bf92.png)
works. is a power of two, it doesn't satify the condition. such that 
. Now if is even, then 
is odd which means . So 
. Now let 
and so 
. Also notice that 
because , and hence a contradiction. The case when is odd, and is even follows the same logic and we are done. that is even and not a power of two work.
Now if 
, let 
. Then let be the modular inverse of 
. This means that 
and 
. Because we know , we know that 
. Now if 
then we can have 
and we would be done. Now if 
then we consider the number 
. Notice that
and so we can have 
. Using the same proof as above for when 
, we are done.
besides .
work as![\[n \mid 1+2+3+\ldots+(2k-2)+(2k-1)+2k=(1+2k)+(2+2k-1)+\ldots+(k+k+1)\]](http://latex.artofproblemsolving.com/0/6/3/0633ba55d8da39dc80094e8e02fac2845d248bd5.png)
so 
. Another way to see this is that 
.
satisfies 
, then so does 
hold., with being odd, then we have![\[2n=4k+2\mid 1+2+\ldots+2k+(2k+1)=\frac{(2k+1)(2k+2)}{2}=(2k+1)(k+1)\]](http://latex.artofproblemsolving.com/e/d/1/ed1209deafcec492c37a94f270f386fc056433d2.png)
as 
is even, i.e. 
. Otherwise, if is even,![\[2n=4k+2\mid 1+2+\ldots+2k=k(2k+1)=\frac k2(4k+2)\]](http://latex.artofproblemsolving.com/3/2/4/3242c239d11badc5c8fe6bf182e17ecac8376647.png)
i.e. 
. ., 
do not satisfy .
is even then![\[\nu_2\left(\frac{\ell(\ell+1)}{2}\right)=\nu_2\left(\frac{\ell}{2}\right)=\nu_2(\ell)-\nu_2(2)=\nu_2(\ell)-1<k.\]](http://latex.artofproblemsolving.com/8/6/f/86fb240c5e47b031b43959e7de95e93c20b5410f.png)
so cannot divid this sum. We get the same thing when 
is odd, as 
as well, so 
.
. If 
for an integer 
, then we need 
in order for 
to be at least 
, since we need either 
or 
. Hence none of the powers of work (other than ).
where 
and 
is a positive integer. We want 
and 
. Let 
be the inverse of 
. If 
, then we can let 
, since then 
and 
, and furthermore 
. If 
, then we can let 
, since then 
and 
, and furthermore 
. Hence all numbers of the form 
work, and we are done.
.
. We firstly work with . Now I claim that there is a multiple of 
among the following,
as the working choice from the above listed for 
, otherwise the 
for 
.. Also notice that all the choices above are even. So we consider their binary representation. So the representation must have its last digit as . Now also notice that all the ones are distinct 
which simply follows from a contradiction and some case bashing. Now note that we have at most 
binary representations with digits that are even but are not divisible by but above, we have 
choices which is a clear contradiction and we are done.
, note that taking just taking 
works and we are done. Now for the proof that the powers of don't work, a simple 
contradiction works and we are done.
work. Clearly 
works, so assume 
Write 
where 
is odd. Obviously 
Thus we require that 
or, when plugging in values, 
Now, let 
be the unique integer between and 
inclusive such that 
and 
Such a value for exists by CRT, and setting 
would work. However, we do not know if 
or not. To counter this, we consider the unique integer 
between and such that 
and 
This value of also exists by CRT, and plugging in 
would also work. We also do not know whether or not 
and 
We end up getting 
and 
Since 
we are forced to have 
Say by Pigeonhole, this implies that at least one of 
is less than or equal to 
so plugging in that value for 
will show that all non-powers of two work. of the form where 
do not work. (Note: the above argument does not work for powers of since 
in that case, and it is illogical to take things modulo 
) Once again, we require 
At least one of and 
is odd, so that forces all of the powers of to go into one term. But that would mean that 
if is even and 
if is odd. Since 
both yield clear contradictions. that work are those that are not of the form 
where 
as claimed at the beginning.
where 
and 
are integers such that is odd.
such that 
By Chinese Remainder Theorem, we can split this into 
If 
(e.g. is a power of 2), then this is clearly not possible, as in the first congruence, and 
are opposite parity, so all factors of 2 must come from one of them, which is clearly not possible unless 
as is restricted to at most 
. Call a number orz if 
Call a number xor if 
Note that, modulo 
, there is exactly one orz number, which we call , and one xor number, which we call . Note that 
which rearranges to 
Obviously, 
is too high as even if and are the largest possible, it is still one away. Thus, we must have 
Thus, by Pidgeonhole, one of and is at most 
. Furthermore, clearly and are both nonzero, and both 
and 
satisfy 
hence all non-powers of 2 work as there is some solution at most and we are done. (Amusingly, the part where 
is used is when stating that 
).
satisfies the condition. We split the rest of the problem into two cases.
for a positive integer , then 
.
. Since and 
are relatively prime, the least possible value of is 
, which is greater than for . 
for an odd integer 
, then 
. and 
such that
![\[T_{m_1} \equiv 1 - T_{m_2} \implies T_{m_1}~+~T_{m_2} = 2^{k+1} \cdot n - 1 \implies \min(T_{m_1}, T_{m_2}) < 2^k \cdot n - 1 < m,\]](http://latex.artofproblemsolving.com/2/d/b/2dbd0bced5b0deccabd4711368b4f23ac98f5aa8.png)
such that . 
. 
if and only if cannot be expressed in the form for some positive integer . for positive integers work., then 
. Observe that 
, with and 
having opposite parities. Hence, 
if and only if or are divisible by 
. Thus 
. that cannot be expressed as where is a positive integer do not work.
, observe that 
and 
. So it is left to consider the case when 
where does not divide 
and is a positive integer. Then consider the unique integers by Chinese Remainder Theorem 
such that
and 
so 
. Now 
both satisfy 
but we can simply choose 
and we are done.
for all odd . Otherwise, let 
for some odd . Let odd 
. Then, let 
. If 
, then let 
. Then, 
or 
. Notice that if 
, then 
, but 
is not a possible sum. Otherwise, . Therefore, all integers that aren't 
for some integer 
work.
work since 
. Now, let 
. We would like to have![\[a \cdot 2^{b+1} \mid T_k (T_k+1).\]](http://latex.artofproblemsolving.com/3/f/5/3f57ecb1c81031c27db409d23f48fcce1a8b68c6.png)
, we can let 
be a value such that![\[p \equiv 0 \pmod{a}\]](http://latex.artofproblemsolving.com/a/7/8/a7874d7d98485a8b7846bcad9c14821893ebb511.png)
![\[p \equiv -1 \pmod{2^{b+1}}.\]](http://latex.artofproblemsolving.com/d/f/b/dfb15eaebfec05c2e4ab14e493a7682eca8f39db.png)
works. However, we do not necessarily know that 
.
be a value such that:![\[q \equiv -1 \pmod{a}\]](http://latex.artofproblemsolving.com/f/0/1/f012118263c4c61baeb6aa9dc3681ea76ff0ab1e.png)
![\[q \equiv 0 \pmod{2^{b+1}}.\]](http://latex.artofproblemsolving.com/2/0/4/2043fbb4ce31e9129ea329ede4078732e1a36ec5.png)
works. We still do not know that 
, but we have![\[p+q \equiv -1 \pmod{a \cdot 2^{b+1}} \quad \text{and} \quad p+q < 2(a \cdot 2^{b+1})-1\]](http://latex.artofproblemsolving.com/4/9/e/49ecb14acfd7a3bf9a2c24d2ed7e2b2aa3aab671.png)
![\[\implies p+q = a \cdot 2^{b+1}-1.\]](http://latex.artofproblemsolving.com/d/3/f/d3f96f77915339598ac217af7585adbdbefad3b7.png)
.
does not work. We must have![\[2^{x+1} \mid T_k(T_k+1).\]](http://latex.artofproblemsolving.com/2/d/a/2da362c44bb526fc8601a8fe3f0cc3f853212222.png)
and 
are relatively prime, the minimum value is clearly 
.
with the exception of 
work., then 
, so 
.
where is odd and greater than 
, we will prove that 
.
, then the maximum value of is 
, so it works.
, there are two possible values 
and 
that (could) work.![\[T_{m_1} \equiv 0\pmod{n}\]](http://latex.artofproblemsolving.com/2/6/5/26595cfb3a83b2acbdd71c839390f39bf06cf855.png)
![\[T_{m_1} \equiv -1\pmod{2^{k+1}}\]](http://latex.artofproblemsolving.com/9/6/a/96ad7f8f3521b0e7166ab62430a73578d8f05a3d.png)
![\[T_{m_2} \equiv -1\pmod{n}\]](http://latex.artofproblemsolving.com/c/f/7/cf74d8e8ad774f7644d5fe4beb00b153af42f0c2.png)
![\[T_{m_2} \equiv 0\pmod{2^{k+1}}\]](http://latex.artofproblemsolving.com/b/c/5/bc55d2e8f59acaf24a81c976fd299c41f1bbfa58.png)
.![\[T_{m_1} + T_{m_2} \equiv -1\pmod{n}\]](http://latex.artofproblemsolving.com/1/c/1/1c17676a587edf9d01cf665d76f7e122bc5dba31.png)
![\[T_{m_1} + T_{m_2} \equiv -1\pmod{2^{k+1}}\]](http://latex.artofproblemsolving.com/e/3/2/e322d2421cd3081dcbaf26f7c4308c23fcf4a44d.png)
![\[T_{m_1} + T_{m_2} \equiv -1\pmod{n \cdot 2^{k+1}}\]](http://latex.artofproblemsolving.com/9/1/4/91448a559de1fec7b61c29cd260ea7a7366f14b9.png)
is 
, so this satisfies our conditions. work. (Except for , of course.)
such that is not a power of greater than . It is clear that for all such that , 
is the smallest possible solution, and this is greater than for all values of . is not a power of greater than . We see that in ![\[x(x+1) \equiv 0 \pmod{2m},\]](http://latex.artofproblemsolving.com/d/4/5/d453250bc73cbf47c0e6f8ae560123fe56e84c73.png)
is the smallest possible value of . Let a solution be 
if ![\[T_m \not\equiv 0 \pmod{2m}\]](http://latex.artofproblemsolving.com/7/1/7/7178ec87f55a9a6f89992ac19f0609e09dd293e5.png)
![\[T_m \not\equiv 2m-1 \pmod{2m}.\]](http://latex.artofproblemsolving.com/e/1/b/e1ba0e2224ce1775496145649b5144419af575fb.png)
Note that if 
is a solution, then 
is also a solution. Therefore, if there exists a nontrivial solution, then the condition must be satisfied because 
. Then it suffices to show that the number of solutions to the above congruence is greater than (or that there exists at least one nontrivial solution). is not a power of , we write 
, where is odd. We have ![\[x(x+1) \equiv 0 \pmod{2^{a+1} \cdot b}.\]](http://latex.artofproblemsolving.com/1/5/6/15648a1d155ec36a6388b4df591e722479b129ea.png)
By the Chinese Remainder Theorem, we see that the systems ![\[x_1 \equiv 0 \pmod{2^{a+1}}\]](http://latex.artofproblemsolving.com/d/5/4/d54b2a724bf785891168af4e4439fa1a381ca1e3.png)
![\[x_1 \equiv -1 \pmod{b}\]](http://latex.artofproblemsolving.com/e/f/6/ef6ca52dab7af2cc25ab58670c09669e3f203411.png)
and ![\[x_2 \equiv -1 \pmod{2^{a+1}}\]](http://latex.artofproblemsolving.com/7/4/0/7403f3cea337a0da8374c16544ec0fabe86de17d.png)
![\[x_2 \equiv 0 \pmod{b}\]](http://latex.artofproblemsolving.com/b/3/9/b395500632666c2234de86a6c9780d0014f46388.png)
produce valid solutions (because is odd, we can conclude that 
and are relatively prime). In fact, we have ![\[x_1 \equiv -1-x_2 \pmod{2^{a+1}}\]](http://latex.artofproblemsolving.com/f/6/3/f635f035eef4e7844bb7b8c1cfb32ae079764acb.png)
![\[x_1 \equiv -1-x_2 \pmod{b}\]](http://latex.artofproblemsolving.com/7/d/b/7dbd2dd268b0f4ccbcc4508a33ad794f6e5f0aed.png)
![\[\implies x_1 \equiv -1-x_2 \equiv (2m-1)-x_2 \pmod{2m}.\]](http://latex.artofproblemsolving.com/5/f/5/5f5e4c8ba8862a489f7f2ca403014455a9eddb4b.png)
Therefore there exists at least one nontrivial solution for all such , as desired.
not an even integral power of work. is odd, we can just let 
. is even (and not a power of ), let be the largest power of dividing so that 
. values all less than :
Note that since is odd, these numbers are the complete even residue set modulo . in the set such that divides it, we obtain a value less than such that 
concluding this part of the proof. don't work :
Which is greater than , for 
and we are finished 
for any positive integer except for powers of and we ll prove that by CRT. We can easily exclude the case of by observing 
. isn't a power of . Since 
it suffices to find an positive integer for which:
exist by CRT. If 
we're done, otherwise oen can see that if is a solution to the system, so is 
and this latter is strictly smaller than .
greater than . 
where 
. Then, is the least positive integer such that 
If 
, then we can set 
and the conclusion is true. For the remainder of this proof we will assume 
.
(in other words is a power of ), then the conclusion is false. This is true because either one of or 
cannot have a factor of 
without exceeding 
. or can have the factors of in the denominator, and one must hold them all. is the multiple of . Then, we can write 
and then 
. Therefore, there is 
possible values of in this scenario. is the multiple of . Then by similar reasoning we have that 
. Thus, has possible solutions in this case as well, using the fact that .
total possible values of the numerator such that the powers of cancel out. Clearly, all of the "other" factors (the one without the powers of ) have distinct modular residues 
(this is simply because is odd).
.
which contradicts the bounds on as said before. The other case follows similarly. . distinct modular residues which cannot be equal to . Therefore there must be one equal to , and the result is an integer. We are done. .
not a perfect power of (except ). For all odd we see that taking 
works so obviously 
. fail, note that we want 
. Thus, we need 
. Since 
, we either have or 
. Both of these imply 
, so we're done.
, where 
is odd. We want 
The key is to notice that if there exists a solution to this congruence, then 
is also a solution. Therefore, if there exists a solution 
, we would be done (either take or take ).
, simply take 
and 
. There exists an (by CRT) such that 
. We know that 
, so we're done! (Clearly 
).
for a positive integer works.
we know 
Since 
, we know 
also satisfies our equation.
where and are relatively prime, there is a solution to 
with 
Note that there are solutions 
(this is because 
when 
and 
when 
, and there exists 
when is not a power of ). If this 
we are done. If 
we know 
is also a solution, and we are done. \qed
instead of 
)![\[n|\frac{T_n(T_n+1)}{2}\]](http://latex.artofproblemsolving.com/0/f/0/0f0da2d3304097c392ec68562d531239ce90c128.png)
Now if 
.
or 
which cannot satisfy 
unless 
,
.
where 
and 
.
.
,
,
or 
respectively.
,
and be done, so assume otherwise. Let 
be congruent to 
modulo 
,
,
,
.
is not a positive integer.
so that 
where 
Now, 
is equivalent to 
which is further equivalent to 
or 
or 
such that 
and 
Similarly, let 
and 
By the Chinese Remainder Theorem, there exists exactly one such 
Note that both 
Note that 
and 
Therefore, by the Chinese Remainder Theorem, 
However, note that 
meaning that 
Therefore, one of 
Therefore, 
where 
Note that 
are relatively prime, so we must have either 
or 
This means that 
so 
: Any 
satisfies.
satisfies.
satisfies. Hence proved Claim-1.
doesn't satisfy.
satisfies.
.
.
,
or 
,
.
where 
or 
.
or 
.
or 
.
be 
.
,
satisfies as 
.
,
satisfies.