AoPS Academy
be reals such that 
and 
Prove that
Let be reals such that and 
Prove that
Let be reals such that and 
Prove that
and a set 
consisting of 
disting positive integers smaller than 
are given. Prove that there exists a positive integer 
that can be written in the form 
, for 
in at least 
different ways.
and colors are given. We will say that a set of 
points on a plane is 
, if it contains exactly 2 points of each color and if lines connecting every two points of the same color are pairwise distinct. Find, in terms of the least integer such that: in every set of 
points of a plane, no three of which are collinear, consisting of 
points of every color there exists a subset.
?
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
,
.
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)
.
,
.
.