IMO Shortlist 2012, Number Theory 1

The post below has been deleted. Click to close.

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

lyukhson

127 posts

lyukhson

#1 h Jul 29, 2013, 12:32 PM • 9 Y

Y by Davi-8191, Mathuzb, Epistle, megarnie, microsoft_office_word, Adventure10, Mango247, Sedro, and 1 other user

Call admissible a set $A$ of integers that has the following property:
If $x,y \in A$ (possibly $x=y$ ) then $x^2+kxy+y^2 \in A$ for every integer $k$ .
Determine all pairs $m,n$ of nonzero integers such that the only admissible set containing both $m$ and $n$ is the set of all integers.

Proposed by Warut Suksompong, Thailand

This post has been edited 3 times. Last edited by WakeUp, Jan 4, 2014, 3:51 AM
Reason: Edited Title and Changed Format of The Problem.

Z K Y

The post below has been deleted. Click to close.

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

SCP

1502 posts

SCP

#2 h Jul 29, 2013, 3:17 PM • 14 Y

Y by odnerpmocon, agimog, pablock, qubatae, mathleticguyyy, microsoft_office_word, Math4Life7, Adventure10, Mango247, shafikbara48593762, Sedro, and 3 other users

We will prove the answer are all pairs such that $(m,n)=1$

If $d=gcd(m,n)>1$ then the set of all multiples of $d$ satisfy the question too, hence this pair isn't one we want.

If $d=1$ then by $x=y=m$ we can get all multiples of $m^2$ and similar for $n^2.$

Because $gcd(m^2,n^2)=1$ there exist $a,b$ such that $am^2-bn^2=1$

We can form $1$ with $x=am^2, y=bn^2$ and $k=-2$ .

After that is is trivial the only admissable set containing $1$ is the one 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.

lyukhson

127 posts

lyukhson

#3 h Jul 29, 2013, 4:46 PM • 2 Y

Y by Adventure10 and 1 other user

SCP wrote:

We will prove the answer are all pairs such that $(m,n)=1$

If $d=gcd(m,n)>1$ then the set of all multiples of $d$ satisfy the question too, hence this pair isn't one we want.

If $d=1$ then by $x=y=m$ we can get all multiples of $m^2$ and similar for $n^2.$

Because $gcd(m^2,n^2)=1$ there exist $a,b$ such that $am^2-bn^2=1$

We can form $1$ with $x=am^2, y=bn^2$ and $k=-2$ .

After that is is trivial the only admissable set containing $1$ is the one of all integers.

your solution is same with mine^^ I think it's a good, simple question.

Z K Y

The post below has been deleted. Click to close.

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

ssilwa

5451 posts

ssilwa

#4 h Aug 2, 2013, 9:53 PM • 5 Y

Y by samuel, Adventure10, Mango247, and 2 other users

This is ridiculous:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=151&t=507200&p=2849284&hilit=X%5E2+kxy+y%5E2#p2849284

Z K Y

The post below has been deleted. Click to close.

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

JuanOrtiz

366 posts

JuanOrtiz

#5 h Aug 10, 2013, 1:08 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

It is very easy to conjecture $(m,n)=1$ , because if $(m,n) \textgreater 1$ , it obviously doesn't work ( $A = (m,n) \times \mathbb{Z}$ ), and it is very difficult to come up with a counterexample if $(m,n)=1$ . And whenever coprime integers and $\mathbb{Z}$ are involved, one can smell Bezout. However, the condition is a quadratic one, not a linear one, so the trick is to surpass this obstacle, by introducing some expressions of degree $2$ that belong to $A$ .

Now, assume $(m,n)=1$ and we have $m,n \in A$ an admissible set. We will try to prove $A = \mathbb{Z}$ . Take any $z \in A$ . Clearly with $x=y=z$ , $kz^2 \in A \forall k$ . So if $z=1 \in A$ , we're done. So we'll try to find $x,y \in A$ such that $x^2+kxy+y^2=1$ . If $k=-2$ , we can easily factor this and it will suffice to find $x, y \in A$ such that $x-y=1$ . So if we find two consecutive integers, both in $A$ , we're done.

But remember that $am^2 \in A$ and $bm^2 \in A$ for all $a, b$ integers. By Bezout, we can set $a$ , $b$ such that $am^2-bn^2=1$ , and we have found two consecutive integers, both in $A$ . So we're done.

Z K Y

The post below has been deleted. Click to close.

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

junioragd

314 posts

junioragd

#6 h Sep 15, 2014, 3:49 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

We will prove that for all integers such that $(m,n)=1$ .It is obvious that if $(m,n)=d>1$ then every element of the set $A$ is divisible with $d$ and the set $A$ is ${...-3d,-2d,-d,0,d,2d,3d....}$ satisfayes the conditions.Now,if $(m,n)=1$ ,then plugg $x=y=m$ and $x=y=n$ that every integer of the form $k*m^2$ and $k*n^2$ is in the set,so we can pick $a$ and $b$ such that $a*m^2-b*n^2=1$ (by chineese remainder theorem),so plug $x=a*m^2$ and $y=b*n^2$ and $k=-2$ we obtain $1$ ,so now it is trivial that we have all integers.

This post has been edited 1 time. Last edited by junioragd, Sep 15, 2014, 5:17 PM

Z K Y

The post below has been deleted. Click to close.

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

thunderz28

32 posts

thunderz28

#7 h Jun 11, 2017, 7:51 PM • 1 Y

Y by Adventure10

Answer: If $(m,n)=1$ , the admissible set containing both $m$ and $n$ is the set of all integers.

Let's think $(m,n)=g>1$ . Then every element of $A$ is divisible by $g$ . Because $g$ is underneath every integer there. So, the set $\{...,-3g,-2g,-g,0,g,2g,3g,....\}$ will work.

Now we'll prove that if $(m,n)=1$ the admissible set containing both $m$ and $n$ is the set of all integers.

Lemma 1: If we have $j \in A$ , then every multiple of $j^2$ will be in $A$ .
Proof: By taking $x=y=m$ we will have $m^2+km^2+m^2=2m^2+km^2=m^2(k+2)$ . Then by putting $k= \{-2,-1,0,1,2\}$ we will have every multiple of $j$ .

Now the main part. We've $(m,n)=1$ . So, $(m^2,n^2)=1$ . By bezout's identity there exists $a,b$ such that $am^2+bn^2=1$ .

Now by applying lemma 1 if we've $m,n$ in $A$ then we will also have $am^2$ and $bn^2$ in $A$ . So by taking $x=am^2, y=bn^2, k=2$ we have $(am^2)^2+2(am^2)(bn^2)+(bn^2)^2= (am^2+bn^2)^2=1$ So, we can always form $1$ by taking these values from a set whare $(m,n)=1$ . Then by taking $x=y=1$ and taking $k= \{...,-2,-1,0,1,2,...\}$ we will have every integer in $A$ .

$\mathbb Q. \exists .\mathbb D.$

This post has been edited 8 times. Last edited by thunderz28, Jun 11, 2017, 8:03 PM

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#8 h Mar 26, 2018, 3:16 AM • 2 Y

Y by Adventure10, Mango247

solution

Z K Y

The post below has been deleted. Click to close.

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

Vfire

1354 posts

Vfire

#9 h Apr 9, 2018, 12:25 PM • 2 Y

Y by Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

ayan.nmath

643 posts

ayan.nmath

#10 h May 24, 2018, 8:00 AM • 2 Y

Y by Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

niyu

830 posts

niyu

#11 h Jul 20, 2020, 5:16 PM

Y by

We claim the $(x, y)$ which satisfy the problem condition are precisely those for which $\gcd(x, y) = 1$ .

We first show that these pairs work.

Lemma: The elements $x, y, x^2 + y^2, x^2 + xy + y^2 \in A$ are pairwise relatively prime.

Proof: By assumption $\gcd(x, y) = 1$ . Also, $\gcd(x^2 + y^2, x) = \gcd(y^2, x) \leq \gcd(y, x) = 1$ , implying that $\gcd(x^2 + y^2, x) = 1$ . Similarly, $\gcd(x^2 + y^2, y) = 1$ . Additionally, $\gcd(x^2 + xy + y^2, x^2 + y^2) = \gcd(xy, x^2 + y^2) \leq \gcd(x, x^2 + y^2) \cdot \gcd(y, x^2 + y^2) = 1$ , so $\gcd(x^2 + xy + y^2, x^2 + y^2) = 1$ . Finally, $\gcd(x^2 + xy + y^2, x) = \gcd(y^2, x) \leq \gcd(y, x) = 1$ , so $\gcd(x^2 + xy + y^2, x) = 1$ . Similarly, $\gcd(x^2 + xy + y^2, y) = 1$ , proving the lemma. $\blacksquare$

Now, we have that all $a \equiv x^2 + y^2 \pmod{xy}$ are members of $A$ , and additionally that all $a \equiv (x^2 + xy + y^2)^2 + (x^2 + y^2)^2 \pmod{(x^2 + xy + y^2)(x^2 + y^2)}$ are members of $A$ . Since $\gcd(xy, (x^2 + xy + y^2)(x^2 + y^2)) = 1$ , by CRT there exists $N$ such that
$\begin{align*} N &\equiv x^2 + y^2 \pmod{xy} \\ N + 1 &\equiv (x^2 + xy + y^2)^2 + (x^2 + y^2)^2 \pmod{(x^2 + xy + y^2)(x^2 + y^2)}. \end{align*}$ For such an $N$ , both $N$ and $N + 1$ are members of $A$ . Now, $N^2 + (N + 1)^2 - 2N(N + 1) = 1 \in A$ . To conclude, $1^2 + 1^2 + 1 \cdot 1 \cdot k = k + 2 \in A$ for all $k \in \mathbb{Z}$ , implying that $A$ contains all integers. Thus, the pairs $(x, y)$ for which $\gcd(x, y) = 1$ satisfy the problem condition.

Finally, if $\gcd(x, y) = d > 1$ , the set $A$ of all multiples of $d$ is an admissible set which contains $x, y$ , but $A \neq \mathbb{Z}$ .

Thus, the only pairs $(x, y)$ which work are those described initially, so we are done. $\Box$

Z K Y

The post below has been deleted. Click to close.

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

EulersTurban

386 posts

EulersTurban

#12 h Nov 28, 2020, 11:38 PM • 2 Y

Y by Mango247, Mango247

The answer is all integers such that they are relatively prime.

First we set $k=2$ to get that $(x+y)^2 \in \mathcal{A}$ , then we set $k=-2$ to get that $(x-y)^2 \in \mathcal{A}$ , also we have that when $k=0$ that $x^2+y^2 \in \mathcal{A}$ .
Setting $x=y$ we get that $0 \in \mathcal{A}$ , this implies that $x^2 \in \mathcal{A}$ , this means that if $x^2 \in \mathcal{A}$ , then we have that $x \in \mathcal{A}$ .

This means that $x+y \in \mathcal{A}$ and $x-y \in \mathcal{A}$ , this implies that for every integer $k$ we have that $kx \in \mathcal{A}$ , thus we need to get that $x=1$ .

We use the following ultra well known lemma:
Lemma: Let $d=(x,y)$ , then there exist some integer numbers $k$ and $q$ such that $kx+qy=d$ .

By this lemma we easily get that $d=(x,y) \in \mathcal{A}$

Now if $d=1$ we win and $\mathcal{A}=\mathbb{Z}$

If $d \neq 1$ , then we have that we only generate pairs of numbers such that they are divisible by $d$ , thus $\mathcal{A} \neq \mathbb{Z}$

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

#13 h Jan 8, 2021, 12:04 AM

Y by

Solved with nukelauncher.

Clearly, $\gcd(m,n)=1$ since $\gcd(m,n)$ divides every element of $A$ . We claim all such pairs work.

Let $P(x,y,k)$ denote the assertion $x^2+kxy+y^2\in A$ . By plugging in $(x,y)=(m,m)$ , we get that $am^2 \in A$ for any $a$ , and similarly $bn^2 \in A$ for any $b$ . Since $\gcd(m,n)=1$ implies $\gcd(m^2,n^2)=1$ , we can find $a,b\in\mathbb Z$ such that $am^2-bn^2=1$ . Plugging in $(x,y,k)=(am^2,bn^2,-2)$ gives
$1=(am^2-bn^2)^2 \in A.$ Finally, $(x,y,k)=(1,1,k)$ gives $2+k \in A$ for any $k$ , i.e. $A=\mathbb{Z}$ .

This post has been edited 1 time. Last edited by pad, Jan 8, 2021, 12:04 AM

Z K Y

The post below has been deleted. Click to close.

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

Nymoldin

57 posts

Nymoldin

#14 h Mar 8, 2021, 9:13 AM

Y by

The same idea was used in USAMO 2004/2

Z K Y

The post below has been deleted. Click to close.

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

AwesomeYRY

579 posts

AwesomeYRY

#15 h Mar 22, 2021, 2:52 AM

Y by

I claim the answer is that this is true for all pairs such that $\gcd(m,n)=1$ .

Clearly if $\gcd(m,n)=g>1$ , then any new element satisfies
$g^2 \mid x^2+kxy+y^2$ Thus, we cannot generate the necessary infinitely many elements not divisible by $g^2$ .

We now construct a solution for all $\gcd(m,n)=1$ . Note that by plugging in $(m,m)$ , we get all multiples of $m^2$ , similarly we can get all multiples of $n^2$ . Since $\gcd(m,n)=1\Longrightarrow \gcd(m^2,n^2)=1$ , we have that by Bezout's we can find $x,y$ such that $xm^2-yn^2=1$ .

Thus, we can plug in $(xm^2,yn^2)$ with $k=2$ which yields
$(xm^2-yn^2)^2 = 1$
Thus 1 is in the set, and by plugging in $x=y=1$ we get all integers.

This post has been edited 2 times. Last edited by AwesomeYRY, Mar 23, 2021, 10:38 PM

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1915 posts

cj13609517288

#34 h Jun 8, 2023, 1:38 PM

Y by

The answer is when $\boxed{\gcd(m,n)=1}$ . Obviously this is necessary as otherwise everything in $A$ has to be a multiple of $\gcd(m,n)$ .

Now we will prove that this is sufficient. By Bezout's, there exists integers $a$ and $b$ such that
$ax^2-by^2=1.$ Now let $k_1=(2y^2-2x^2+1)a$ and $k_2=(2y^2-2x^2+1)b$ . Then
$m=x^2+k_1x^2+x^2=((2y^2-2x^2+1)a+2)x^2\in A$ and
$n=y^2+k_2y^2+y^2=((2y^2-2x^2+1)b+2)y^2\in A.$ But $m=n+1$ , so
$m^2+(-2)(m)(n)+n^2=(m-n)^2=1\in A.$ Now for any positive integer $z$
$(1)^2+(z-2)(1)(1)+(1)^2=z\in A\,\blacksquare$

This post has been edited 1 time. Last edited by cj13609517288, Jun 8, 2023, 1:38 PM

Z K Y

The post below has been deleted. Click to close.

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

Inconsistent

1455 posts

Inconsistent

#35 h Jun 9, 2023, 9:56 AM • 1 Y

Y by ihatemath123

All coprime pairs. If not, just take a prime ideal containing both. If $m, n$ are coprime, then all multiples of $m^2, n^2$ lie in the set from $(m, m)$ and $(n, n)$ . Thus by Bezout's theorem, there exists $s, t \in A$ such that $s - t = 1$ . However by $k = -2$ we must have $1 = (s-t)^2 \in A$ , then from $(1, 1)$ we have all integers must lie in $A$ .

Z K Y

The post below has been deleted. Click to close.

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

S.Das93

709 posts

S.Das93

#36 h Jun 9, 2023, 12:33 PM

Y by

Storage

Z K Y

The post below has been deleted. Click to close.

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

pikapika007

298 posts

pikapika007

#37 h Jun 21, 2023, 5:36 PM

Y by

All integers $(m, n)$ such that $\gcd(m,n) = 1$ work. Clearly $m,n$ not satisfying this condition do not work; then all numbers in $A$ must be a multiple of $\gcd(m,n)$ , contradiction.

Otherwise, $(x, y) = (m,m)$ and $(x,y) = (n,n)$ show that all multiples of $m^2, n^2$ are in $A$ ; by Bezout's, there exists integers $a,b$ so that
$am^2 - bn^2 = 1;$ taking $(x,y) = (am^2, bn^2)$ and $k = -2$ shows that $1 \in A$ ; now it is trivial to check that $(1, 1)$ gives that all integers are in $A$ .

This post has been edited 1 time. Last edited by pikapika007, Jun 21, 2023, 5:38 PM

Z K Y

The post below has been deleted. Click to close.

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

minusonetwelth

225 posts

minusonetwelth

#38 h Nov 14, 2023, 4:47 PM

Y by

Nice problem:

First note that if $(m,n)=(1,1)$ or $(m,n)=(-1,-1)$ results in $A=\mathbb{Z}$ , as $1^2+k\cdot1\cdot1+1^2=2+k$ covers all the integers. Now, let $\gcd(m,n)=s>1$ so that $m=xs$ and $s=ys$ . Then each element of $A$ is divisble by $s^2$ , so in particular, $1\notin A$ , and thus $A\neq\mathbb{Z}$ .

Claim: If $m,n\in A$ and $\gcd(m,n)=1$ , then $A=\mathbb{Z}$ .

Proof: By taking $m=m$ , $m^2+km^2+m^2=(k+2)m^2$ all multiples of $m^2$ are in $A$ . Similarly, all multiples of $n^2$ are in $A$ . By Bezout's theorem, there exist integers $x,y$ such that $xm^2-yn^2=1$ . So there are two elements in $A$ which are consecutive. Let them be $r$ and $r+1$ . Then,
$r^2-2r(r+1)+(r+1)^2=r^2-2r^2-2r+r^2+2r+1=1\in A$ and thus, by our first observation, $A=\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.

lian_the_noob12

173 posts

lian_the_noob12

#39 h Feb 10, 2024, 12:56 AM

Y by

$\color{magenta}\boxed{\textbf{SOLUTION N1}}$

If $\gcd(m,n) > 1$ , Then $A =$ the multiples of $\gcd(m,n)$ works
So, Suppose $\gcd(m,n) = 1$ . Let $P(x,y,k)$ be the statement. Then,
$\bullet P(m,m,k)$ and $P(n,n,k)$ $\implies$ all multiples of $m^2$ and $n^2$ are in $A$ .
$\bullet P(am^2,bn^2,2)$ gives $a^2 \cdot m^4 + 2ab \cdot m^2n^2 + b^2 n^4 = (am^2+bn^2)^2 \in A$ Hence, $1 \in A$ .
$\bullet P(1,1,k) \implies A = {\mathbb Z} \blacksquare$ .

This post has been edited 2 times. Last edited by lian_the_noob12, Feb 10, 2024, 12:58 AM

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

139 posts

Ywgh1

#40 h Feb 14, 2024, 8:02 AM

Y by

We claim the answer is for all pairs such that $gcd(m,n)=1$
Assume that $gcd(m.n) > 1$ , and assume that $gcd(m,n)=d$ then we can see that the set $A$ will be equal to the multiples of $d$ , namely
$A= \{...-3d,-2d,-d,0,d,2d,3d,....\}$
Now we show that $gcd(m.n)=1$ works.

Claim 1: If $j$ is in $A$ then all multiples of $j^2$ are as well in $A$ :

Plugging in $(m,m)$ in the equation
$x^2+kxy+y^2 (1)$ We will have all multiples of $m^2$ , similarly for $n^2$ .

Claim 2: If $gcd(m,n)=1$ then $1 \in A$ :

We know that $gcd(m^2,n^2)=1$ .
Here we apply Bezout lemma, so there exists $a,b$ such that
$am^2+bn^2=1$ , so plugging $x=am^2$ , $y=bn^2$ and $k=-2$ we have :
$(am^2)^2+2(am^2)(bn^2)+(bn^2)^2= (am^2+bn^2)^2=1$ Meaning that $1 \in A$ as desired.

Now by Claim 1 we have that all multiples of $1$ are in $A$ , so $A$
is the set of all integers.

This post has been edited 1 time. Last edited by Ywgh1, Feb 14, 2024, 8:06 AM

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1324 posts

dolphinday

#41 h May 16, 2024, 11:49 PM

Y by

Clearly if $m$ and $n$ are not relatively prime then all elements in $A$ will be divisible by $\gcd(m, n)$ which is undesirable(since we won't be able to get numbers that are not divisible by $\gcd(m, n)$ .
So then $\gcd(m, n) = 1$ . We can plug in $(m, m)$ and $(n, n)$ and vary $k$ to get multiples of $m^2$ and $n^2$ respectively. Since Bezout's lemma states there exists $a$ and $b$ so that $ax + by = \gcd(x, y)$ we can plug in $(am^2, bn^2)$ with $k = 2$ to get $(am^2 + bn^2) \in A$ with $a$ and $b$ chosen so that $am^2 + bn^2 = 1$ . Now that $1 \in A$ we can plug in $(1, 1)$ and vary $k$ to get all integers, done.

Z K Y

The post below has been deleted. Click to close.

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

KevinYang2.71

427 posts

KevinYang2.71

#42 h May 18, 2024, 7:54 PM • 2 Y

Y by blueberryfaygo_55, LostDreams

We claim $\boxed{\gcd(m,n)=1}$ is necessary and sufficent. It is necessary since the admissible set generated by $m$ and $n$ is a subset of $(m,n)$ (the ideal).

Suppose $\gcd(m,n)=1$ . Let $A$ be the admissible set generated by $m$ and $n$ . Then $xm^2,yn^2\in A$ for all integers $x$ and $y$ . By Bezout, there exists integers $x$ and $y$ such that $xm^2+yn^2=1$ . Then $(xm^2)^2+2(xm^2)(yn^2)+(yn^2)^2=1$ so $1\in A$ . The conclusion follows. $\square$

This post has been edited 1 time. Last edited by KevinYang2.71, May 18, 2024, 7:55 PM

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1267 posts

ezpotd

#43 h Sep 6, 2024, 2:06 AM

Y by

I claim the answer is only the pairs $m,n$ with greatest common divisor $1$ .

To prove nothing else works, note that the set of all numbers divisible by the greatest common divisor of $m,n$ is a working solution.

To prove all such pairs work, consider all numbers of the form $2m^2 + km^2, 2n^2 + kn^2$ are in the set. We can then find two of these numbers with difference $1$ by Bezout's theorem, then set $k = - 2$ and we get that $1$ is part of the set. We are clearly done from there, as all numbers of the form $1^2 + k \cdot 1 \cdot 1 + 1^2 = 2 + k$ are part of the set, which is just all integers.

Z K Y

The post below has been deleted. Click to close.

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

EpicBird08

1751 posts

EpicBird08

#44 h Oct 15, 2024, 10:48 PM

Y by

We claim that the answer is all $(m,n)$ such that $\boxed{\gcd(m,n) = 1}.$

First, if $\gcd(m,n) = d > 1,$ then obviously every element of $A$ is divisible by $d,$ so we can make $A$ not contain every positive integer.
On the other hand, if $\gcd(m,n) = 1,$ by using $m,m$ in the given condition, we see that every multiple of $m^2$ is in $A,$ and similarly every multiple of $n^2$ is also in $A.$ Since $\gcd(m,n) = 1,$ we also have $\gcd(m^2,n^2) = 1,$ so by Bezout we may find integers $k,l$ such that $km^2 + ln^2 = 1.$ Since $km^2, ln^2 \in A,$ we see that $(km^2)^2 + 2(km^2)(ln^2) + (ln^2)^2 = (km^2+ln^2)^2 = 1 \in A.$ Then taking $1,1$ in the given condition, we see that every integer is in $A.$

Thus all $m,n$ such that $\gcd(m,n) = 1$ work, and these are the only solutions, as claimed.

This post has been edited 1 time. Last edited by EpicBird08, Oct 15, 2024, 11:49 PM

Z K Y

The post below has been deleted. Click to close.

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

Maximilian113

575 posts

Maximilian113

#45 h Jan 11, 2025, 4:32 AM

Y by

We claim that the only solutions are coprime pairs. Clearly if they are not coprime, every integer generated will be divisible by their GCD.

Now, we show that coprime pairs $(m, n)$ work. Letting $x=y=m$ yields all multiples of $m^2$ are in $A,$ and similarly all multiples of $n^2$ are in $A.$ By Bezout's Theorem, it follows that there are $a, b$ such that $am^2-bn^2=1.$ Thus letting $x=am^2, y=bn^2, k=-2$ yields $(am^2-bn^2)^2 \in A \implies 1 \in A.$ Now letting $x=y=1$ gives $k+2 \in A$ for all integers $k$ and we are done. QED

Z K Y

The post below has been deleted. Click to close.

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

Sedro

5846 posts

Sedro

#46 h Mar 2, 2025, 7:16 AM

Y by

The answer is all relatively prime $m$ and $n$ . If there is some prime $p\mid m,n$ , then the set of all multiples of $p$ contains $m$ and $n$ , is admissible, but does not contain all integers. We now show that if $\gcd(m,n)=1$ , the only admissible set containing both $m$ and $n$ is the set of all integers.

Claim: If $1\in A$ and $A$ is admissible, then $A$ is the set of all integers.

Proof: Since $A$ is admissible, $1^2+k+1^2 = k+2 \in A$ for every integer $k$ , as desired. $\blacksquare$

Claim: If an admissible set $A$ contains two consecutive integers, then $A$ is the set of all integers.

Proof: Suppose the two consecutive integers are $r$ and $r+1$ . Since $A$ is admissible, $(r+1)^2 + kr(r+1) + r^2\in A$ for any integer $k$ . Setting $k=-2$ implies that $1\in A$ , which proves the claim. $\blacksquare$

Claim: If $s\in A$ , then every integer multiple of $s^2$ is in $A$ .

Proof: Since $A$ is admissible, $s^2+ks^2+s^2 = (k+2)s^2\in A$ for every integer $k$ , as desired. $\blacksquare$

Suppose that $\gcd(m,n)=1$ and $A$ is an admissible set containing $m$ and $n$ . Then, every every multiple of $m^2$ and $n^2$ is in $A$ . Since $m$ and $n$ are relatively prime, by Bezout, there exist a multiple of $m^2$ (call it $m'$ ) and a multiple of $n^2$ (call it $n'$ ) such that $|m'-n'| = 1$ . Since $A$ contains two consecutive integers, it must contain all integers; this completes the proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

g0USinsane777

48 posts

g0USinsane777

#47 h Apr 19, 2025, 3:50 PM

Y by

Ans: All pairs $(m,n)$ of integers with $\gcd(m,n)=1$ .
Proof that other pairs do not work. First, say that $\gcd(m,n)=d>1$ , then notice that the set containing all the integer multiples of $d$ is an admissible set since if any two integer multiples of $d$ , say $s$ and $t$ are in an admissible set then so is $s^2 + kst + t^2 = d^2l$ , since it is multiple of $d$ .

Now, we prove that if two co-prime integers, $m$ and $n$ are in an admissible set $A$ , then the only possible set is the set of integers.
Lemma: $1 \in A$
Notice, that $am^2$ for $a \in \mathbb{Z}$ is also in $A$ , this is because $(m,m) \in A$ which implies that $(k+2)m^2 \in A$ .
Similarly, $bn^2$ for $b \in \mathbb{Z}$ also belongs to $A$ .
Now, by bezout's theorem we can find integers $a$ and $b$ such that $am^2+bn^2 = 1$ since $\gcd(m^2,n^2)=1$
Also, for some $x,y$ belonging to $A$ , $(x+y)^2 \in A$ by putting $k=2$ in the condition.
So, since $am^2, bn^2 \in A$ , then $(am^2+bn^2)^2=1^2=1 \in A$ proving the lemma.

Now, the lemma is enough to finish since we have gotten that $1 \in A$ , then putting $x=y=1$ in the condition we get that any $k \in \mathbb{Z}$ belongs to $A$ , proving that the only set containing $m,n$ with $\gcd(m,n)=1$ is the set of integers.

This post has been edited 1 time. Last edited by g0USinsane777, Apr 19, 2025, 3:54 PM

Z K Y

The post below has been deleted. Click to close.

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

sansgankrsngupta

143 posts

sansgankrsngupta

#48 h Apr 27, 2025, 6:59 AM

Y by

OG! We claim that the answer is only and all pairs $(m,n)$ such that $gcd(m,n)=1$
Proof that other pairs don't work: Let $gcd(m,n)= d>1$ . Then $A=\{dk|k \in \mathbb{Z}\}$ works well , while we note that $A \neq \mathbb{Z}$
Proof that $gcd(m,n)=1$ works:
Claim: There is an integer $t$ such that $t \in A, t \equiv 1 \pmod{n^2}$
Proof: set $x=y=m$ and you get that all integers of the form $m^2(k+2)$ are there; select $k$ such that $k \equiv m^{-2} -2 \pmod{n^2}$ to get $t$ .
Let $t=n^2l+1$ , set $x=y=n , k=l-2$ , then you get that $n^2l \in A$ . Now, set $k=-2, x=t, y= n^2l$ to get that $1 \in A$ taking $x=y=1$ gives that any integer is in $A$ . Hence $A=Z$ is the only possible admissible set(obviously $Z$ is an admissible set for any pair $(m,n)$ ).
Hence, the pairs which satisfy are the ones which we claimed at the start; as desired.

Z K Y