USAMO 2001 Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MithsApprentice

2390 posts

MithsApprentice

#1 h Sep 30, 2005, 8:14 PM • 3 Y

Y by Davi-8191, Adventure10, Mango247

Let $S$ be a set of integers (not necessarily positive) such that

(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$ ;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$ .

Prove that $S$ is the set of all integers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MithsApprentice

2390 posts

MithsApprentice

#2 h Sep 30, 2005, 8:14 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mustafa

580 posts

mustafa

#3 h Jan 20, 2007, 5:42 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mstoenescu

316 posts

mstoenescu

#4 h Jan 20, 2007, 8:31 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cuopbientcd

169 posts

cuopbientcd

#5 h Jan 21, 2007, 11:17 AM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#6 h Jan 6, 2011, 4:02 AM • 13 Y

Y by QuocBao, Nguyenhuyhoang, SMOJ, huynguyen, r31415, guptaamitu1, mijail, Adventure10, Mango247, and 4 other users

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jatin

547 posts

jatin

#7 h Aug 13, 2011, 5:50 AM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#8 h Aug 13, 2011, 3:40 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#9 h Jul 11, 2017, 4:12 AM • 8 Y

Y by anantmudgal09, vsathiam, Delray, mmathss, v4913, mijail, Kobayashi, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yunseo

163 posts

yunseo

#11 h May 1, 2019, 11:34 PM • 1 Y

Y by Adventure10

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.

This post has been edited 1 time. Last edited by yunseo, May 1, 2019, 11:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#12 h May 26, 2020, 12:21 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexiaslexia

110 posts

alexiaslexia

#13 h Feb 19, 2021, 3:24 PM • 2 Y

Y by yayups, ATGY

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$

Magical Transformation?

$\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.

Motivation: Replicating the Legendary Euclids, with two bases and Hensels.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#14 h Feb 28, 2021, 11:43 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nbdaaa

347 posts

nbdaaa

#15 h Jun 28, 2021, 9:12 AM

Y by

Bezout Lemma
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!!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7352 posts

DottedCaculator

#16 h Oct 26, 2021, 9:12 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

guptaamitu1

656 posts

guptaamitu1

#17 h Feb 13, 2022, 1:21 PM • 1 Y

Y by mijail

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$

Motivation

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#18 h Mar 24, 2022, 8:50 PM

Y by

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$

This post has been edited 1 time. Last edited by IAmTheHazard, Mar 24, 2022, 8:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1717 posts

awesomeming327.

#19 h Dec 26, 2022, 3:18 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vsamc

3789 posts

vsamc

#20 h Jun 9, 2023, 6:42 PM

Y by

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

Solution

This post has been edited 1 time. Last edited by vsamc, Jun 9, 2023, 6:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AtharvNaphade

341 posts

AtharvNaphade

#21 h Sep 12, 2023, 9:25 PM

Y by

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$ .

This post has been edited 1 time. Last edited by AtharvNaphade, Sep 12, 2023, 9:59 PM
Reason: e

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1541 posts

YaoAOPS

#22 h Oct 9, 2023, 4:11 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8861 posts

HamstPan38825

#23 h Dec 18, 2023, 4:18 PM

Y by

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.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 18, 2023, 4:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

795 posts

shendrew7

#24 h Mar 27, 2024, 3:42 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

623 posts

Ilikeminecraft

#25 h Apr 25, 2025, 4:15 PM

Y by

Let an integer $x$ be called translater if $S = S + x.$ I claim there exists a translater:

First, notice that if $x, m, n\in S,$ we have that $n^2 - x\in S,$ and thus, $m^2 - (n^2 - x) = x + m^2 - n^2 \in S,$ and thus, $S = S + m^2 - n ^2.$

Now I claim that $1$ is a translater.

AFTSOC it isn't. Then, because of GCD reasons, we know that the set of alternater integers is all integer multiples of $d$ for some $d > 2.$ We have that the set $S = \{x : x^2\equiv m\pmod d\}.$ Hence, $a^2 \equiv b^2 \equiv (a^2 - a)^2 \equiv (b^2 - b)^2\pmod d.$ Let $p\mid d.$ We now have the following:
\begin{enumerate}
\item $a^2 \equiv (a^2 - a)^2 \implies a^3(a - 2) \equiv 0 \implies a \equiv 0, 2.$
\item similarly, $b\equiv0, 2$
\item $a^2\equiv b^2\pmod p \implies a \equiv \pm b \pmod p \implies a \equiv b \equiv 0$ or $a\equiv b\equiv 2 \pmod p.$ However, in either cases, this is a contradiction.
\end{enumerate}

Hence, 1 is a translater, and so $S = 1 + S,$ which only satisfies for the set $S = \mathbb Z.$

Z K Y