AoPS Academy
such that
![\begin{align*}
[(a+1)x-(b-1)y][ax+by]\\
\end{align*}](http://latex.artofproblemsolving.com/b/5/2/b52d93a771b06b5b0a0bebc986de07eda44f25f4.png)
is a polynomial function such that 
then must be greater than 
, 
, and 
be the roots of 
. Find 
such that 
has integer roots.
. A circle O with center C has a radius of 2. Let P be a point on the circle O.
?
?
and 
, such that 
, and 
. Find the last two digits of .
be positive integers with product 
where is an odd positive integer. Prove that 
then 
for all 
and 
. Let 
then it suffices to prove 
then 
, otherwise WLOG 
then 
so 
\for all 
, a contradiction to 
.
so 
or 
. Thus, 
This follows 
or 
. Thus, the only possible prime divisor of 
is .
. Indeed, if 
then 
and 
. Since and 
so 
.
. Since is odd so there exists 
. Hence 
.
then there exists 
. Hence, .
. We follow 
, as desired.
. So, we can replace the 
as 
for all 
. Let 
. Also, 
.
.
.
or 
or it suffices to show 
.
such that 
.
such that 
, then 
. So, for every 
, 
. So, 
for all 
. But we had 
, so there is no such 
such that . 
.
, 
.
. If we take the product over all , we get
As 
, 
. Now as ,we get is even. But we were given that is odd which gives us a contradiction.
such that . So, 
or 
.
, we are done, so we need to consider the case in which 
that implies 
for 
.
such that is even, then 
is also even. So, 
, which would make all other 
also to be even which contradicts the fact that . So, we get all 
are odd. So, 
., 
. So, 
. we get 
. and as is odd, 
. So, 
.
where 
for all to be odd.
such that 
and 
, it suffices to prove that 
.
such that 
and 
.
such that 
, contradiction!
and this shows that is odd!)
as 
, and set 
Clearly 
.
, so 
To prove the given inequality, we need to show 
; we claim that 
is relatively prime of each of the 's. To see this, note that if there a and a prime 
so that and 
, then 
, and since 
, we have 
, implying that divides each of the 's. This contradicts .
, we have 
Multiplying these congruences for , and noting that is odd we have 
But since is relatively prime to 
, this implies 
, as required. 
, and write 
for positive integers 
with 
. Then ![\[\gcd(a_1^n + P, \ldots, a_n^n + P) = d^n \gcd(b_1^n + Q, \ldots, b_n^n + Q)\]](http://latex.artofproblemsolving.com/c/b/0/cb00e3a967bc6aa05aa5e7aab2aa40d2f0643e49.png)
where 
. Hence it suffices to show ![\[D := \gcd(b_1^n + Q, \ldots, b_n^n + Q) \le 2.\]](http://latex.artofproblemsolving.com/e/7/0/e70d3916a978c7e53ab7b16175312a38e53c10b3.png)
To do this, write ![\[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \pmod{D}.\]](http://latex.artofproblemsolving.com/0/d/e/0de9d0b6dfdc6972f1eadbb98eee6756fbf57699.png)
Suppose some prime divides both 
and . Then ![\[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/c/c/3/cc3d43ebd649404e153174b9846377733e5634b3.png)
so 
, contradicting . Thus 
. But ![\[Q^n = b_1^nb_2^n\ldots b_n^n \equiv (-Q)^n \pmod{D}\]](http://latex.artofproblemsolving.com/1/6/f/16f169a1fdbd1aa042925d4055675c2837808dd8.png)
so 
(since is odd). This is enough to force 
, i.e. 
, as desired.
, we can divide out by 
from both sides since every term in the LHS is of degree . So assume 
, then we want to show![\[ d:=\gcd(a_1^n + P, a_2^n+P, \ldots, a_n^n + P) \le 2. \]](http://latex.artofproblemsolving.com/0/b/5/0b512fb674d0c1a07b1489fc9a5568254a91a502.png)
We have 
by Euclid, so![\[ -a_1a_2\cdots a_n \equiv a_1^n \equiv a_2^n \equiv \cdots \equiv a_n^n \pmod{d}. \]](http://latex.artofproblemsolving.com/a/7/7/a77615ce8f6856cf2222d62a98f45b75a9a24c7f.png)
Multiplying together each of the above relations containing 
, we get![\[ (-a_1a_2\cdots a_n)^n \equiv a_1^na_2^n\cdots a_n^n \pmod{d} \implies 2(a_1a_2\cdots a_n)^n \equiv 0 \pmod{d} \]](http://latex.artofproblemsolving.com/d/6/b/d6b71e436a582f171e2ed13fec2dc67c3a2055fc.png)
since is odd. existed s.t. 
and 
. Then there must exist some 
such that 
, otherwise 
. We know 
, so 
. But 
, so 
, so 
, which is a contradiction since we assumed 
. There was nothing special about 
, so 
for all 
. In particular, 
. So we can divide by 
on both sides to get 
, so 
.
be positive integers with product where is an odd positive integer. Prove that 
.Hence 
for some .Hence 
where 
.Thus we have to show ![\[d^n\cdot \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)=\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq
\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq 2\gcd(a_1,\dots, a_n)^n=2d^n\cdot \gcd(b_1,\dots, b_n)^n\]](http://latex.artofproblemsolving.com/f/2/2/f228a1d7dc7534af17b6bfcaf20a2bf0e5c477b8.png)
![\[\implies \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)\leq 2\gcd(b_1,\dots, b_n)^n =2\]](http://latex.artofproblemsolving.com/8/e/4/8e46dfcf669c47ff5ef18956d561f63e865743e6.png)
.Since 
Now let 
be a prime.Then ![\[-Q\equiv b_1^n\equiv b_2^n\cdots \equiv b_n^n\pmod p\]](http://latex.artofproblemsolving.com/d/d/2/dd2ca477535b3d6ac79055428e866911335330c2.png)
![\[(b_1^n)(b_2^n)\cdots (b_n^n)\equiv (-Q)^n\pmod p \implies Q^n\equiv -Q^n\pmod p\implies 2Q^n\equiv 0\pmod p\]](http://latex.artofproblemsolving.com/7/e/f/7ef5e9d25f555b366a180405568e21de5313c3a0.png)
.Now if 
.Then 
a contradiction!Thus .Then if 
.Clearly all are odd.Clearly not all 
otherwise 
.Similarly not all 
.Thus there are 
such that 
and 
.But then 
again a contradiction.Hence 
as desired
Then let for each . We want to show that 
dividing each of 
Then, we must have 
Multiplying over all gives 
for any 
If there exists with 
, then 
for all , contradiction. Thus, , and we conclude. 
; then we wish to show that if 
divides all of the 
, then 
. Write down all the equations of the form 
. Note that cannot share a prime factor with any of the , since then that prime would divide all the . Now multiplying together all these equations gives 
and we're done.
; from here, FTSOC assume that there exists some odd prime dividing all of 
. Then, we see that if one is a multiple of , then 
is a multiple of which would force every other 
to be a multiple of and violate the condition. Hence, we have 
. Though, multiplying every equation gives us that 
modulo which upon dividing both sides by 
(allowed as it is not a multiple of ) gives that 
which obviously is impossible.
be the 
and write 
.
. Let P' denote the product 
. What is left to prove is that 
. Clearly 
is relatively prime to each 
since otherwise a commmon divisor would divide the remaining 
.
and if we multiply them we get 
(since n is odd). Hence divides 
but since and P are relatively prime this implies that 
and hence 
doesn't change anything, hence WLOG let 
, so the inequality becomes:
whenever .
divide the gcd. Suppose FTSOC that a prime does divide the gcd. Clearly cannot divide all of 
. Now suppose divides some of these numbers, so 
. But there exists an with , which means 
: contradiction. Hence divides none of . Then it is necessary to have 
for all . Since is odd, multiplying these congruences yields 
. But since 
, this gives 
, which is impossible since 
. Hence proved.
does not divide the gcd. Suppose FTSOC that 
for all . As with before, since not all of can be even, none of them can be even. Further, observe that since is odd, 
. are congruent to 
, then their product is as well and thus 
, contradiction. Similarly not all of the are congruent to 
. But then picking such that 
and 
implies that 
, so they cannot both equal zero: contradiction.. 
the following equation :
for rational 
.
,
Now raising to the power of 
to both sides and we have 
.
.
Now we just need to find 
mod 
.
,
mod 
.
and 
because 
So we have that 
,
Showing that 
for any prime 
we have that 
so 
and 
(
for any 
We have * because 
.
is odd so 
and 
so 
for any 
is even, so we achieve a contradiction thus 
in this final case, so we are done.
.
,
now divides both terms.
.
for each 
.
where we let 
.
.
for some 
.
,
but since 
for all 
However, since 
for all 
,
,
,
.
First, we prove that 
does not divide the LHS. Note that at least one of the 
while another is 
,
,
is odd
.
.
so 
.
,
.
as the largest integer 
.
and there exists 
,
for 
.
where 
and 
.
.
so cancelling 
on both sides, we obtain 
Since the inequality still holds equivalently when 
,
Consider a prime 
for some 
.
for all primes that divide one of 
to be true, we must have 
This implies that 
or 
We note that 
,
,
,
,
for some 
as 
.
.
.
for 
and 
such that 
(meaning one of them is 
)
and 
at the same time, which is impossible.
,
,
,
,
(since 
,
or 
,
and 
the problem becomes prove that 
.
.
for all 
then by taking the product over all 
or 
,
or 
so we are finished
,
.
so we want to prove 
Now suppose we have a power of a prime 
such that 
,
and since they are coprime we must have 
.
and 
,
which means
If 
is relatively prime to 
.
we get 
.
is 
is not relatively prime to 
then since we know this holds for every pair of 
,
.
,
so 
and no higher powers of 2 is achievable.
then there exists 
such that 
which means every integer in the sequence must be the same modulo 
.
,
,
and no higher powers of 
.
.
,
because 
,
.
,
for all 
,
,
,
but this means that 
.
for all 
for all 
,
,
.
,
.
.
is a power of 2.
have a common odd prime factor 
.
Taking the cyclic product, 
But now, for any 
So 
have the common factor 
.
.
,
,
.
.
,
.
.
,
,
,
for some integer 
.
till 
,
.
,
.
and therefore 
![\[\epsilon=gcd(a_1,a_2,\dots,a_n)\]](http://latex.artofproblemsolving.com/0/0/0/0005227e91e1e502bef8ec9c1f89a4ae47141131.png)
which leads us to a simplification through letting 
as: ![\[gcd(a_1^n+P,a_2^n+P,\dots,a_n^n+P)=gcd\left(\epsilon^n b_1^n+\epsilon^n \prod_{i=1}^{n} b_i, \epsilon^n b_2^n+\epsilon^n \prod_{i=1}^{n} b_i, \dots, \epsilon^n b_n^n+\epsilon^n \prod_{i=1}^{n} b_i\right)\]](http://latex.artofproblemsolving.com/a/2/8/a288f764784e0abd3009fe18c3828da8bbbb0f64.png)
![\[=\epsilon^n gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)\]](http://latex.artofproblemsolving.com/8/d/0/8d0ce9d00973659eab08fd6309dd12bcdcbc2f73.png)
by basic simplification of greatest common divisor function. Now basically our original statement is equivalent to proving that for 
we have that,![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \le 2 \ \ \ \ \ \ \ (1)\]](http://latex.artofproblemsolving.com/e/e/b/eeb0b03a5c841c67356ee078bb632ddc46471bfb.png)
considering some prime 
such that 
holding for each 
for any 
immediately consider all the other 
type statements which would give us 
by Euclid's Lemma again, and finally 
.![\[b_1^n \equiv b_2^n \equiv \dots \equiv b_n^n \equiv -\prod_{j=1}^{n}b_j \ (mod \ p)\]](http://latex.artofproblemsolving.com/9/c/1/9c126d97405c5708d1690678126a8de521af5720.png)
and if we take product of all the individual statements, ![\[\left(\prod_{i=1}^{n}b_i\right)^n \equiv \left(-\prod_{i=1}^{n}b_i\right)^n \ (mod \ p) \implies 2\left(\prod_{i=1}^{n}b_i\right) \equiv 0 \ (mod \ p)\]](http://latex.artofproblemsolving.com/7/1/c/71c2309ac46ee4ba3cd50c63d1c0414763d1bf38.png)
due to the fact that ![\[p \mid 2\left(\prod_{i=1}^{n}b_i\right) \implies p \mid \left(\prod_{i=1}^{n}b_i\right)\]](http://latex.artofproblemsolving.com/2/d/1/2d1d64768230e4a963b68ea3009077a1ff8bf95c.png)
but by consecutive Euclid's Lemma application we must have that ![\[4 \mid \left(b_j^n+\prod_{i=1}^{n} b_i\right) \ \forall j\]](http://latex.artofproblemsolving.com/0/0/2/002cda18e492047be63183a83e04026880787b28.png)
now if any 
for some ![\[4 \mid b_j^n+\prod_{i=1}^{n}b_i\]](http://latex.artofproblemsolving.com/2/4/6/2465e77536bcf141d24e3421ace98ef3f52ed4b0.png)
such that 
gives us 
and again contradicts the ![\[\prod_{i=1}^{n}b_i \equiv 1 \ (mod \ 4)\]](http://latex.artofproblemsolving.com/e/4/8/e48c004ba2c1f7efe4280153397b69fcfcc8fe7d.png)
then we have 
for each 
since 
for any ![\[1 \equiv \prod_{i=1}^{n}b_i \equiv (-1)^n \equiv (-1) \ (mod \ 4)\]](http://latex.artofproblemsolving.com/8/a/0/8a079a0c9b454f69f320115d6c182a45ee713190.png)
contradicting our assumption.![\[\prod_{i=1}^{n}b_i \equiv (-1) \ (mod \ 4)\]](http://latex.artofproblemsolving.com/3/9/c/39cc7f2d040b7869c9344ccb0eb4767de57e936a.png)
in which case 
for each 
when we combine the following facts:
Thus we have that, ![\[(-1) \equiv \prod_{i=1}^{n}b_i \equiv 1^n \equiv 1 \ (mod \ 4)\]](http://latex.artofproblemsolving.com/b/e/2/be23b0659fec952a5c5cf3eb9995c7000d89c81c.png)
which contradicts our assumption again. Hence we have covered all possible cases and deduced that first, ![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)=2^a\]](http://latex.artofproblemsolving.com/c/e/f/cefa417227eaefe41115dd6240c8a9f3ba74be12.png)
for some 
and thus ![\[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \mid 2\]](http://latex.artofproblemsolving.com/c/4/0/c40eb3c38ebc4d58ce4b989403089725e8328c74.png)
which in combination with 
gives us our required 
and thus we are done. 
until their GCD is 
.
for all ![\[-P^n = (-P)^n \equiv a_1^n a_2^n \dots a_n^n = P^n \pmod{k}.\]](http://latex.artofproblemsolving.com/4/f/1/4f1b33e7486aa3d7e8cd6895427c2dd06f0d47cd.png)
If 
which is a contradiction. Therefore we can divide both sides by 
,
,
and 
so that it suffices to prove 
as then 
To this end, suppose that an odd prime 
for all 
,![\[Q^n \equiv x_1^n \dotsm x_n^n \equiv \underbrace{(-Q) \dotsm (-Q)}_{n \text{ times}} \equiv -Q^n \pmod{p}.\]](http://latex.artofproblemsolving.com/0/1/2/01219478ed7f0bfec250663390beb15847557603.png)
This implies that 
for some 
.
case, thankfully it's pretty trivial
.
,
.
we have![\[\gcd(a_1^n + P, \dots, a_n^n + P) = d^n \gcd(b_1^n + Q, \dots, b_n^n + Q)\]](http://latex.artofproblemsolving.com/c/2/9/c29edf7e1aeb7800ee393a200d0e5d5c8fa59a8e.png)
and![\[2d^n = 2\gcd(a_1,\dots, a_n)^n\]](http://latex.artofproblemsolving.com/7/6/c/76cfef37322df722c60a620bfeba5bf7d79814b4.png)
Then note,![\[\gcd(a_1^n + P, \dots, a_n^n + P) \le 2\gcd(a_1,\dots, a_n)^n \iff \gcd(b_1^n + Q, \dots, b_n^n + Q) \le 2\]](http://latex.artofproblemsolving.com/b/f/6/bf690762ba5029bbdf45110c3d46d0021d056cd0.png)
.
then note that all 
.
.
,![\[4\mid b_1^n + Q = b_1 \left(b_1^{n-1}+\frac{Q}{b_1}\right)\]](http://latex.artofproblemsolving.com/d/2/d/d2d12d0cc92856e9a9c9acda03dd07c32fa14484.png)
Since 
.
.![\[4 \mid b_i^n + Q = b_i \left(b_i^{n-1}+\frac{Q}{b_i}\right)\]](http://latex.artofproblemsolving.com/3/b/a/3bae7d515c09523616b94e5ea1f341694acb7fb4.png)
Since 
.
in this product, which is a clear contradiction. Similarly, we have a contradiction when 
which implies that 
.
note,![\[p\mid b_i^n + Q = b_i(b_i^{n-1}+\frac{Q}{b_i})\]](http://latex.artofproblemsolving.com/5/3/2/532d782433d6ceb2006c47ba41cfb9dfa61d66af.png)
If 
.
which is a clear contradiction. Thus, 
or in other words, 
for all ![\[Q^{n-1} \equiv (-1)^n \frac{Q^n}{Q} = -Q^{n-1} \pmod{p}\]](http://latex.artofproblemsolving.com/7/b/a/7ba3db2f6862f62b9bfcf4b7d2651c1d7abec386.png)
since 
which finishes the proof.
,
,
,
,
.
It suffices to prove that 
.
.
then 
for every 
,
.
.
This forces 
,
which would imply that 
,
,
.
.
Indeed, note that 
.
.
.
such that 
.
(by definition), we have 
,
.
If there doesn’t exist such a prime, then the 
.
since both sides are homogeneous with order 
.
for 
.
and hence 
.
and hence 
for all 
Now, assume that there exists some prime 
Thus, we have that 
However, this implies that 
and so 
which means that 
However, we clearly can't have that 
or else this implies that 
Hence, 
which is a contradiction.
Assume that 
we will prove that 
we see that 
which implies that 