INAMO 2019 P7

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

INAMO 2019 P7

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: INAMO 2019 P7

The post below has been deleted. Click to close.

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

1063 posts

#1 h Jul 3, 2019, 7:42 AM • 2 Y

Y by Adventure10, Mango247

Determine all solutions of
$x + y^2 = p^m$ $x^2 + y = p^n$ For $x,y,m,n$ positive integers and $p$ being a prime.

Z K Y

The post below has been deleted. Click to close.

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

1002 posts

Afo

#2 h Jul 3, 2019, 1:49 PM • 2 Y

Y by Adventure10, Mango247

Answer:
$(x,y,p,m,n)=( 1 ,1 ,2 ,1 ,1)$
$(x,y,p,m,n) =(2 ,5 ,3 ,3, 2)$
$(x,y,p,m,n) =(5, 2, 3 ,2 ,3)$
Progress:
When $m=n$ , we have
$x^2+y=x+y^2 \implies x=y$
So $x(x+1)=p^m \implies x =y=m=n=1, p = 2$

I think we can show p <5 by mod 6. But it's a lot of work.

This post has been edited 4 times. Last edited by Afo, Jul 3, 2019, 2:09 PM

Z K Y

The post below has been deleted. Click to close.

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

691 posts

#3 h Jul 3, 2019, 2:10 PM • 2 Y

Y by Adventure10, Mango247

Notice that if $m = n$ , then we must have $x = y$ . This gives us $(x,y,m,n) = (1,1,1,1)$ and $p = 2$ .
WLOG $m < n$ , then we have $y < x$ .
So, $x + y^2 | x^2 + y$ . Notice that $(x,y) = 1$ .
Thus, we have $x + y^2 | y^3 + 1$ Suppose $x + y^2 = p^n$ where $p \not= 3$ , or $p = 3$ but $(y + 1, y^2 - y + 1) = 1$ .
$x + y^2 | y + 1$ $x + y^2 | y^2 - y + 1$ Which are both impossible for size reasons.

Then, we just need to consider when $p = 3$ .
$x + y^2 | 3(y^2 - y + 1)$ Then, we have $3^{n - 1}| y^2 - y + 1$ .
So $y^2 - y + 1 = k . 3^{n - 1}$ . Suppose $k \ge 3$ , then we have $y^2 - y + 1 \ge 3^n = x + y^2$ , which is impossible
So $k = 1$ or $k = 2$ .
If $y^2 - y + 1 = 2 . 3^{n - 1}$ , LHS must be odd while RHS is even.
So, $y^2 - y + 1 = 3^{n - 1}$ . Then we have $y^3 + 1 = 3^{n - 1} . (y + 1)$ .
Checking $y = 1$ , we have $n = 1$ . Then, $x = 2$ , but $y + x^2 = 5 \not= 3^m$ . A contradiction.
Checking $y = 2$ , we have $n = 2$ . Then, $x = 5$ , then $y + x^2 = 27 = 3^3$ , which is a solution.
If $y \ge 3$ , notice that by Zsigmondy Theorem, there exists a primitive prime divisor of $y^3 + 1$ which is not in $y + 1$ , and furthermore, notice that $3 | y + 1$ . So, we are hence finished.

So, we have three solutions : $(x,y,m,n,p) = (1,1,1,1,2), (2,5,2,3,3), (5,2,3,2,3)$

This post has been edited 1 time. Last edited by IndoMathXdZ, Jul 3, 2019, 2:13 PM

Z K Y

The post below has been deleted. Click to close.

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

33 posts

Doppel

#4 h Aug 4, 2023, 2:56 AM

Y by

WLOG assume $x\ge y$ , we will divide this into two cases.
Case 1. $\quad x=y$
We have,
$x(x+1)=p^m=p^n$ Because $gcd(x,x+1)=1$ we must have $m=n=1$ . It follows that the only solution is $(x,y,p,m,n)=(1,1,2,1,1)$ .

Case 2. $\quad x>y$
Assume $gcd(x,y) \ne1$ , let $gcd(x,y)=p^k$ with $k,a,b\in \mathbb{N}$ such that $x=p^ka$ and $y=p^kb$ .
We have,
$a+p^kb^2=p^{m-k}$ $p^ka^2+b=p^{n-k}$ Because $m,n>k$ , we must have $p|a$ and $p|b$ from those two equation. A contradiction, therefore $gcd(x,y)=1$ .
Notice that,
$(x+y-1)(x-y)>0 \Rightarrow x^2+y>x+y^2 \Rightarrow p^n>p^m$ Hence $p^m|p^n$ , which is equivalent to
$x+y^2|x^2+y \Rightarrow x^2+y|y^4+y \Rightarrow p^m|(y+1)(y^2-y+1) \quad (1)$ Notice that $gcd(y+1,y^2-y+1)=1$ or $3$ , if $gcd(y+1,y^2-y+1)=1$ . Then
$p^m|y+1 \Rightarrow x+y^2\le y+1$ or
$p^m|y^2-y+1 \Rightarrow x+y^2\le y^2-y+1$ Both possibility implies a contradiction(size reason), then we must have $gcd(y+1,y^2-y+1)=3$ .
Therefore $p=3$ , from $(1)$
$3^{m-2}|\big(\frac{y+1}{3}\big)\big(\frac{y^2-y+1}{3}\big)$ Because $gcd\big(\frac{y+1}{3},\frac{y^2-y+1}{3}\big)=1$ ,
$3^{m-2}|\frac{y+1}{3} \Rightarrow 3^{m-1}|y+1$ or
$3^{m-2}|\frac{y^2-y+1}{3} \Rightarrow 3^{m-1}|y^2-y+1$ By size reason, of course $3^{m-1}|y^2-y+1$ . Notice that $y^2-y+1$ is odd, because $y^2-y+1<x+y^2=3^m$ , $y^2-y+1=3^{n-1}$ .
We have $y^3+1=3^{n-1}(y+1)$ .
For $y\le 2$ , the only solution is $(x,y,p,m,n)=(5,2,3,2,3)$
For $y\ge3$ , notice that $3|y+1$ . By Zsigmondy, there exist a prime $p$ such that $p|y^3+1$ and $p\nmid y+1$ which implies $p|3^{n-1}(y+1)$ .
A contradiction, the only solution for this case is $(x,y,p,m,n)=(5,2,3,2,3)$ .

We can conclude from those two cases, that the only solutions are $(x,y,p,m,n)=(1,1,2,1,1),(5,2,3,2,3),(2,5,3,3,2)$ .

This post has been edited 4 times. Last edited by Doppel, Aug 4, 2023, 3:04 AM

Z K Y

The post below has been deleted. Click to close.

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

27 posts

Nartku

#7 h Apr 12, 2024, 3:51 AM

Y by

Different approach

This post has been edited 2 times. Last edited by Nartku, Apr 12, 2024, 5:00 AM

Z K Y

The post below has been deleted. Click to close.

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

1239 posts

#8 h Jul 9, 2024, 4:31 PM

Y by

IndoMathXdZ wrote:

WLOG $m < n$ , then we have $y < x$ .
So, $x + y^2 | x^2 + y$ . Notice that $(x,y) = 1$ .

I'm sorry, but why must we immediately have $(x,y)=1$ ?

EDIT, ok I saw in below posts, but yeah, this just needs a bit of justification.

This post has been edited 1 time. Last edited by Assassino9931, Jul 9, 2024, 4:32 PM

Z K Y

The post below has been deleted. Click to close.

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

1239 posts

#9 h Jul 9, 2024, 4:55 PM

Y by

Here's a very quick simple approach.

Answer. $(1,1)$ , $(2,5)$ , $(5,2)$

Let $a^2 + b = p^m$ , $a + b^2 = p^n$ , without loss of generailty let $m\leq n$ . If $m=n$ , and $a^2 + b = a + b^2$ , so $(a-b)(a+b-1) = 0$ and $a=b$ , but in $a(a+1) = p^m$ the multipliers on the left are coprime, whence $a=1$ (and $a=b=1$ satisfies the requirements).

From now on $m < n$ , so (as above) $a<b$ . Then $a^2 + b = p^m$ divides $b^2 + a = p^n$ , thus $a^2 + b$ also divides $a^4 + a$ (as $a^4 - b^2 = (a^2-b)(a^2+b)$ is divisible by $a^2+b$ ), i.e.
$p^m = a^2 + b \mbox{ divides } a(a+1)(a^2-a+1).$ We have $\gcd(a,a+1) =$ $\gcd(a, a^2 - a + 1) = 1$ and $\gcd(a+1, a^2-a+1) = 1$ or $3$ . Hence if $a$ is divisible by $p$ , then $p^m$ is coprime with $a+1$ and $a^2-a+1$ and necessarily divides $a$ , implying $a^2 + b = p^m \leq a$ , impossible. From now on we assume that $a$ is not divisible by $p$ and hence $p^m$ divides $(a+1)(a^2 - a + 1)$ . We have two cases:

If $p\neq 3$ , then $p^m = a^2 + b$ divides fully at least one of $a+1$ and $a^2-a+1$ (due to their gcd), which is impossible for $a\geq 2$ , as $a^2 + b > a^2 \geq a^2 - a + 1 \geq a + 1$ ; and for $a=1$ we need $p^m$ to divide $2$ , so $p=2$ , $m=1$ and $b=1$ , which we got in the beginning.

Now let $p=3$ . Necessarily $a+1$ and $a^2-a+1$ are divisible by $3$ (and $m\geq 2$ ), otherwise they are coprime and we obtain a contradiction as in the previous case. Direct verification shows that $a^2-a+1$ is not divisible by $9$ for any $a$ . Hence in
$\frac{a^2+b}{9} = 3^{m-2} \mbox{ divides } \frac{a+1}{3} \cdot \frac{a^2-a+1}{3}$ the dividend and the multiplier $\displaystyle \frac{a^2-a+1}{3}$ are coprime, so necessarily $\displaystyle \frac{a^2+b}{9}$ divides $\displaystyle \frac{a+1}{3}$ . In particular, $a^2 + a + 1 \leq a^2 + b \leq 3a + 3$ , i.e. $a(a-2) \leq 2$ . Therefore (as $a+1$ is divisible by $3$ ) the only option is $a=2$ and $\displaystyle \frac{4+b}{9}$ to divide $1$ , i.e. $b=5$ . Note that $(2,5)$ (and $(5,2)$ ) is indeed a solution, since $2^2 + 5 = 3^2$ and $5^2 + 2 = 3^3$ .

Z K Y

The post below has been deleted. Click to close.

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

21 posts

#10 h Apr 2, 2025, 5:04 AM

Y by

WLOG: $x \geq y$ , then $m \leq n$ . Substract both equation gives
$p^n - p^m = (x - y)(x + y - 1) \Rightarrow p^m | (x - y)(x + y - 1)$ Case 1. $p$ divides $x - y$ .
We also have $p$ divides $x + y^2$ so $x + y^2 \equiv x - y \mod p$ . Then we have $y^2 + y \equiv 0 \mod p$ . Which gives $y \equiv 0, -1 \mod p$ .

Case 1.1: $y \equiv 0 \mod p$
Hence $x \equiv 0 \mod p$ , clearly $p \nmid x + y - 1$ , so $x \equiv y \mod p^m$ .
Notice that if $x \neq y$ , hence $\max(x, y) > p^m$ gives $x + y^2 > p^m$ . So we must have $x = y$ , which gives $x + x^2 = p^m$ . Only $x = 1, p = 2$ works, which $1 \not\equiv 0 \mod p$ . No solution in this case.

Case 1.2: $y \equiv -1 \mod p$
Hence $x \equiv -1 \mod p$ .
Case 1.2.1: $p$ divides $x + y - 1$
then we have $x + y - 1 \equiv -3 \equiv 0 \mod p$ . Thus, we have $p = 3$ .
$x + y^2 = 3^m \Rightarrow x + (3^n - x^2)^2 = 3^m \Rightarrow x^4 + x = 3^m - 3^{2n} - 2\cdot 3^n \cdot x^2$ As $m \geq n$ , we have $x^4 + x \equiv 0 \mod 3^m$ . Because $\gcd(x, 3) = 1$ , we have $x^3 + 1 \equiv 0 \mod 3^m$ .
$x^3 + 1 = (x + 1)(x^2 - x + 1) = (x + 1)((x + 1)^2 - 3x) \equiv 0 \mod 3^m$ Let $v_3(x + 1) = j$ . It's easy to see that $v_3((x+1)^2 - 3x) = 1$ as $\gcd(x, 3) = 1$ . Thus $j \geq m - 1$ . Let $x = k.3^{m-1} - 1$ . We'll plug the value of $x$ into the first equation.

If $k = 1$ gives $y^2 - 1 = 2 \cdot 3^{m-1} \Rightarrow (y - 1)(y + 1) = 2 \cdot 3^{m-1}$ . No solution.
If $k = 2$ gives $y^2 - 1 = 3^{m-1} \Rightarrow (y - 1)(y + 1) = 3^{m-1}$ . Works for $y = 2$ . Plugging further $(x, y, p, m, n) = (5, 2, 3, 2, 3)$ .
If $k = 3$ gives $y = 1$ , to the second equation $x^2 + 1 = 3^n$ , no solution for $x$ .
If $k > 3$ to the first equation, $y < 0$ .

Case 1.2.2: $p$ doesn't divide $x + y - 1$
Hence $p^m | x - y$ . If $x \neq y$ , $\max(x, y) > p^m$ which result to $x + y^2 > p^m$ . Contradiction. So $x = y$ , which gives $x + x^2 = p^m$ . Only $x = 1, p = 2$ works, so $(x, y, p, m, n) = (1, 1, 2, 1, 1)$ .

Case 2. $p$ doesn't divide $x - y$
Hence $p^m | x + y - 1$ , as $x + y - 1 > 0$ , hence $x + y - 1 \geq p^m$
$x + y^2 \geq x + 2y - 1 > x + y - 1 \geq p^m$ No solution.

Therefore all solution is $(5, 2, 3, 2, 3), (2, 5, 3, 3, 2), (1, 1, 2, 1, 1)$ , it's easy to see that all values satisfies both equation.

This post has been edited 1 time. Last edited by SYBARUPEMULA, Apr 3, 2025, 11:15 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a