BMO 2021 problem 3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

BMO 2021 problem 3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Balkan MO 2021 P3

The post below has been deleted. Click to close.

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

1390 posts

#1 h Sep 8, 2021, 5:01 PM • 2 Y

Y by jhu08, PineApplePen

Let $a, b$ and $c$ be positive integers satisfying the equation $(a, b) + [a, b]=2021^c$ . If $|a-b|$ is a prime number, prove that the number $(a+b)^2+4$ is composite.

Proposed by Serbia

This post has been edited 1 time. Last edited by VicKmath7, Jan 1, 2023, 2:17 PM

Z K Y

The post below has been deleted. Click to close.

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

laikhanhhoang_3011

637 posts

laikhanhhoang_3011

#2 h Sep 8, 2021, 5:26 PM • 1 Y

Y by jhu08

look like it is not difficult but small cases confused us

Z K Y

The post below has been deleted. Click to close.

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

InvertedDiabloNemesisXD

6 posts

InvertedDiabloNemesisXD

#3 h Sep 8, 2021, 5:27 PM • 3 Y

Y by jhu08, Danie1, Arabian_Math

Case Bash solution
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

577 posts

#4 h Sep 8, 2021, 5:33 PM • 2 Y

Y by jhu08, Iora

WLOG $a-b=p$ where $p$ is a prime number.
i) $p|b$
Let $b=pd$ . Then, $(a,b)=(pd+p,pd)=p(d+1,d)=p$ and $[a,b]=[pd+p,pd]=p[d+1,d]=pd(d+1)$ . Hence, $p+pd(d+1)=2021^c\Rightarrow p|2021^c\Rightarrow p|2021\Rightarrow p=43,47$ .
i.a) $p=43$
$2021^c=p(d^2+d+1)=43(d^2+d+1)\Rightarrow d^2+d+(1-43^{c-1}\cdot 47^c)=0$ . Hence, the number $\triangle_d 1-4(1-43^{c-1}\cdot 47^c)=4\cdot 43^{c-1}\cdot 47^c-3$ must a perfect square. But, $4\cdot 43^{c-1}\cdot 47^c-3\equiv -3\pmod{47}$ and $47\equiv 2\pmod{3}$ . So, this number cannot be a perfect square. Contradiction.
i.b) $p=47$
$2021^c=p(d^2+d+1)=47(d^2+d+1)\Rightarrow d^2+d+(1-43^c\cdot 47^{c-1})=0$ . Hence, the number $\triangle_d 1-4(1-43^c\cdot 47{c-1}c)=4\cdot 43^c\cdot 47^{c-1}-3$ must a perfect square. If $c\ge 2$ , again $4\cdot 43^c\cdot 47^{c-1}-3\equiv -3\pmod{47}$ . Contradiction. Thus, $c=1$ . Then, $\triangle_d=4\cdot 43^c\cdot 47^{c-1}-3=4\cdot 43-3=169=13^2$ . Hence, $d=\dfrac{-1\pm\sqrt{\triangle_d}}{2}=\dfrac{-1\pm 13}{2}=\{-7,6\}$ . Since $d>0$ , we find that $d=6$ . Then, $b=pd=47\cdot 6=282$ and $a=b+p=282+47=329\Rightarrow (a+b)^2+4=611^2+4\equiv 0\pmod{5}$ . Clearly, $611^2+4>5$ , so it is composite.
ii) $p\not |b$
Then, $(a,b)=(b+p,b)=(b,p)=1$ and $[a,b]=[b+p,b]=(b+p)b$ . Hence, $1+(b+p)b=2021^c\Rightarrow b^2+pb+(1-2021^c)=0$ . Hence, the number $\triangle_d=p^2-4(1-2021^c)=p^2+4\cdot 2021^c-4$ must be a perfect square. Let $p^2+4\cdot 2021^c-4=t^2$ where $t\in \mathbb{Z^+}$ . Then, $b=\dfrac{-p\pm \sqrt{t^2}}{2}$ and since $b>0$ , we find that $b=\dfrac{t-p}{2}$ . Then, $(a+b)^2+4=\left(\dfrac{t-p}{2}+\dfrac{t+p}{2}\right)^2+4=t^2+4$ . Suppose that $t^2+4=q$ where $q$ is a prime number. Hence, $p^2+4\cdot 2021^c=t^2+4=q$ .
ii.a) $c$ is even.
Let $c=2c_1$ . Then, $p^2+(2\cdot 2021^{c_1})^2=q=t^2+2^2$ . But, each prime number can be written in $1$ or $0$ different way as the sum of $2$ perfect squares. Thus, $\{p,2\cdot 2021^{c_1}\}=\{t,2\}$ . Clearly, $2\cdot 2021^{c_1}>2$ so $p=2$ . Then $q=p^2+4\cdot 2021^c\equiv 0\mod{2}\Rightarrow q=2$ but $p^2+4\cdot 2021^c>$ . Contradiction.
ii.b) $c$ is odd.
If $p\neq 3$ , then $t^2+4=p^2+4\cdot 2021^c\equiv (-1)^c\equiv -1\pmod{3}\Rightarrow t^2\equiv 2\pmod{3}$ . Contradiction. So $p=3$ . Then, $t^2+4=9+4\cdot 2021^c\equiv 9\pmod{47}\Rightarrow t^2\equiv 5\pmod{47}$ . Contradiction.

This post has been edited 1 time. Last edited by BarisKoyuncu, Sep 8, 2021, 5:34 PM
Reason: .

Z K Y

The post below has been deleted. Click to close.

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

1424 posts

#6 h Sep 8, 2021, 5:46 PM • 1 Y

Y by jhu08

BarisKoyuncu wrote:

WLOG $a-b=p$ where $p$ is a prime number.
i) $p|b$
Let $b=pd$ . Then, $(a,b)=(pd+p,pd)=p(d+1,d)=p$ and $[a,b]=[pd+p,pd]=p[d+1,d]=pd(d+1)$ . Hence, $p+pd(d+1)=2021^c\Rightarrow p|2021^c\Rightarrow p|2021\Rightarrow p=43,47$ .
i.a) $p=43$
$2021^c=p(d^2+d+1)=43(d^2+d+1)\Rightarrow d^2+d+(1-43^{c-1}\cdot 47^c)=0$ . Hence, the number $\triangle_d 1-4(1-43^{c-1}\cdot 47^c)=4\cdot 43^{c-1}\cdot 47^c-3$ must a perfect square. But, $4\cdot 43^{c-1}\cdot 47^c-3\equiv -3\pmod{47}$ and $47\equiv 2\pmod{3}$ . So, this number cannot be a perfect square. Contradiction.
i.b) $p=47$
$2021^c=p(d^2+d+1)=47(d^2+d+1)\Rightarrow d^2+d+(1-43^c\cdot 47^{c-1})=0$ . Hence, the number $\triangle_d 1-4(1-43^c\cdot 47{c-1}c)=4\cdot 43^c\cdot 47^{c-1}-3$ must a perfect square. If $c\ge 2$ , again $4\cdot 43^c\cdot 47^{c-1}-3\equiv -3\pmod{47}$ . Contradiction. Thus, $c=1$ . Then, $\triangle_d=4\cdot 43^c\cdot 47^{c-1}-3=4\cdot 43-3=169=13^2$ . Hence, $d=\dfrac{-1\pm\sqrt{\triangle_d}}{2}=\dfrac{-1\pm 13}{2}=\{-7,6\}$ . Since $d>0$ , we find that $d=6$ . Then, $b=pd=47\cdot 6=282$ and $a=b+p=282+47=329\Rightarrow (a+b)^2+4=611^2+4\equiv 0\pmod{5}$ . Clearly, $611^2+4>5$ , so it is composite.
ii) $p\not |b$
Then, $(a,b)=(b+p,b)=(b,p)=1$ and $[a,b]=[b+p,b]=(b+p)b$ . Hence, $1+(b+p)b=2021^c\Rightarrow b^2+pb+(1-2021^c)=0$ . Hence, the number $\triangle_d=p^2-4(1-2021^c)=p^2+4\cdot 2021^c-4$ must be a perfect square. Let $p^2+4\cdot 2021^c-4=t^2$ where $t\in \mathbb{Z^+}$ . Then, $b=\dfrac{-p\pm \sqrt{t^2}}{2}$ and since $b>0$ , we find that $b=\dfrac{t-p}{2}$ . Then, $(a+b)^2+4=\left(\dfrac{t-p}{2}+\dfrac{t+p}{2}\right)^2+4=t^2+4$ . Suppose that $t^2+4=q$ where $q$ is a prime number. Hence, $p^2+4\cdot 2021^c=t^2+4=q$ .
ii.a) $c$ is even.
Let $c=2c_1$ . Then, $p^2+(2\cdot 2021^{c_1})^2=q=t^2+2^2$ . But, each prime number can be written in $1$ or $0$ different way as the sum of $2$ perfect squares. Thus, $\{p,2\cdot 2021^{c_1}\}=\{t,2\}$ . Clearly, $2\cdot 2021^{c_1}>2$ so $p=2$ . Then $q=p^2+4\cdot 2021^c\equiv 0\mod{2}\Rightarrow q=2$ but $p^2+4\cdot 2021^c>$ . Contradiction.
ii.b) $c$ is odd.
If $p\neq 3$ , then $t^2+4=p^2+4\cdot 2021^c\equiv (-1)^c\equiv -1\pmod{3}\Rightarrow t^2\equiv 2\pmod{3}$ . Contradiction. So $p=3$ . Then, $t^2+4=9+4\cdot 2021^c\equiv 9\pmod{47}\Rightarrow t^2\equiv 5\pmod{47}$ . Contradiction.

You can excise a fair amount of work here. Let $d={\rm gcd}(a,b)$ with $a=da_1$ and $b=db_1$ , $(a_1,b_1)=1$ . Assume w.l.o.g. $a_1>b_1$ (clearly $a\ne b$ ). We then have $d(a_1-b_1)=p$ for a prime $p$ , thus $d\in\{1,p\}$ . Now, if $d=p$ then we obtain that
$d\left(b_1^2+b_1+1\right)=43^c\cdot 47^c.$ If $47\mid b_1^2+b_1+1$ , then $47\mid (2b_1+1)^2+3$ , but $(-3/47)=-1$ as $47\equiv -1\pmod{6}$ . Hence, in this case, $47^c\mid d = p$ , thus $c=1$ and $d=47$ is the only possibility. With this we find $b_1^2+b_1+1=43$ , for which $(a_1,b_1)=(7,6)$ is obtained; and for this solution, $(a+b)^2+4>5$ is divisible by $5$ , hence is the conclusion.

This brings us to the case $(a,b)=1$ , $a-b=p$ , which is handled exactly as demonstrated by Baris. (Let me also add that one way to prove the also contradiction, $t^2\equiv 5\pmod{47}$ , in the very last step is to use the quadratic reciprocity: $(5/47)(47/5)=1$ whereas $(57/5)=(2/5)=-1$ .)

This post has been edited 1 time. Last edited by grupyorum, Sep 8, 2021, 5:48 PM

Z K Y

The post below has been deleted. Click to close.

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

351 posts

#7 h Sep 8, 2021, 5:53 PM • 1 Y

Y by jhu08

Proposed by Serbia

Z K Y

The post below has been deleted. Click to close.

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

1390 posts

#8 h Sep 8, 2021, 8:37 PM • 1 Y

Y by mijail

Woah this was very hard and nice NT, involving QRs. This is similar to the above soln.
Case 1. $gcd(a,b)$ is not $1$ . Then $a=p(x+1)$ and $b=px$ . Thus $p(x^2+x+1)=2021^c$ . Hence $p=43$ or $p=47$ .
Case 1.1 $p=47$ . The number we want to be composite is $A=4.47^{c+1}.43^c-3.47^2+4$ . Note that if $c$ is even, then $A$ is divisible by $3$ , done. If $c$ is odd, then $A$ is $(-1)2^{c+1}.(-2)^c+2=2(2^{2c}+1) (mod 5)$ which is divisible by $5$ for odd $c$ .
Case 1.2 $p=43$ . We prove that this is actually impossible. Note that $(2x+1)^2=4.47^c.43^{c-1}+3$ , so $-3$ is a QR modulo $47$ , but that's impossible due to quadratic reciprocity.
Case 2. $gcd(a,b)=1$ . Thus $1+ab=2021^c$ and $a-b=p$ and we want $A=p^2+4.2021^c$ to be composite.
Case 2.1 $p>3$ . Then $c$ can't be odd, otherwise $A$ is divisible by $3$ . So suppose $c$ is even. We have that $b^2+bp+1-2021^c=0$ and it's discriminant is $p^2+4.2021^c-4=d^2$ . Thus the prime $A$ is representable as sum of two squares in two ways. But that's impossible (view this as a lemma: if $p=a^2+b^2=c^2+d^2$ , then $p^2=(ac-bd)^2+(ad+bc)^2=(ad-bc)^2+(ac+bd)^2$ but note that $a^2c^2=b^2d^2 (mod p)$ , and now we easily see contradiction).
Case 2.2 $p=3$ ( $2$ is impossible, obviously). We have similarly that $b^2+3b+1-2021^c=0$ so it's discriminant is $4.2021^c+5=d^2$ , but now finish again with quadratic reciprocity modulo $47$ .
So we're done.

This post has been edited 3 times. Last edited by VicKmath7, Sep 9, 2021, 6:57 AM

Z K Y

The post below has been deleted. Click to close.

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

406 posts

#9 h Sep 8, 2021, 8:51 PM

Y by

VicKmath7 wrote:

Let $a, b$ and $c$ be positive integers satisfying the equation $(a, b) + [a, b]=2021^c$ . If $|a-b|$ is a prime number, prove that the number $(a+b)^2+4$ is composite.

Let $d=(a,b)$ and $a=dx$ , $b=dy$ and suppose that $d$ different from $1$ then:
As $d|x-y|=prime$ we have $x=y+1$ and $d=prime$ .
Now at the first equation we have:
$d(y^2+y+1)=2021^c$
If $c>=2$ then $47|y^2+y+1$ by the well known lemma:Let $q=prime=2(mod3)$ then if $q|c^2+cd+d^2$ we have $q|c$ and $q|d$ .So $47|1$ contradiction.
If $c=1$ we have $d=47$ and $y=6$ which gives $47^2(6+7)^2+4=0(mod5)$

So $d=1$ and we have: $ab+1=2021^c$ (1)and $|a-b|=p$ .(2)
We consider two cases:

If $c=1(mod2)$ then (1) $mod3$ gives $a=b(mod3)$ using condition (2) we have $a=b+3$ so equation (1) became:
$b^2+3b+1=2021^c$ or $(2b+3)^2-5=4*2021^c$
But $(5/43)=(43/5)=(3/5)=-1$ so no solution.

If $c=0(mod2)$ set $c=2d$ then we have:
$ab+1=2021^{2d}$ or $4ab+4=2021^{2d}*4$
or $(a+b)^2-(a-b)^2+4=2021^{2d}*4$
or $(a+b)^2+4=2021^{2d}*4+p^2$ .

Suppose that $(a+b)^2+4=prime$ then it is well known that every prime in the form $4k+1$ can be written as a sum of two square in a unique way.
This mean that $p=2$ but it is obvious that $p=odd$ so contradiction.

This post has been edited 1 time. Last edited by P2nisic, Sep 8, 2021, 8:53 PM

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#10 h Sep 8, 2021, 9:05 PM

Y by

Let $p=|a-b|$ .

Case 1: $p \vert a,b$ We have:
$2021^c=(a,b)+[a,b]=p+\frac{ab}{p} \Rightarrow ab=p \left(2021^{c}-p\right)$ $\Longrightarrow (a+b)^2=(a-b)^2+4ab=p^2+4p\left(2021^{c}-p\right)=p \left(4 \times 2021^{c}-3p\right)$ As $p \vert a+b$ we have $p \vert 4 \times 2021^{c}$ and hence $p \in \{2,43,47\}$ . In the case $p=2$ , the quantity in question is even and $>2$ so composite. For $p=47$ observe:
$(a+b)^2+4 \equiv 2 \left(4-1\right)+4 \equiv 0 \pmod{5}$ and as $(a+b)^2+4>5$ it follows it is composite. Finally, for $p=43$ observe that $2021^{c} \in \{7,11\} \pmod{19}$ thus:
$(a+b)^2=43 \left(4 \times 2021^{c}-3 \times 43\right) \in \{8,12\} \pmod{19}$ and by a direct check neither of these are quadratic residues modulo $19$ thus this case cannot occur.

Case 2: $p \nmid a,b$ We have:
$2021^c=(a,b)+[a,b]=1+ab \Rightarrow (a+b)^2+4=(a-b)^2+4\left(1+ab\right)=p^2+4 \times 2021^{c}$ Firstly observe if $p=2$ then the quantity is even and $>2$ so composite. Now consider $p>2$ .

Case 2.1: $c$ is evenIn this case, as $p>2$ and $2 \times 2021^{c/2}>2$ , it follows $(a+b)^2+2^2$ is composite else we would have a prime written as a sum of two squares in two distinct ways.

Case 2.2: $p=3$ In this case observe:
$(a+b)^2=4 \times 2021^{c}+3^2-4 \equiv 5 \pmod{43}$ but by LQR as $\mathrm{LHS}$ is a perfect square we have:
$1=\left(\frac{5}{43}\right)=\left(\frac{43}{5}\right)=\left(\frac{3}{5}\right)=-1$ which is a contradiction.

Case 2.3: $p>3$ , $c$ odd Here we have:
$(a+b)^2+4 \equiv 4 \times (-1)^{c}+1 \equiv 0 \pmod{3}$ so $\mathrm{LHS}$ is divisible by $3$ and $>3$ therefore composite.

Z K Y

The post below has been deleted. Click to close.

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

square_root_of_3

78 posts

square_root_of_3

#11 h Sep 9, 2021, 11:35 AM • 1 Y

Y by MathsLion

I just wonder how the person who came up with this problem thought of this. I wonder at what point did they say 'let's put a-b to be a prime'. Did they first come up with the solution for the case where $(a,b)=1$ and $a-b$ is prime and then just added the particular case to make it longer? Or did they try solving the general $(a,b)+[a,b]=2021^c$ and then managed to just do the first two small cases?

Z K Y

The post below has been deleted. Click to close.

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

1746 posts

oVlad

#12 h Sep 9, 2021, 11:39 AM • 3 Y

Y by Pitagar, steppewolf, Mango247

Why so bashy? :noo:

:noo:

Anyways, my only goal while solving this was to shorten the solution as much as possible. I think I succeeded:

Let $b=a+p.$ We then have two cases:

Case One: Assume that $p$ divides $a.$ In other words, let $a=pk$ and $b=p(k+1).$ Our condition is then equivalent to $\Phi_3(k)=k^2+k+1=\frac{2021^c}{p}$ It's well known that for any prime number $q$ and positive integer $n,$ only prime numbers congruent to $0$ or 1 modulo $q$ can divide $\Phi_q(n).$

Thus, since $47\equiv 2\bmod 3$ then $47\nmid \Phi_3(k)$ so $47\nmid 2021^c/p.$ Therefore, $c=1$ and $p=47.$ After computing, this yields $k=6.$ Just bash $(a+b)^2+4.$

Case Two: Assume that $p$ does not divide $a.$ Then, our condition rewrites as $1+a(a+p)=2021^c\iff (2a+p)^2+4=4\cdot 2021^c+p^2.$
Assume that $p>3.$ Clearly, $3$ cannot divide $(2a+p)^2+4$ so $4\cdot 2021^c+p^2\equiv (-1)^c+1\not\equiv 0\bmod 3$ which implies that $c$ is even.

Hence, $(a+b)^2+4=(2a+p)^2+4$ can be written as the sum of $2$ squares in two ways, so it must be composite.

If $p=3$ then $(2a+p)^2\equiv 5\bmod{43}$ which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

694 posts

#13 h Sep 9, 2021, 12:28 PM • 2 Y

Y by steppewolf, mijail

Balkan MO 2021/3 wrote:

Let $a, b$ and $c$ be positive integers satisfying the equation $(a, b) + [a, b]=2021^c$ . If $|a-b|$ is a prime number, prove that the number $(a+b)^2+4$ is composite.

WLOG $a > b$ . Since $(a,b) \mid |a - b|$ , which is a prime number, then there are two possible cases.
Case 01. $(a,b) = p$ for some prime number $p$ .
Since $|a - b| = (a,b) = p$ . This implies $(a,b) = (px + p, px)$ for some $x \in \mathbb{N}$ . Therefore, we get
$p(x^2 + x + 1) = 2021^c$ First, we claim that $c = 1$ . Otherwise, $x^2 + x + 1 \equiv 0 \pmod{47}$ . However, $-3$ is not a QR modulo $47$ . Furthermore, this implies that $p = 47$ , which gives us $x^2 + x + 1 = 43$ , and this gives $x = 6$ as a solution. Just check that
$(a + b)^2 + 4 = p^2(2x + 1)^2 + 4 = 47^2 \cdot 13^2 + 4 \equiv 0 \pmod{5}$ and $a + b > 1$ , which implies $(a + b)^2 + 4$ is composite.

Case 02. $(a,b) = 1$ .
We then have
$(a + b)^2 + 4 = (a - b)^2 + 4(ab + 1) = (a - b)^2 + 4 \cdot 2021^c = p^2 + 4 \cdot 2021^c$ We first claim that $|a - b| \not= 3$ . Otherwise, then $b^2 + 3b + 1 = 2021^c \equiv 0 \pmod{47}$ , and one can check that $5$ is not a QR modulo $47$ . We claim that $c$ must be even. Indeed, if $c$ is odd, then $p^2 + 4 \cdot 2021^c \equiv 0 \pmod{3}$ .
Now, note that $(a + b)^2 + 2^2$ can be represented as $p^2 + (2 \cdot 2021^{c/2})^2$ as well, and we could quickly check that $p \not= 2$ , or otherwise it's composite because it's divisible by $4$ . We'll finish off by the following claim and conclude that $(a + b)^2 + 4$ must in fact be composite.

Claim. Every prime $1$ modulo $4$ has a unique representation as a sum of squares.
Proof. Suppose otherwise, that $p = a^2 + b^2 = c^2 + d^2$ for some $a,b,c,d \in \mathbb{Z}$ . Then,
$(a + bi)(a - bi) = (c + di)(c - di)$ Note that $\mathbb{Z}[i]$ is a UFD, which implies that $a + bi$ and $c + di$ can't both be primes. WLOG $a + bi$ is not a prime. Then, there exists a nontrivial factorization $a + bi = (x + yi)(z + wi)$ . Therefore,
$p = N(a + bi) = N(x + yi)N(z + wi) = (x^2 + y^2)(z^2 + w^2)$ contradicting the fact that $p$ is a prime.

Z K Y

The post below has been deleted. Click to close.

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

548 posts

#14 h Dec 4, 2021, 5:13 AM

Y by

By Thue lemma c odd
mod 3 c Evan

This post has been edited 1 time. Last edited by lazizbek42, Dec 4, 2021, 5:14 AM

Z K Y

The post below has been deleted. Click to close.

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

1481 posts

CT17

#15 h Apr 1, 2022, 2:38 AM

Y by

WLOG let $a < b$ .

Case 1: $(a,b) = 43$ . Let $a = 43a'$ and $b = 43(a'+1)$ . Then we have

$43 + 43a'(a'+1) = 2021^c\implies a'^2 + a' + 1 = \frac{2021^c}{43}$
a contradiction by mod $47$ .

Case 2: $(a,b) = 47$ . Let $a = 47a'$ and $b = 47(a' + 1)$ . Then we have

$47 + 47a'(a'+1) = 2021^c\implies a'^2 + a' + 1 = \frac{2021^c}{47}$
a contradiction by mod $47$ unless $c = 1$ . When $c = 1$ , we have $a' = 6$ so that

$(a+b)^2 + 4 = (13\cdot 47)^2 + 4\equiv 0\pmod{5}$
is composite, as desired.

Case 3: $(a,b) = 1$ . Let $p = b - a$ so that $a^2 + ap + 1 = 2021^c$ . Note that $p\neq 2$ , as otherwise $a$ and $b$ would both be even. We have $2$ subcases.

Subcase 3.1: $c$ is odd. Then $2021^c - 1\equiv 1\pmod{3}$ , so $a\equiv b\pmod{3}$ . Hence $p = 3$ , and $a^2 + 3a + 1\equiv 0\pmod{43}$ . In particular, the discriminant $5$ of this quadratic must be a QR mod $43$ , which we can verify is false with quadratic reciprocity.

Subcase 3.2: $c$ is even. Then we have

$(a+b)^2 + 4 = (2a + p)^2 + 4 = 4a^2 + 4ap + p^2 + 4 = 4\cdot 2021^c + p^2 = \left(2\cdot 2021^{\frac{c}{2}}\right)^2 + p^2$
By a well-known theorem, since $(a+b)^2 + 4$ is expressible as the sum of $2$ squares in $2$ different ways it is composite, as desired.

This post has been edited 1 time. Last edited by CT17, Apr 1, 2022, 2:39 AM

Z K Y

The post below has been deleted. Click to close.

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

139 posts

#16 h May 15, 2022, 8:13 AM • 1 Y

Y by Mango247

Can anybody tell me the NAME of this well known theorem with the sum of two squares??

Z K Y

The post below has been deleted. Click to close.

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

168 posts

#17 h Aug 22, 2022, 4:51 PM

Y by

I though it's gonna require a lot of case works but it didn't. Assume the statement doesn't hold:
If $gcd(a,b) \geq 2$ , then it would be $p \in \{43,47\}$ . let $a=px , b=p(x+1)$ so $p(x^2+x+1)=2021^c$ . But it's well-known that the polynomial $x^2+x+1$ has no prime divisor in the form $3k+2$ , but $47$ is such number. So $p=47$ and $c=1$ and we should've: $x^2+x+1=43$ which means $x=6$ and $a=282$ , $b=329$ so we can just compute the desired expression and it wouldn't be a prime number.

Now let $gcd(a,b)=1$ and $ab=2021^c -1$ , which means : $(a+b)^2 + 4 = p^2 + 4.2021^c$ where $p=|a-b|$ . if $c$ was odd , we're done since it's divisible by $3$ . if it was odd , it's well-known that every prime number in the form $4k+1$ can be UNIQUELY written as $x^2+y^2$ for positive integers $x,y$ . So $\{2.2021^{c/2},p\}=\{a+b,2\}$ but by the definition of $p$ , we have $p+1 \le a+b$ so $p=2 , a+b=2.2021^{c/2}$ . this is impossible since one of $a-b , a+b$ for $a=b (mod 2)$ should be divisible by $4$ which is a contradiction and 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.

168 posts

#18 h Aug 22, 2022, 5:01 PM • 1 Y

Y by sttsmet

sttsmet wrote:

Can anybody tell me the NAME of this well known theorem with the sum of two squares??

I don't know the name but in post #8 , VicKmath7 explained it. let $p=a^2+b^2=c^2+d^2$ so
$p^2=(ac-bd)^2+(ad+bc)^2=(ad-bc)^2+(ac+bd)^2 *$ and $a^2c^2=b^2d^2 (mod p)$ follows from the fact that if $p=a^2+b^2$ , $\frac{a}{b}$ (clearly $a,b$ are not zero modulo $p$ ) is the solution of $x^2 = -1 (modp)$ in Z_p so $\frac{a^2}{b^2}=\frac{d^2}{c^2}$ . Which contradicts $*$

This post has been edited 1 time. Last edited by alinazarboland, Aug 22, 2022, 5:02 PM

Z K Y

The post below has been deleted. Click to close.

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

2502 posts

ATGY

#19 h Feb 17, 2024, 7:17 PM

Y by

brah interesting problem

WLOG, say $a > b$ . Let $\gcd(a, b) = d$ , $a = dx, b = dy, (x, y) = 1, \text{lcm}(a, b) = dxy$ . Notice that $d \mid dxy \implies d \mid 2021^c$ . Say:
$p = (a - b) = dx - dy = d(x - y) \implies d = 1 \; \text{or} \; (x - y) = 1$ Case 1: $d = 1$ . This means that $(x, y) = (a, b)$ , so we have $1 + ab = 2021^c$ . If $c$ is even:
$(a + b)^2 + 4 = (a - b)^2 + 4ab + 4 = p^2 + 4(ab + 1) = p^2 + 4\cdot2021^c$ If $(a + b)^2 + 4$ was prime, it only can be uniquely represented as a sum of squares, which means $(a + b)^2 + 4 = p^2 + 4\cdot2021^c \implies p = 2$ , however, that means it's even, contradiction.
If $c$ was odd, we have $2021^c \equiv 2\mod3 \implies ab \equiv 1 \mod3 \implies a \equiv b\mod3$ . However, this means $a - b = 3$ since it's prime, so $a = b + 3 \implies (a + b)^2 = (2b + 3)^2 = 4b(b + 3) + 9 = 4\cdot2021^c + 5 = 4\cdot43^c\cdot47^c + 5$ . This means $5$ is a quadratic residue mod $47$ .
$\left(\frac{5}{47}\right) = \left(\frac{47}{5}\right) = \left(\frac{2}{5}\right) = -1$ Contradiction.

Case 2: If $d \neq 1$ , we have $x - y = 1 \implies x = y + 1$ . Furthermore, $d$ is prime and $d \mid 2021^c \implies d = 43, 47$ .
Subcase 2.1: $d = 43$ . We have:
$d + dxy = 43(xy + 1) = 2021^c \implies xy + 1 = 43^{c - 1}\cdot47^c$ We also have $(x + y)^2 = (2y + 1)^2 = 4y^2 + 4y + 1 = 4y(y + 1) + 1 = 4\cdot43^{c - 1}\cdot47^c - 3$ , which means $-3$ is a quadratic residue mod 47. We have:
$\left(\frac{-3}{47}\right) = \left(\frac{-1}{47}\right)\cdot\left(\frac{3}{47}\right) = \left(\frac{47}{3}\right) = \left(\frac{2}{3}\right) = -1$ Contradiction.
Subcase 2.2: $d = 47$ . We have:
$d + dxy = 47(xy + 1) = 2021^c \implies xy + 1 = 43^c\cdot47^{c - 1}$ Now, $(x + y)^2 = (2y + 1)^2 = 4y(y + 1) + 1 = 4\cdot43^c\cdot47^{c - 1} - 3$ . For $c > 1$ , we are done by the same step as earlier, however if $c = 1$ , we have $(2y + 1)^2 = 169 \implies y = 6, x = 7, a = 47\cdot7, b = 47\cdot6, 5 \mid (a + b)^2 + 4$ . Hence, 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.

1536 posts

#20 h Sep 7, 2024, 11:48 PM

Y by

First WLOG $a>b$ ( $a=b$ obviously cannot happen), then since $a-b$ is a prime and $d=(a,b) \mid a-b$ we have $d=a-b$ or $d=1$ . Suppose FTSOC that $(a+b)^2+4=p$ was a prime.
Case 1: $d=1$
In this case $ab+1=2021^c$ it means that $ab=2021^c-1$ , now if both $a,b$ were even then clearly $(a+b)^2+4$ cannot be a prime as it is divisbile by $4$ . Now back to $a-b=q$ where $q$ is a prime we also have that $b^2+qb+1-2021^c=0$ which means by quadratic formula that:
$b=\frac{-q+\sqrt{q^2+4 \cdot 2021^c-4}}{2} \implies q^2+4 \cdot (2021^c-1)=t^2$ Now clearly $a+b$ is odd so $q \ge 3$ , and also notice that $b=\frac{t-q}{2}$ implies that $a=\frac{t+q}{2}$ so we in fact get $a+b=t$ , so if we have that $p=t^2+4=q^2+4 \cdot 2021^c$ and $c$ is even then as $p \equiv 1 \pmod 4$ must have exactly one representation of the form $p=x^2+y^2$ (this can be proven using Thue Lemma), then we have that either $4=q^2$ or $4=4 \cdot 2021^c$ , of course neither can happen therefore we get a contradiction!. And if $c$ is odd then if $q \ge 5$ we get that as $2021 \equiv -1 \pmod 3$ that $t^2 \equiv 2 \pmod 3$ which is a contradiction so $q=3$ , but then $t^2=4 \cdot 2021^c+5 \equiv 5 \pmod 47$ and this is a contradiction as by QR's we have that $\left( \frac{5}{47} \right) = \left( \frac{47}{5} \right)= \left( \frac{2}{5} \right)=-1$ so no such $t$ should exist, contradiction!.
Case 2: $d=q$ prime.
In this case we have $a=qx+q$ and $b=qx$ and $[a,b]=q(x^2+x)$ so $2021^c=qx^2+qx+q=q(x^2+x+1)$ and so $q \mid 2021^c$ therefore $q=43,47$ , as an extra notice that if some prime $r \mid x^2+x+1$ then we must have by orders that either $r=3$ and $x \equiv 1 \pmod 3$ or $r \equiv 1 \pmod 3$ , but notice that $47 \equiv 2 \pmod 3$ so we must have $q=47$ and $c=1$ or else $47 \mid x^2+x+1$ and that can't happen, which means that we must have $43=x^2+x+1$ and it's clear that the only positive solution is $x=6$ therefore $a=47 \cdot 7=329$ and $b=47 \cdot 6=282$ and thus $p=611^2+4$ must be prime, but this can't happen as then $611^2+4 \equiv 1+4 \equiv 0 \pmod 5$ so $5 \mid p$ which would mean $p=5$ , an obvious size contradiction!.
Therefore in either case we can't have that $(a+b)^2+4$ is prime, thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

22 posts

#21 h Apr 23, 2025, 2:42 AM

Y by

Is this wrong?
Can someone check it!
Let $a>b$ , $a-b=p$ prime and $(a,b)=d$ . For the contrary let $(a+b)^2+4=q$ prime. Then $d\mid (a,b)\mid {a-b}=p$ , so $d=1$ or $p$ .
Case 1: If $d=1$ , then $ab+1=[a,b]+(a,b)=2021^c$ . If $c$ even then $(a+b)^2+2^2=q=(a-b)^2+4(ab+1)=(a-b)^2+(2\cdot2021^\frac{c}{2})^2$ , which is the contradiction, because a prime number has unique represantion as sum of two squares (I think its Fermat theorem). So if $c$ odd then $ab\equiv 1 \pmod 3$ , i.e $a\equiv b\pmod 3$ , so $a-b=p=3$ . So our condition becomes $b^2+3b+1\equiv 0\pmod {43}$ (in fact $b^2+3b+1=2021^c$ ). In other word $(2b+3)^2\equiv 8\pmod {43}$ , i.e $(\frac{8}{43})=1$ , but $1=(\frac{8}{43})=(\frac{2^3}{43})=(\frac{2}{43})=(-1)^{\frac{43^2-1}{8}}=-1$ , which is contradiction.
Case 2: If $d=p$ , then $a=b+p$ , $b=pb_1$ and $p(1+b_1(b_1+1))=(a,b)+[a,b]=2021^c$ , so $b_1(b_1+1)+1=43^{c-1}47^c$ or $43^c47^{c-1}$ . If $47\mid b_1(b_1+1)+1$ , then $b_1(b_1+1)+1\equiv 0\pmod {47}$ , i.e $(2b_1+1)^2\equiv -3\pmod {47}$ . So $(\frac{-3}{47})=1$ , but
$1=(\frac{-3}{47})=(\frac{-1}{47})(\frac{3}{47})=(-1)(\frac{47}{3})(-1)^{\frac{(3-1)(47-1)}{4}}=-1$ ,
which is contradiction. So $47\nmid b_1(b_1+1)+1$ , i.e $b_1(b_1+1)+1=43$ ( $c=1$ ), then $b_1=6$ , $p=47$ , $b=6\cdot47$ , $a=7\cdot47$ . And $(a+b)^2+4$ is not prime (because it divisible by 5).
So we are done!

This post has been edited 4 times. Last edited by NuMBeRaToRiC, May 2, 2025, 4:04 PM

Z K Y

The post below has been deleted. Click to close.

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

10 posts

#24 h Apr 27, 2025, 11:14 AM

Y by

sttsmet wrote:

Can anybody tell me the NAME of this well known theorem with the sum of two squares??

I think it's called "Fermat's Two Squares Theorem"

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a