AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
be a triangle such that 
. Points 
lie on segments 
, respectively, such that lines 
and 
are the angle bisectors of triangle 
. Find the measure of angle 
.
satisfy 
prove in equality.
has circumcircle 
and circumcenter 
. A circle 
with center 
intersects the segment 
at points 
and 
, such that 
, , , and 
are all different and lie on line in this order. Let 
and 
be the points of intersection of and , such that , , , , and lie on in this order. Let 
be the second point of intersection of the circumcircle of triangle 
and the segment 
. Let 
be the second point of intersection of the circumcircle of triangle 
and the segment 
.
and 
are different and intersect at the point 
. Prove that lies on the line 
.
be a point inside a triangle 
such that![\[ \angle APB - \angle ACB = \angle APC - \angle ABC.
\]](http://latex.artofproblemsolving.com/a/6/e/a6e3dc27d0457682fa22af4f918f58d9cd8403bc.png)
, 
be the incenters of triangles 
, 
, respectively. Show that the lines 
, 
, 
meet at a point.
cups labeled 
, where the 
-th cup has capacity liters. In total, there are liters of water distributed among these cups such that each cup contains an integer amount of water. In each step, we may transfer water from one cup to another. The process continues until either the source cup becomes empty or the destination cup becomes full.
Prove that from any configuration where each cup contains an integer amount of water, it is possible to reach a configuration in which each cup contains exactly 1 liter of water in at most 
steps.
Prove that in at most 
steps, one can go from any configuration with integer water amounts to any other configuration with the same property.
for which 
divides 
.
and 
, 
cannot be a power of 
.
of natural numbers such that for every pair of natural numbers 
and 
, the following inequality holds:![\[
\frac{1}{2} < \frac{\gcd(a_r, a_s)}{\gcd(r, s)} < 2
\]](http://latex.artofproblemsolving.com/1/6/7/167679c1707b957d87311298ea5b72347a9bdc45.png)
such that 
for all 
such that for all real numbers 
and 
,![\[f(xf(y))+f(y)=f(x+y)+f(xy).\]](http://latex.artofproblemsolving.com/d/2/f/d2ff6ed448cf39e7ec9bce6b944965d5e89b9878.png)
table filled with natural numbers, we say it is a divisor table if:
-th row are exactly all the divisors of some natural number 
,
-th column are exactly all the divisors of some natural number 
,
for every 
.
is given. Determine the smallest natural number 
, divisible by , such that there exists an divisor table, or prove that such does not exist., a line 
to tangent , and another circle disjoint from such that and lie on opposite sides of . The tangents to from a variable point on meet at 
and 
. Prove that, as varies over , the circumcircle of 
is tangent to two fixed circles.
be a triangle and let 
be its incircle. Denote by 
and 
the points where is tangent to sides and 
, respectively. Denote by 
and 
the points on sides and , respectively, such that 
and 
, and denote by 
the point of intersection of segments 
and 
. Circle intersects segment at two points, the closer of which to the vertex is denoted by 
. Prove that 
.
be a set of integers (not necessarily positive) such that
with 
; and are elements of (possibly equal), then 
also belongs to . is the set of all integers.
and 
. We claim that 
. Assume to the contrary that this is false. Then we can find some prime such that 
, 
, and 
. Since 
, 
if and only if 
; since 
, divides neither nor . From 
, 
or 
. Since 
, 
. Similarly,
, which contradicts 
.
. We note that for any 
in , 
must be in , so 
must be in . It follows that for all 
and 
in , 
. Hence, for all positive integers , , and , 
. As , the Frobenius coin problem tells us that all sufficiently large positive integers lie in . In other words, for some positive integer 
, all integers larger than or equal to lie in . We may suppose without loss of generality that 
.
be any integer less than . Since 
(from ) and 
, 
and 
lie in , whence 
must lie in as well. Thus, 
, as desired.
![\[m=\gcd \{c^2-d^2:c,d\in S\} \]](http://latex.artofproblemsolving.com/3/f/b/3fbce8ee4e18eebc9b01e6be85a3eb8e19b86b41.png)
is infinite, as it later turns out to be, 
is not well defined. may be a supernatural number. (http://en.wikipedia.org/wiki/Supernatural_numbers) must be assumed to be finite.
would not be well-defined. The 
of an infinite set of integers is perfectly well-defined; it is the largest integer that divides every element of the set. In your case, if you let 
be any nonzero element of 
, you must have 
, so is certainly finite.
shifty if 
(meaning is invariant under shifting by 
).
, then for any 
, ![\[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]](http://latex.artofproblemsolving.com/a/9/e/a9e93b29aa7b21432bbbc8fae63985c5dfaa71e8.png)
Since we can easily check that 
and 
we conclude exists a shifty integer.
is shifty. Assume for contradiction not. Then for GCD reasons the set of shifty integers must be 
for some 
.![\[ S \subseteq \left\{ x : x^2 \equiv m \pmod d \right\} \]](http://latex.artofproblemsolving.com/d/3/2/d3282c4f5705c412cccbd29920c5e33ee8597fa4.png)
for some fixed , since otherwise if we take any 
with distinct squares modulo , then 
is shifty, which is impossible. as in (a). In that case we need to have ![\[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod d. \]](http://latex.artofproblemsolving.com/9/f/c/9fc75dcfea5ecef20cdbf57dde00ef8bef2e1e62.png)
Passing to a prime 
, we have the following:
or equivalently 
, either 
or 
.
or 
.
, or 
, we find either 
or 
(even if 
).
or 
, say.
+ z is in S. Thus, we wish to show that we can create all residues 
where a, b are elements given in condition 1., , 
, 
are all distinct mod 
. Then, we show that 
. Since for any elements x, y, z that are in S, we know that + z, let 
and 
and we can span through all the residues.
. Then![\[ x\in S\implies m^2-x \in S \implies n^2-(m^2-x)=x + (n^2-m^2) \in S. \]](http://latex.artofproblemsolving.com/b/0/4/b04e1bb59226a5dba1cdf3ae2292fc30482c289f.png)
Therefore, it suffices to show that we can get any residue mod . From now on, we work fully in mod .
, we can get 
, which is equivalent to just 
mod . Therefore, if 
, then we can also get plus the difference of two elements of 
in . Now, it suffices to show that we cannot have![\[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod{p} \qquad (\clubsuit)\]](http://latex.artofproblemsolving.com/4/1/a/41ae96752a87bca6af8138db5957740bf62b093d.png)
for a prime , because if this were the case, then any new element we add can only be a multiple of greater; hence we will not get all possible residues. Otherwise, we will get a difference which is relatively prime to , and then we can add this difference over and over to to generate all possible residues.
holds. All equivalences are in mod . Then 
, so 
or 
. Similarly 
or 
. But 
, so 
. Therefore, either 
or 
. But neither of these are possible by condition (a)! Contradiction. This completes the proof.
is easy enough, however 
won't be used 
Let 
. Then, for every 
,![\[ s+ (y^2-x^2) \in S; \quad s+(x^2-y^2) = s- (y^2-x^2) \in S \]](http://latex.artofproblemsolving.com/b/b/a/bbafbe2f9c23c0f717e957dd7e015b18e76ddc20.png)
This will imply the fact that![\[ S = S+(y^2-x^2) \ \forall x,y \in S \]](http://latex.artofproblemsolving.com/9/6/8/968ffa4137fe242c86c62c49b05419fd0e02d935.png)
The Main Point of the Problem (and what makes this a 25+ MOHS.), then 
. We'll apply this again with instead of : as , so![\[ y^2- (x^2-s) \in S \]](http://latex.artofproblemsolving.com/a/8/b/a8bbda86b33badfd04f37e853948e9b5fd4431b9.png)
validating the Claim. 
Let . Then,![\[ s+1 \in S\]](http://latex.artofproblemsolving.com/1/6/a/16ab6866c1e255199bea3cef185ba163da616ac3.png)
(such a simple Claim, is it not?)
This is multiple (tedious) applications of 
(the tedious-ness of this does in fact contribute on why this is my favorite NT problem among my recent sessions. See 
for further exposition.)
in the problem statement, 
and 
are elements of .
![\[ \{b^2-a^2, (a^2-b)^2-b^2, (b^2-a)^2-a^2\} \in \{s_2^2-s_1^2 \mid \ \text{for} \ s_1,s_2 \in S\} \]](http://latex.artofproblemsolving.com/b/9/e/b9e6b1e965817de3cad9e7dcd1107fc6d6928f1b.png)
and we can infer from that![\[ S = S+z \cdot (b^2-a^2); \ S = S+z \cdot (a^2)(a^2-2b); \ S = S+z \cdot (b^2)(b^2-2a) \]](http://latex.artofproblemsolving.com/c/f/8/cf85b428244915b8e7a54a1d397d11dc8c46dcf5.png)
for every 
.
implies 
by 
/
/
.![\[ \gcd(b^2-a^2,a^2(a^2-2b)) = \gcd(b+a,a^2-2b) = g_1 \]](http://latex.artofproblemsolving.com/3/8/6/386f18e093f7eb560c5e1ef7e1f93e6da511518f.png)
applying the above statement with 
and 
yields![\[ S = S+g_1 \]](http://latex.artofproblemsolving.com/d/a/a/daa318c0a75b48889ac963d5063dfc2c0c8858a9.png)
and similarly with 
, we get![\[ S = S+g_1=S+g_2 \]](http://latex.artofproblemsolving.com/f/0/6/f06e9bea91b7aae94dfd6871f18fb91eadda34dd.png)
and 
are prime targets to apply the Lemma in Thirdly (I purposefully avoided another as a placeholder variable for the transitional 
, instead I picked 
from 
.)
, our job is done. To prove that, suppose 
for prime. Then,![\[ p \mid a+b, p \mid a^2-2b \Rightarrow p \mid a^2+2a, b^2-2b. \]](http://latex.artofproblemsolving.com/1/2/e/12e359f57d633fdd7fbeab27fd688ca9870fe6a9.png)
This may not seem like much, but that's the usefulness of having more than one 
s! Doing the same for the other expression,![\[ p \mid a^2-2a, b^2+2b. \]](http://latex.artofproblemsolving.com/4/1/8/41805f92e02a240082740b336cc56e83e2ad49ec.png)
Substracting yields 
--- which means either 
and even or 
which is impossible as . explicitly to prove the computation in Thirdly. 
with 
. have 
we are done. Otherwise are both 
, so taking implies the desired. with , note 
, 
. Thus 
for all integers by this argument. Such observations imply that consists of a set of residues modulo some integer 
. Let 
and be minimal. For any , we claim 
. This is because we must have 
by the minimality of . We claim 
, which suffices. Otherwise, let 
be prime. Let be the given relatively prime elements of . Then 
implies that at least one of 
and 
holds. Since and are relatively prime, we cannot have 
. Note that all elements of are 
modulo . Then we have is one of and 
modulo . The second case is clearly bad, so 
. Similarly 
, which contradicts the given, so we are done.
.
, then from we get 
. Then by induction we have 
for 
(*)
,
and 
. Suppose that 
then there exists such that 
![\[ \Leftrightarrow \left\{ \begin{array}{l}
p \mid {a^2} - {b^2}\\
p \mid {({a^2} - a)^2} - {a^2}\\
p \mid{({b^2} - b)^2} - {b^2}
\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}
\left[ \begin{array}{l}
p \mid a - b\\
p \mid a + b
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {a^2} - 2a\\
p \mid {a^2}
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {b^2} - 2b\\
p \mid {b^2}
\end{array} \right.
\end{array} \right.\]](http://latex.artofproblemsolving.com/8/7/5/875cdea74967a17dcc59ad319ab2389fa37a4888.png)
But all the cases can happen will lead to a contradiction that 
.
, then there exists 
such that 
by Bezout Lemma
, we lead to 
. We will show the claim by induction
are in 
then 
and from induction, 
is not a perfect square, let it be 
for 
(Since 
)
, means 
and 
from induction, then 
and done!!!
, all residues modulo are in .
are the only residues in with 
. Then for any we must have 
. Summing 
is same for each . As 
, so 
. Thus 
and 
(if 
). Now 
. If 
, then 
, forcing 
, contradicting . Thus 
and 
. Then 
. But then for any , either 
or 
, contradiction. 
and 
. By Cauchy-Davenport there 
has cardinality at least 
. But also there is subset of . This forces . We can finish as before. 
, all residues modulo are in . are only residues modulo with 
. Pick a prime dividing 
. As before all are congruent modulo . Thus each 
are congruent modulo . This basically means for any 
, 
is same modulo for any choice of . But by previous claim, we know the residues 
are in (modulo ), forcing 
mod , contradiction. 
. Let 
. We Claim that
This follows by fixing and using induction on 
(by using (b) two times for 
or 
). By our Claim, can be anything modulo , hence 
. 
is dropped):
shifty if (meaning is invariant under shifting by )., then for any , Since we can easily check that and we conclude exists a shifty integer. is shifty then 
is as well (by swapping 
), here is another solution. It's not as efficient but the idea is basically a carbon copy of the technique used in the ELMO problem and I think it's pretty neat: covers all residues modulo 
for any prime and 
. Surprisingly, most of the work is to prove this for 
. Let , and let 
be the set of residues modulo of , so we want to prove that 
. Suppose otherwise, and fix 
, so 
for all 
. As varies these are all distinct, hence
Summing both sides, this means that
as 
. Hence it follows that is constant, so 
.
, then we have 
, so 
. But then either divides 
or 
for all , violating the first condition.
, then we have 
. But then 
, so 
, which is a contradiction.. Now, to extend to , the same "sum argument" applied to the set of residues 
, which we will define as 
, implies that
for all 
. But there exists 
such that 
but 
by the case, so if 
then 
, hence we cannot have 
. It follows that 
., forms a complete residue set 
. Then and are shifty, so it follows that covers all of 
, as desired. 
then for any 
we have 
and thus 
Now, if we let 
then for any 
we have 
for any integer . Therefore, if we find 
such that 
then we are done by Bezout's. Suppose
Then the second plus the first is 
. Since 
we have 
Similarly, 
so 
If then odd which violates the second one. Now, so we can switch any with to get from the second one 
and 
, impossible. Therefore we are done.
is odd, and since 
is also in the set and 
. Other elements in the set are clearly 
and 
Then note that 
Similarly 
so 
.
.
similarly 
. Now since 
, by bezout's all integers are then in .
then it follows that 
. contains every residue 
for prime power 
.
, it follows for all . FTSOC suppose not. It must follow that 
for any 
, so can only take on residue . appears. However, it then follows that 
, so either 
or 
.
or , then this contradicts relatively prime . If all residues are 
, then this contradicts relatively prime 
.
is nonzero 
. reaches every residue 
. Shifting by 
repeatedly gives the result.
are elements of , then 
. Indeed, this follows as 
be two elements of that satisfy (a).
.
as 
by the conditions in (a). Furthermore, 
Assume for the sake of contradiction that 
is the common GCD; then it follows 
and 
, so 
. On the other hand, all three terms cannot be even, so this implies . 
that sum to and 
. It follows that if , then 
and 
are both in , which is enough.
such that, for all 
, 
. Notice that showing 
would finish.
. Then we have 
, so 
.
, we find 
.
, they must equal 1, so . Otherwise, we claim either 
or 
equals 1. Note the first expression equals![\[\gcd(a^2-b^2,a^2-2b) = \gcd((a+b)(a-b), b(b-2)) = \gcd((a+b)(a-b),b-2),\]](http://latex.artofproblemsolving.com/1/1/7/1178021b6bdc0659ca5d5ebaf939a96eda8f0627.png)
, the expression equals 
. Similarily, the second expression equals 
, so if neither expression equals 1, 
, contradiction. is also in , Bezout's on the determined coprime pair tells us . 
be called translater if 
I claim there exists a translater:
we have that 
and thus, 
and thus, 
is a translater. for some 
We have that the set 
Hence, 
Let 
We now have the following:
or 
However, in either cases, this is a contradiction.
which only satisfies for the set 
satisfying
Prove
operations will yield a positive operation: making it similar to a Euclidean Algorithm step of 
instead of 
--- which doesn't seem like a groundbreaking observation but simplifies the matter of interpreting the values of![\[ S_{k-\text{modified}} = \{k^2- s \mid \ \text{for} \ s \in S \} \]](http://latex.artofproblemsolving.com/c/9/0/c90e23e71d1bf688c54f75643c8998c48526cef2.png)
(explained more in Motivation, as usual. Find the 
hidden for the hint.)
For those wondering 
,
'
call 
nice if
.
Playing with 
,
(this will be further referred as 
as I'm lazy.) However, why 
should be equal to 
,
,
--- and then I saw that 
yields all elements of 
.
and 
.
It should come as no surprise that I had a more pleasant experience on handling ![\[ a^2-b, a^2-a, b^2-a, b^2-b \]](http://latex.artofproblemsolving.com/3/b/d/3bd36fed1131f4ef566c7e3515d803acbadbcdcb.png)
elementarily formed numbers, since there's a guarantee that when we operate on 
be formed. After forming that number, it's also in our best interests to come up with close numbers to it; and theoretically proceed from a basis of four numbers to prove ![\[ 18,20,42,44 \in S, \ \text{with the addition of} \ 7^2-20 = 29 \in S \]](http://latex.artofproblemsolving.com/2/b/b/2bbabeeac4e4cba0775894fc7e340ac2a7e3bd39.png)
are far apart from each other. With ![\[ 4,6,20,22 \in S\]](http://latex.artofproblemsolving.com/8/b/c/8bcf4450947b109979b013e069872afc5b6c9d94.png)
with 
.
.
,
:![\[ 4^2- 5 = 11 \in S, \ 3^2-11 = -2 \in S\]](http://latex.artofproblemsolving.com/5/0/9/5095533d43de2b66a2b4852d30af52c8c130b7e8.png)
and doing that enabled me to go further down to ![\[ (-2)^2-5 = -1 \in S, \ (-1)^2-(-1) = 2 \in S, \ 2^2-3 = 1 \in S. \]](http://latex.artofproblemsolving.com/7/e/2/7e2eab1cfe0ba58a53f6a80d696321f90b2744bf.png)
and then we get the legendary duo of 
--- and this opened my mind to the possibility of 
the outcome of the procedure![\[ x,y \in S \Rightarrow x^2-y \in S\]](http://latex.artofproblemsolving.com/2/9/b/29b732540648a32951172250f4c379c7fae3586e.png)
by bounding the values of either 
viable Solution.)
.
,
except when 
--- so the pair 
is not a nice pair; and try to prove that 
!
,
Hint 2: reflection to 
and 
.
will solve the problem.
While the 
strat works for small 
in an effective way, ![\[ x^2-y \in S. \]](http://latex.artofproblemsolving.com/e/5/5/e55eab040caf942dc4f67a14a3295cf77265d9b4.png)
.![\[ x^2-(x^2-1) = 1 \in S_{x,x^2-1} \]](http://latex.artofproblemsolving.com/b/b/d/bbde6e0104ff8ba5056b5abf3235b27005781fe3.png)
and we immediately win --- with the condition that 
(or, in more simple terms, 
.
with each other, and applying the same method of![\[ (x-2)^2-(x^2-3) = -4x+7 \in S\]](http://latex.artofproblemsolving.com/0/2/b/02b1d268a187a82c90674891337db78a1b0fa8cd.png)
yielded bleak prospects for explicitly size-bounding a resulting 
!![\[ \text{there does not exist} \ p \ \text{prime so that} \ a \equiv 2 \pmod p \ \text{and} \ b \equiv 2 \pmod p.\]](http://latex.artofproblemsolving.com/e/9/0/e90ad9de11edc0edfe18dfc2d54cfc79a96ad4c2.png)
Since the terms 
and the term 
seems so different from each other, I tried forming the sets![\[ S^{\text{[2]}} = \{s^2 \mid s \in S\}, \quad S^{\text{[1]}} = S \]](http://latex.artofproblemsolving.com/9/b/0/9b0852567fe2e34340d69a7dfa0eb59f383efc12.png)
to differentiate them explicitly. This helped me see the error in my ways: I've been trying so hard to take ![$x,y \in S^{[2]}$](http://latex.artofproblemsolving.com/f/0/6/f066c93bfded998165831bf63191c80296507df1.png)
such as 
on 
instead of taking, say,![\[ (x,y) = (5,7^2-5) \Rightarrow 5^2-(7^2-5) \in S \]](http://latex.artofproblemsolving.com/5/f/0/5f027fc78f2cb745860ece85a9b5b7c805819451.png)
this also helped me realize that 
doesn't help as it returns 
,
(not really) the node 
in the number line twice with respect to the point 
.![\[\begin{tabular}{p{12cm}}
Our goal isn't necessarily to create $1 \in S$, but to make some shift equal to 1!
\end{tabular} \\ \]](http://latex.artofproblemsolving.com/6/4/e/64e4647998c068ff1d510aa6c986691b56b3fc45.png)
this mirrored the Euclidean Algorithm more than anything else, but there's the elusive challenge of applying ![\[ s_1,s_2 \in S \Rightarrow S = S+s_2^2-s_1^2; \]](http://latex.artofproblemsolving.com/3/b/3/3b3d2aacfc88f71cb44b45d33d313e627ab9cd2d.png)
what if we could make some 
appear in the substraction of squares? To be exact, this is just a matter of factorization, but isn't that all Hensel's Lemma on 
do?
After doing some computation work on the ![\[ \gcd(b^2-a^2, (a^2-b)^2-b^2) = \text{not exactly 1} \]](http://latex.artofproblemsolving.com/b/6/d/b6d31cc96e166cdbe8d0a5efb194ef58c7623f86.png)
due to the existence of some pesky 
not canceling out with 
.![\[ p \mid a+b, p \mid a^2+2a, \ \text{and} \ p \mid b^2-2b. \]](http://latex.artofproblemsolving.com/f/b/7/fb7ddf787022b7741b61aa1dae9509e35c643804.png)
As 
is out of the question, this brought a suspicion: what if![\[ a \equiv -2 \ \text{mod} \ p, \ \text{and} \ b \equiv 2 \ \text{mod} \ p? \]](http://latex.artofproblemsolving.com/4/6/c/46cb7ea28a53fcf071e41f43ec3ac537b27bceb8.png)
For example, I tried analyzing 
where 
are divisible by 
.
,![\[ S_{5,16} = S_{a,a^2-b} \subseteq S_{5,9} \]](http://latex.artofproblemsolving.com/c/f/0/cf05dccf8a211a6f76667fe9ef2a4729aa84c59a.png)
and that finishes the problem, since 
is a nice pair.
is a bit scary, but they can be factored as well, right? Also, there are four elementary formed terms of the original set 
that can be compared with 
both complement each other towards a happy ending.![\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]](http://latex.artofproblemsolving.com/8/4/2/842413e566043c96b7a8f2300401b08af9d8ba48.png)
Final Comments: This might seem like a long thread; but in total, I don't think this to be a scary problem.![\[ (a^2-a)^2-(b^2-b) \in S \]](http://latex.artofproblemsolving.com/8/7/4/87411bc75ab81e4a413d802d5ff67afde74fb2e1.png)
reflection among the negatives might carve a quick way into the Solution.
be positive integers. Then there exists integers 
such that![\[\sum_{i=1}^{m} a_ix_i = \gcd(a_1, a_2, ..., a_m)\]](http://latex.artofproblemsolving.com/9/8/f/98fe94ca90cc40bdb6cfcae0a9ca29764e97a29c.png)
Also, 
is the least positive integer satisfying this property.
.
,
.
for all integers 
and 
.
.
.
and 
.
such that 
,
,
.
was irrelevant. But then I realized if all numbers of 
and noticing that we are just through.
elements? I just applied it 
is in 
,
,
.
,
,![$(a^2-b^2) + [(a^2-b^2) + x] = 2(a^2-b^2)+x \in S$](http://latex.artofproblemsolving.com/3/a/a/3aa1873e430baa39aca938296577d66e491d7b2e.png)
,![$(a^2-b^2) + [(a^2-b^2)+ x] = 3(a^2-b^2) + x \in S$](http://latex.artofproblemsolving.com/8/c/0/8c0264fdfa2939f7dc5b0104939d641851de0b54.png)
,
for all 
.
,
,
,
.
,
,
and any 
,
does the trick. Thus, we have that 
for all integers 
be elements of 
is in 
is in 
and 
.
,![$$x + k\gcd(a^2-b^2, c^2-d^2) = x + k[(a^2-b^2)r + (c^2-d^2)s] = [x + (a^2-b^2)(rk)] + (c^2-d^2)(sk) \in S,$$](http://latex.artofproblemsolving.com/d/6/f/d6f3137925fded664605d1affd5a0e2359a643b5.png)
as desired. 
,
.
,
.
Note that 
,
,
.
Similarly, note that 
Note that 
,
Thus, 
Thus, by the second claim, we have that for any integer 
and 
Now, note that 
since if a prime 
,
and 
,
Now, note that for any integer 
so since 
,![\begin{align*}
S &\ni x + \gcd(b-2, b^2-a^2)(sk) \\
&= a + \gcd(a-2, b^2-a^2)(rk) + \gcd(b-2, b^2-a^2)(sk) \\
&= a + k[r\gcd(a-2, b^2-a^2) + s\gcd(b-2, b^2-a^2)] \\
&= a+k,
\end{align*}](http://latex.artofproblemsolving.com/4/3/4/434e2697f6b4d0648f795886d899c2ded3e5e0f9.png)
so 
for any integer 
,
,