When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Furthermore, please do not "hide" any portion of the solution. Please use LaTeX for posting solutions. Thanks.

Sorry to bump up such an old topic, but does anyone have a solution to this?

Look at http://www.kalva.demon.co.uk/usa/usoln/usol015.html

I read it and I feel Math be beautyful!I am happy!

Let $c = a^2 - b$ and $d = b^2 - a$. We claim that $\gcd(a^2 - b^2, a^2 - c^2, b^2 - d^2) = 1$. Assume to the contrary that this is false. Then we can find some prime $p$ such that $a^2 \equiv b^2 \pmod{p}$, $a^2 - b \equiv \pm a \pmod{p}$, and $b^2 - a \equiv \pm a \pmod{p}$. Since $p | a^2 - b^2$, $p | a$ if and only if $p | b$; since $\gcd(a,b) = 1$, $p$ divides neither $a$ nor $b$. From $b^2 \equiv a^2 \equiv b \pm a$, $b^2 \equiv 0 \pmod{p}$ or $b^2 \equiv 2b \pmod{p}$. Since $p \not | b$, $p | b-2$. Similarly,$p | a-2$, which contradicts $\gcd(a-2, b-2) = 1$. Let $z = a$. We note that for any $x,y$ in $S$, $y^2 - z$ must be in $S$, so $x^2 - (y^2 - z) = (x^2 - y^2) + z$ must be in $S$. It follows that for all $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$ in $S$, $z + \sum_{i=1}^n (x_i^2 - y_i^2) \in S$. Hence, for all positive integers $A$, $B$, and $C$, $z + A(a^2 - b^2) + B(a^2 - c^2) + C(b^2 - d^2) \in S$. As $\gcd(a^2 - b^2, a^2 - c^2, b^2 - d^2) = 1$, the Frobenius coin problem tells us that all sufficiently large positive integers lie in $S$. In other words, for some positive integer $M$, all integers larger than or equal to $M$ lie in $S$. We may suppose without loss of generality that $M \geq 2$. Let $k$ be any integer less than $M$. Since $(M+1)^2 - k > (M+1)^2 - M > M$ (from $M \geq 2$) and $M+1 > M$, $(M+1)^2 - k$ and $M+1$ lie in $S$, whence $(M+1)^2 - ((M+1)^2 - k) = k$ must lie in $S$ as well. Thus, $S = \mathbb{Z}$, as desired.

The official solution is given here. I have a doubt in it. In the last line of the first paragraph of the solution, it is said that \[m=\gcd \{c^2-d^2:c,d\in S\} \] But if $S$ is infinite, as it later turns out to be, $m$ is not well defined. In fact, $m$ may be a supernatural number. (http://en.wikipedia.org/wiki/Supernatural_numbers) So for this argument to work, I think that $S$ must be assumed to be finite. Could someone kindly clarify this?

I don't see why $m$ would not be well-defined. The $\gcd$ 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 $s$ be any nonzero element of $\{c^2 - d^2 : c, d \in S\}$, you must have $m \leq |s|$, so $m$ is certainly finite.

Call an integer $d > 0$ shifty if $S = S+d$ (meaning $S$ is invariant under shifting by $d$). First, note that if $u, v \in S$, then for any $x \in S$, \[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]Since we can easily check that $|S| > 1$ and $S \neq \{n, -n\}$ we conclude exists a shifty integer. Now we contend that $1$ is shifty. Assume for contradiction not. Then for GCD reasons the set of shifty integers must be $d {\mathbb Z}$ for some $d > 2$. So it follows that \[ S \subseteq \left\{ x : x^2 \equiv m \pmod d \right\} \]for some fixed $m$, since otherwise if we take any $p,q \in S$ with distinct squares modulo $d$, then $q^2-p^2 \not\equiv 0 \pmod d$ is shifty, which is impossible. Now take $a,b \in S$ 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. \]Passing to a prime $p \mid d$, we have the following: Since $a^2 \equiv (a^2-a)^2 \pmod p$ or equivalently $a^3(a-2) \equiv 0 \pmod p$, either $a \equiv 0 \pmod p$ or $a \equiv 2 \pmod p$. Similarly, either $b \equiv 0 \pmod p$ or $b \equiv 2 \pmod p$. Since $a^2 \equiv b^2 \pmod p$, or $a \equiv \pm b \pmod p$, we find either $a \equiv b \equiv 0 \pmod p$ or $a \equiv b \equiv 2 \pmod p$ (even if $p=2$). This is a contradiction. Remark: The condition (a) cannot be dropped, since otherwise we may take $S = \left\{ 2 \pmod p \right\}$ or $S = \left\{ 0 \pmod p \right\}$, say.

For any elements x, y, z that are in S, we know that $(x^2-y^2)$ + z is in S. Thus, we wish to show that we can create all residues $\mod a^2 - b^2$ where a, b are elements given in condition 1. We then show that $a$, $b$, $a^2-a$, $b^2-b$ are all distinct mod $a^2-b^2$. Then, we show that $(a^2-a)^2-(b^2-b)^2 \not\equiv 0 \mod a^2-b^2$. Since for any elements x, y, z that are in S, we know that $(x^2-y^2)$ + z, let $x = a^2-a $ and $y= b^2-b$ and we can span through all the residues.

Suppose we have some $m,n\in S$. Then \[ x\in S\implies m^2-x \in S \implies n^2-(m^2-x)=x + (n^2-m^2) \in S. \]Therefore, it suffices to show that we can get any residue mod $a^2-b^2$. From now on, we work fully in mod $a^2-b^2$. From just $\{a,b\}$, we can get $\{a^2-a,a^2-b,b^2-a,b^2-b\}$, which is equivalent to just $\{a^2-a, b^2-b\}$ mod $a^2-b^2$. Therefore, if $x\in S$, then we can also get $x$ plus the difference of two elements of $\{a^2, b^2, (a^2-a)^2, (b^2-b)^2\}$ in $S$. 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)\]for a prime $p$, because if this were the case, then any new element we add can only be a multiple of $p$ greater; hence we will not get all possible residues. Otherwise, we will get a difference which is relatively prime to $a^2-b^2$, and then we can add this difference over and over to $x$ to generate all possible residues. Suppose $(\clubsuit)$ holds. All equivalences are in mod $p$. Then $p\mid (a^2-a)^2-a^2=a^3(a-2)$, so $a\equiv 0$ or $a\equiv 2$. Similarly $b\equiv 0$ or $b\equiv 2$. But $a^2\equiv b^2$, so $a \equiv \pm b$. Therefore, either $a\equiv b \equiv 2 \pmod p$ or $a\equiv b \pmod p$. But neither of these are possible by condition (a)! Contradiction. This completes the proof.

A double (or triple, depending on how you word it) Euclidean Algorithm. Using the condition $(a,b) = 1$ is easy enough, however $(a-2,b-2) = 1$ won't be used $\textit{unless you've come up with the thing.}$ $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{A Simple Way to Look at It.}$ Let $x,y \in S$. Then, for every $s \in S$, \[ s+ (y^2-x^2) \in S; \quad s+(x^2-y^2) = s- (y^2-x^2) \in S \]This will imply the fact that \[ S = S+(y^2-x^2) \ \forall x,y \in S \]$\color{green} \rule{25cm}{0.4pt}$ $\color{green} \textbf{Proof 1.}$ The Main Point of the Problem (and what makes this a 25+ MOHS.) If $s \in S$, then $x^2-s \in S$. We'll apply this again with $y$ instead of $x$: as $x^2-s \in S$, so \[ y^2- (x^2-s) \in S \]validating the Claim. $\blacksquare$ $\blacksquare$

$\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{Making the set} \ S \ \textbf{behave like} \ \mathbb{Z} \ \textbf{by compressing the shift into} \ 1.$ Let $s \in S$. Then, \[ s+1 \in S\](such a simple Claim, is it not?) $\color{red} \rule{25cm}{0.4pt}$ $\color{red} \textbf{Proof 2.}$ This is multiple (tedious) applications of $\color{green} \textbf{A Simple Way to Look at It}$ (the tedious-ness of this does in fact contribute on why this is my favorite NT problem among my recent sessions. See $(\bigstar \bigstar)$ for further exposition.) Firstly, we can easily infer that given $a,b$ in the problem statement, $a^2-b$ and $b^2-a$ are elements of $S$. Secondly, We see that \[ \{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\} \]and we can infer from $\color{green} \textbf{A Simple Way to Look at It}$ 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) \]for every $z \in \mathbb{Z}$. Thirdly, as $S = S+d_1 = S+d_2$ implies $S = S+\gcd(d_1,d_2)$ by $\textbf{Euclid}$/$\textbf{Bezout}$/$\textit{just repeat the iteration till you get the smallest number}$. Since \[ \gcd(b^2-a^2,a^2(a^2-2b)) = \gcd(b+a,a^2-2b) = g_1 \]applying the above statement with $d_1 = b^2-a^2$ and $d_2 = a^2(a^2-2b)$ yields \[ S = S+g_1 \]and similarly with $\gcd(b+a,b^2-2a) = g_2$, we get \[ S = S+g_1=S+g_2 \] Fourthly, $g_1$ and $g_2$ are prime targets to apply the Lemma in Thirdly (I purposefully avoided another $d$ as a placeholder variable for the transitional $\text{gcd}$, instead I picked $g$ from $\textbf{g}cd$.) If $\gcd(g_1,g_2) = 1$, our job is done. To prove that, suppose $p \mid g_1, p \mid g_2$ for $p$ prime. Then, \[ p \mid a+b, p \mid a^2-2b \Rightarrow p \mid a^2+2a, b^2-2b. \]This may not seem like much, but that's the usefulness of having more than one $g_i$s! Doing the same for the other expression, \[ p \mid a^2-2a, b^2+2b. \]Substracting yields $p \mid 4a, p \mid 4b$ --- which means either $p = 2$ and $a,b$ even or $p \mid a,b$ which is impossible as $(a,b) = 1$. $\blacksquare$ $\blacksquare$ $\blacksquare$ Note that we did use the condition $(a-2,b-2) = 1$ explicitly to prove the $\gcd$ computation in Thirdly.

Observation: There are at least two elements $c,d\in S$ with $|c|\ne |d|$. Proof: If the $a,b$ have $|a|\ne |b|$ we are done. Otherwise $a,b$ are both $\pm1$, so taking $a^2-b$ implies the desired. Now, for any $c,d\in S$ with $|c|\ne |d|$, note $\forall t\in S$, $c^2-(d^2-t)=c^2-d^2+t\in S$. Thus $k(c^2-d^2)+t\in S$ for all integers $k$ by this argument. Such observations imply that $S$ consists of a set of residues modulo some integer $d\ne0$. Let $d>0$ and $d$ be minimal. For any $a,b$, we claim $a^2\equiv b^2\pmod{d}$. This is because we must have $d\mid a^2-b^2$ by the minimality of $d$. We claim $d=1$, which suffices. Otherwise, let $p\mid d$ be prime. Let $a,b$ be the given relatively prime elements of $S$. Then $p\mid a^2-b^2$ implies that at least one of $p\mid a-b$ and $p\mid a+b$ holds. Since $a$ and $b$ are relatively prime, we cannot have $p\mid a$. Note that all elements of $S$ are $\pm a$ modulo $p$. Then we have $a^2-a$ is one of $a$ and $-a$ modulo $p$. The second case is clearly bad, so $a^2-a\equiv a\pmod{p}\implies a^2\equiv 2a\pmod{p}\implies a\equiv 2\pmod{p}$. Similarly $b\equiv 2\pmod{p}$, which contradicts the given, so we are done.

Claim 1: $1 \in S$. Suppose $a,b,c \in S$, then from $2$ we get $(a^2-b^2)+c \in S$. Then by induction we have $c+(a^2-b^2)n \in S$ for $n \in Z$ (*) Let $A=a^2-b^2$,$B=(a^2-a)^2-a^2$ and $C=(b^2-b)^2-b^2$ Then from the conclusion in (*), we have $c +xA+yB+zC \in S$. Suppose that $d=gcd(A,B,C) >1$ then there exists $p \mid d$ such that $p \mid A,B,C$ \[ \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.\]But all the cases can happen will lead to a contradiction that $(a,b)=(a-2,b-2)=1$. Thus $gcd(A,B,C)=1$, then there exists $x,y,z$ such that $xA+yB+zC=1-c$ by Bezout Lemma Then $c+xA+yB+zC=c+1-c=1 \in S$ Claim 2 : All the integers are in $S$ From $1 \in S$, we lead to $0 \in S,-1 \in S, 2 \in S, -2 \in S$. We will show the claim by induction Suppose that all $|m| \le n$ are in $S$ Consider $n+1$ If $n+1=t^2$ then $t <n$ and from induction, $t \in S \Rightarrow t^2-0=t^2=n+1 \in S$ If $n+1$ is not a perfect square, let it be $n+1=t^2+m$ for $ 0< m < 2t+1$ (Since $t^2 <n+1 <(t+1)^2$) Then $0<m<2t+1<t^2<n$, means $m \in S \Rightarrow -m \in S$ and $t \in S$ from induction, then $t^2-(-m)=t^2+m=n+1 \in S$ and done!!!

Claim: For any prime $p$, all residues modulo $p$ are in $S$. First Proof: FTSOC $\{a_1,\ldots,a_k\}$ are the only residues in $S$ with $k < p$. Then for any $i$ we must have $\{a_i^2 - a_1,\ldots,a_i^2 - a_k \} \equiv \{a_1,\ldots,a_k\}$. Summing $ka_i^2$ is same for each $i$. As $\gcd(k,p)= 1$, so $a_1^2 \equiv \cdots \equiv a_k^2$. Thus $k \le 2$ and $p \mid a_1 + a_k$ (if $k = 2$). Now $a_1^2 - a_1 \in \{a_1,a_k\}$. If $k \ge 2$, then $a_1^2 \equiv 0$, forcing $a_1 \equiv a_k \equiv 0$, contradicting $k \ge 2$. Thus $k=1$ and $a_1^2 - a_1 \equiv a_1$. Then $a_1 \in \{0,2\}$. But then for any $a,b \in S$, either $p \mid \gcd(a,b)$ or $p \mid \gcd(a-2,b-2)$, contradiction. $\square$ Second Proof: Consider sets $\{a_1^2,\ldots,a_k^2\}$ and $\{-a_1,\ldots,-a_k\}$. By Cauchy-Davenport there $\oplus$ has cardinality at least $2k-1$. But also there $\oplus$ is subset of $\{a_1,\ldots,a_k\}$. This forces $k=1$. We can finish as before. $\square$ Claim: For any $n \in \mathbb Z_{>0}$, all residues modulo $n$ are in $S$. Proof: This is similar to previous, but we have to be a little more clever. FTSOC $\{a_1,\ldots,a_k\}$ are only residues modulo $S$ with $k < n$. Pick a prime $p$ dividing $\frac{n}{\gcd(k,n)}$. As before all $ka_i^2$ are congruent modulo $n$. Thus each $a_i^2$ are congruent modulo $p$. This basically means for any $a \in S$, $a^2$ is same modulo $p$ for any choice of $a$. But by previous claim, we know the residues $0,1$ are in $S$ (modulo $p$), forcing $0^2 \equiv 1^2$ mod $p$, contradiction. $\square$ Now fix any $m,n \in S$. Let $T = m^2 - n^2$. We Claim that $$Tk-y \in S ~~ \forall ~ y \in S, k \in \mathbb Z \qquad \qquad (1)$$This follows by fixing $y$ and using induction on $T$ (by using (b) two times for $x=m,n$ or $x=n,m$). By our Claim, $y$ can be anything modulo $T$, hence $S = \mathbb Z$. $\blacksquare$

Inspired by ELMO 2019/5, after getting this (note the condition $d>0$ is dropped): v_Enhance wrote: Call an integer $d \neq 0$ shifty if $S = S+d$ (meaning $S$ is invariant under shifting by $d$). First, note that if $u, v \in S$, then for any $x \in S$, \[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]Since we can easily check that $|S| > 1$ and $S \neq \{n, -n\}$ we conclude exists a shifty integer. and noting that if $d$ is shifty then $-d$ is as well (by swapping $u,v$), 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: The key claim is that $S$ covers all residues modulo $p^n$ for any prime $p$ and $n \geq 1$. Surprisingly, most of the work is to prove this for $n=1$. Let $n=1$, and let $S_p=\{a_1,\ldots,a_k\}$ be the set of residues modulo $p$ of $S$, so we want to prove that $k=p$. Suppose otherwise, and fix $1 \leq i \leq k$, so $a_i^2-a_j \in S_p$ for all $1 \leq j \leq k$. As $j$ varies these are all distinct, hence $$\{a_i^2-a_1,\ldots,a_i^2-a_k\} \equiv \{a_1,\ldots,a_k\} \pmod{p}.$$Summing both sides, this means that $$ka_i^2-(a_1+\cdots+a_k) \equiv a_1+\cdots+a_k \pmod{p} \implies a_i^2 \equiv \frac{2(a_1+\cdots+a_k)}{k} \pmod{p}$$as $p \nmid k$. Hence it follows that $a_i^2$ is constant, so $k=1,2$. If $k=1$, then we have $a_1^2-a_1 \equiv a_1 \pmod{p}$, so $a_1 \equiv 0,2 \pmod{p}$. But then $p$ either divides $\gcd(a,b)$ or $\gcd(a-2,b-2)$ for all $a,b \in S$, violating the first condition. If $k=2$, then we have $a_1\equiv -a_2\pmod{p}$. But then $a_1+\cdots+a_k \equiv 0 \pmod{p}$, so $a_1^2 \equiv a_2^2=0$, which is a contradiction. It follows that $k=p$. Now, to extend to $p^n$, the same "sum argument" applied to the set of residues $\pmod{p^n}$, which we will define as $\{a_1,\ldots,a_K\}$, implies that $$Ka_i^2 \equiv 2(a_1+\cdots+a_K) \pmod{p^n}$$for all $1 \leq i \leq K$. But there exists $i,j$ such that $p \mid a_i$ but $p \nmid a_j$ by the $n=1$ case, so if $p^n \nmid K$ then $\nu_p(Ka_j^2)<n,\nu_p(Ka_i^2)$, hence we cannot have $Ka_i^2 \equiv Ka_j^2 \pmod{p^n}$. It follows that $p^n \mid K \implies K=p^n$. To finish, note that by Chinese Remainder Theorem we can show that for any shifty $d>0$, $S$ forms a complete residue set $\pmod{d}$. Then $d$ and $-d$ are shifty, so it follows that $S$ covers all of $\mathbb{Z}$, as desired. $\blacksquare$

If $a,b\in S$ then for any $c\in S$ we have $a^2-c\in S$ and thus $b^2-(a^2-c)=(b^2-a^2)+c\in S.$ Now, if we let $P=\{a^2-b^2 \mid a,b\in S\}$ then for any $x\in P$ we have $c\in S\implies c+kx\in P$ for any integer $k$. Therefore, if we find $x,y,z\in P$ such that $\gcd(x,y,z)=1$ then we are done by Bezout's. Suppose \begin{align*} p &\mid a^2-b^2 \\ p &\mid (a^2-b)^2-a^2 \\ p &\mid (b^2-a)-b^2 \end{align*}Then the second plus the first is $p \mid a^4-2a^2b$. Since $\gcd(a,b)=1$ we have $p\mid a^2-2b.$ Similarly, $p\mid b^2-2a$ so $p\mid a^2-b^2+2a-2b\implies p\mid 2(a-b).$ If $p=2$ then $a,b$ odd which violates the second one. Now, $p\mid a-b$ so we can switch any $a$ with $b$ to get from the second one $p\mid a^4-2a^3\implies p\mid a-2$ and $p\mid b-2$, impossible. Therefore we are done.

EDIT: Oops, Bezout is a thing with $>2$ elements? I just applied it $3$ times to sets of two elements

Is this a fakesolve? Seems too straightforward for a 25 MOHS. At least one of $a, b$ is odd, and since $c = b^2 - a$ is also in the set and $\gcd(b^2 - a, a) = 1$. Other elements in the set are clearly $d = (c^2 - a)^2$ and $e = (c^2 - c)^2.$ Then note that $$\gcd(c+a, (c^2 - a)^2-(c^2 - c)^2) =\gcd(c+a, (a^2-a)^2 - (a^2+a)^2) = \gcd(b^2, 4a^3) = 1.$$Similarly $$\gcd(c-a, (c^2 - a)^2-(c^2 - c)^2) = 1,$$so $\gcd(c^2 - a^2, d^2-e^2) = 1$. Call $v = c^2 - b^2, w = d^2 - e^2$. Now note that $$x\in S \implies c^2 - (b^2 - x) = x + v \in S, \text{similarly } x - v \in S,$$similarly $x \in S \implies x + w \in S, x -w \in S$. Now since $\gcd(v, w) = 1$, by bezout's all integers are then in $S$.

Note that if $x, m, n \in S$ then it follows that $m^2 - (n^2 - x) = x + (m^2 - n^2) \in S$. Claim: $S$ contains every residue $\pmod{p^k}$ for prime power $p^k$. Proof. Note that if we show this for $k = 1$, it follows for all $k$. FTSOC suppose not. It must follow that $m^2 \equiv n^2$ for any $m, n \in S$, so $S$ can only take on residue $\pm a$. WLOG guarentee that $a$ appears. However, it then follows that $a^2 - a \equiv \pm a$, so either $a \equiv 0$ or $a \equiv 2$. If all residues are $0 \pmod{p}$ or $p = 2$, then this contradicts relatively prime $a, b$. If all residues are $2 \pmod{p}$, then this contradicts relatively prime $a - 2, b - 2$. Else, $2^2 - 0 = 4$ is nonzero $\pmod{p}$. $\blacksquare$ As such, it follows that $S$ reaches every residue $\pmod{a^2 - b^2}$. Shifting by $a^2 - b^2$ repeatedly gives the result.

The first observation is counterintuitively very tricky to get. The key observation is that if $x, a, b$ are elements of $S$, then $x + a^2 - b^2 \in S$. Indeed, this follows as $$x+a^2-b^2 = a^2-(b^2-x).$$ Now, let $a, b$ be two elements of $S$ that satisfy (a). Claim. $\gcd(a^2-b^2, a^2-(b^2-a)^2, b^2-(a^2-b)^2) = 1$. Proof. Notice that $$\gcd(a^2-b^2, a^2-(b^2-a)^2) = \gcd(2a-b^2, (a-b)(a+b)) = \gcd(2a-b^2, a+b)$$as $$\gcd(2a-b^2, a-b = \gcd(b(b-2), a-b) = 1$$by the conditions in (a). Furthermore, $$\gcd(a^2-(b^2-a)^2, b^2-(a^2-b)^2) = \gcd(2a-b^2, 2b-a^2) = \gcd(a+b+2, 2a-b^2).$$Assume for the sake of contradiction that $d>1$ is the common GCD; then it follows $d \mid a+b$ and $d \mid a+b+2$, so $d=2$. On the other hand, all three terms cannot be even, so this implies $d=1$. $\blacksquare$ Hence by Bezout there exists some combination of $a^2-b^2, a^2-(b^2-a)^2, b^2-(a^2-b)^2$ that sum to $1$ and $-1$. It follows that if $x \in S$, then $x+1$ and $x-1$ are both in $S$, which is enough.

Consider the set of integers $T$ such that, for all $t \in T$, $S = S+t$. Notice that showing $1 \in T$ would finish. Suppose $m,n,x \in S$. Then we have $m^2-(n^2-x) = m^2-n^2+x \in S$, so $m^2-n^2 \in T$. Setting $(m,n) = (a,b),(a^2-b,b),(b^2-a,a)$, we find $a^2-b^2,a^2(a^2-2b),b^2(b^2-2a) \in T$. If $a=b$, they must equal 1, so $1 \in T$. Otherwise, we claim either $\gcd(a^2-b^2,a^2(a^2-2b))$ or $\gcd(a^2-b^2,b^2(b^2-2a))$ 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),\] and since $\gcd(a-b,b-2)=\gcd(a-2,b-2)=1$, the expression equals $\gcd(a+b,b-2)$. Similarily, the second expression equals $\gcd(a+b,a-2)$, so if neither expression equals 1, $\gcd(a-2,b-2)>1$, contradiction. Since any linear combination of elements in $T$ is also in $T$, Bezout's on the determined coprime pair tells us $1 \in T$. $\blacksquare$