IMO Shortlist 2014 N5

The post below has been deleted. Click to close.

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

209 posts

#1 h Jul 11, 2015, 9:09 AM • 14 Y

Y by ahmedosama, Davi-8191, dalarin01, anantmudgal09, Hypernova, HolyMath, KNM, pog, megarnie, PNT, Adventure10, Mango247, NicoN9, Funcshun840

Find all triples $(p, x, y)$ consisting of a prime number $p$ and two positive integers $x$ and $y$ such that $x^{p -1} + y$ and $x + y^ {p -1}$ are both powers of $p$ .

Proposed by Belgium

This post has been edited 3 times. Last edited by hajimbrak, Jul 23, 2015, 10:51 AM
Reason: Added proposer

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#2 h Jul 11, 2015, 10:10 AM • 14 Y

Y by kaito_shinichi, huyaguero, anantmudgal09, bluephoenix, SAM8, Math-Ninja, AlastorMoody, rashah76, mijail, pog, math31415926535, Adventure10, Mango247, NicoN9

I like this problem!
Solution

This post has been edited 2 times. Last edited by 62861, Jul 16, 2015, 9:08 PM
Reason: typo

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

#3 h Jul 11, 2015, 4:35 PM • 26 Y

Y by quangminhltv99, randomusername, Devesh14, anantmudgal09, PRO2000, steppewolf, ZzIsaacNewtonZz, MathbugAOPS, yayups, Loppukilpailija, AlastorMoody, Aryan-23, Leia_Skywalker, pog, Kobayashi, HamstPan38825, chystudent1-_-, math31415926535, PNT, ThisNameIsNotAvailable, Kingsbane2139, Adventure10, Mango247, NicoN9, Frank25, Funcshun840

If $p=2$ then any $(x,y)$ with $x+y$ a power of two is okay.

Hence assume $p > 2$ . Then if $\nu_p(x) \ge \nu_p(y) > 0$ we get an immediate contradiction, thus we may assume $p \nmid x,y$ . So by Fermat's Little Theorem, $x$ and $y$ are $-1 \pmod p$ .

It is easy to check that when $p > 2$ we cannot have $x=y$ , since otherwise $x(x^{p-2}+1)$ is a power of $p$ , which is clearly impossible when $p=2$ . Moreover, if $p > 2$ then $x^{p-1}+y \neq y^{p-1}+x$ , since otherwise $(x-y)(x^{p-2}+\dots+y^{p-2}) = x-y$ , which is impossible unless $x=y$ .

Thus, suppose $y^{p-1}+x < x^{p-1}+y$ , which is equivalent to $y < x$ . Then in particular $y^{p-1}+x$ divides $x^{p-1}+y$ , so $y^{p-1} + x \mid (-y^{p-1})^p + y \implies y^{p-1}+x \mid y^{p(p-2)}+1.$ By Lifting the Exponent, we thus deduce that $\nu_p(y^{p-1}+x) \le 1 + \nu_p(y+1).$ Actually, since LHS is a power of $p$ , this informs us that $y^{p-1} + x \mid p \cdot (y+1) \implies y^{p-1} + x \le p \cdot (y+1).$ Since $x > y$ , this forces $y^{p-1} + y \le p \cdot (y+1).$ Also, $y \ge p-1$ since $y \equiv -1 \pmod p$ . This can only occur if $y = 2$ and $p = 3$ .

So, it remains to find all $x > 2$ such that $x^2+2$ and $4+x$ are powers of $3$ . Letting $4+x=3^b$ , we find that $\left( 3^b-4 \right)^2 + 2 = 3^{2b} - 8 \cdot 3^b + 18$ is supposed to be a power of $3$ , which can only occur for $b \le 1$ . Checking, this gives the last solution $(x,y,p) = (5,2,3)$ .

This post has been edited 1 time. Last edited by v_Enhance, Jul 11, 2015, 4:35 PM
Reason: Spacing

Z K Y

The post below has been deleted. Click to close.

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

andria

824 posts

andria

#4 h Jul 16, 2015, 6:18 PM • 3 Y

Y by A_Math_Lover, pog, Adventure10

have another solution:
Obviously if $p=2, x+y=2^s$ is a solution if the problem so assume that $p\ge 3$ and let $x^{p-1}+y=p^{\gamma}(1), x+y^{p-1}=p^{\beta}$ (2)
Consider two cases:
1) $p\mid x$ then it's obvious that $p\mid y$ let $v_p (x)=r, v_p (y)=t$ then from (1),(2) we get $(p-1)r=t,(p-1)t=r$ which is contradiction for $p\ge 3$ so there isn't any solution in this case.
2) $p\nmid x,y$ note that if $x=y$ then $x^{p-1}+x=p^{\gamma} \longrightarrow p\mid x$ which is a contradiction so without loss of generality assume that $x>y\longrightarrow \gamma>\beta$ note that from (1): $y=p^{\gamma}-x^{p-1}$ substituting this in (2) we get $x+(p^{\gamma}-x^{p-1})^{p-1}=p^{\beta}$ (3) now taking this equality modulo $p^{\beta+1}$ we have $x+(p^{\gamma}-x^{p-1})^{p-1}\equiv x+x^{(p-1)^2}\equiv p^{\beta}\pmod{p^{\beta+1}}\longrightarrow v_p (x^{(p-1)^2-1}+1)=\beta$ using lifting exponent lemma we get $\beta=v_p (x^{(p-1)^2-1}+1)=v_p (x+1)+v_p ((p-1)^2-1)=v_p (x+1)+1\longrightarrow v_p (x+1)=\beta-1\longrightarrow x\equiv -1\pmod{p^{\beta-1}}, x=p^{\beta-1}l+1$ (4).
Now notice that using (4): $p^{\gamma}-x^{p-1}\equiv -1\pmod{p^{\beta-1}}\longrightarrow p^{\gamma}-x^{p-1}=p^{\beta-1}r-1$ now substituting this in (3) we get $x+(p^{\beta-1}r-1)^{p-1}=p^{\beta}$ but since $p-1\ge 2, r\ge 1, x=p^{\beta-1}l-1$ : $p^{\beta}=x+(p^{\beta-1}r-1)^{p-1}\ge (p^{\beta-1}-1)^{p-1}+p^{\beta-1}-1=(p^{\beta-1}-1)(1+(p^{\beta-1}-1)^{p-2})$ from this inquality we immediately get $p=3,\beta=2$ which gives us the solution $(3,5,2)$ .
Q.E.D

This post has been edited 1 time. Last edited by andria, Jul 16, 2015, 6:25 PM

Z K Y

The post below has been deleted. Click to close.

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

JackXD

151 posts

JackXD

#5 h Jul 30, 2015, 7:23 PM • 4 Y

Y by Navi_Makerloff, pog, Adventure10, Mango247

If $p=2$ then any $x+y$ being a power of two will do.Let $p \ge 3$ .

Let $x^{p-1}+y=p^k$ and $y^{p-1}+x=p^l$ .If $x=y$ then we have $x(x^{p-2}+1)=p^k$ which is not possible because $gcd(x,x^{p-2}+1)=1$ .So wlog $x>y$ .Then $k>l$ .
If $p|x,y$ then let $p^{\alpha}||x,p^{\beta}||y$ .Then we must have $\alpha(p-1)=\beta$ and $\beta(p-1)=\alpha$ simultaneously which is not possible.So now we work on the case when $x,y$ are not divisible by $p$ .
Let $p^j||x-y$ .From the two relations it is easy to see that $x^p-y^p=p^kx-yp^l$ .Thus $v_p(p^kx-p^ly)=j+1 \implies l=j+1$ .Thus $y^{p-1}+x=p^{j+1} \implies y^{p-1}+y+x-y=p^{j+1} \implies p^j||y^{p-1}+y \implies p^j||y^{p-2}+1=(y+1)(y^{p-3}-y^{p-4}+\cdots+1)$ .From $y \equiv -1{\pmod{p}}$ we get that the second factor leaves remainder $p-2$ upon division by $p$ .So $p^j||y+1 \implies y \ge p^jl-1$ .Thus $p^{j+1}=y^{p-1}+x>y^{p-1} \ge (p^j-1)^{p-1}$ .This is not possible for $p>3$ .Also for $p=3$ it is possible only for $j=1$ .Checking into this possibility we have to have $y^2+x=9$ .The only solution in $(x,y)$ satisfying this such that $x^2+y$ is also a power of three is $(2,5)$ .

So the solutions are $(2,x,y)$ where $x+y$ is a power of two, $(3,2,5),(3,5,2)$ .

This post has been edited 3 times. Last edited by JackXD, Jul 30, 2015, 7:31 PM
Reason: XX

Z K Y

The post below has been deleted. Click to close.

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

juckter

323 posts

juckter

#6 h Dec 21, 2015, 4:21 AM • 3 Y

Y by pog, Adventure10, Mango247

If $p = 2$ then $x + y$ a power of two works. Assume $p \geq 3$

Let $x^{p - 1} + y = p^{\alpha}$ and $y^{p - 1} + x = p^{\beta}$ . If one of $x, y$ is divisible by $p$ then the other is also divisible by $p$ , in this case we have $\upsilon_p(y) = \upsilon_p(x^{p - 1}) = (p - 1)\upsilon_p(x)$ as otherwise $x^{p - 1} + y > p^{\max\{(p - 1)\upsilon_p(x), \upsilon_p(y)\}}$ but this number does not divide $x^{p - 1} + y$ . Similarly we have $\upsilon_p(x) = (p - 1)\upsilon_p(y)$ , but it is impossible for these two relations to hold as $p > 2$ . Hence $x, y$ are not divisible by $p$ and so by FLT they are congruent to $-1 \mod{p}$ . Additionally we check that $\alpha \neq \beta$ as otherwise we have $\displaystyle\frac{x^{p - 1} - y^{p - 1}}{x - y} = 1$ which is impossible as $p - 1 > 1$ . We also have $x \neq y$ as $x(x^{p - 2} + 1)$ is not a power of $p$ since $p \nmid x$ .

Now assume $x > y$ so $\alpha > \beta$ . We have $x^p + xy = p^{\alpha}x$ and $y^p + xy = p^{\beta}y$ . Substracting gives us $x^p - y^p = p^{\alpha}x - p^{\beta}y$ so that $\upsilon_p(x - y) + 1 = \upsilon_p(x^p - y^p) = \beta$ by LTE. Put $x - y = p^{\beta - 1}k$ . Substituting gives us $y^{p - 1} + p^{\beta - 1}k + y = p^{\beta} \implies y(y^{p - 2} + 1) = p^{\beta - 1}(p - k)$ . As $p \nmid y$ this implies $p^{\beta - 1} \mid (y^{p - 2} + 1)$ . Thus
$p^{\beta -1}(p - 1) \geq p^{\beta - 1}(p - k) = y(y^{p - 2} + 1) \geq (p - 1)(p^{\beta - 1})$ Where the last equality follows from $p \mid y + 1 \implies y \geq p - 1$ . Thus $y = p - 1$ , $k = 1$ and $y^{p - 2} + 1 = p^{\beta - 1}$ as all equalities must hold. Thus by LTE $\beta - 1 = \upsilon_p(y^{p - 2} + 1) = \upsilon_p(y + 1) = 1$ as $p - 2$ is odd and $y + 1 = p$ . Hence $\beta = 2$ . Thus $(p - 1)^{p - 2} + 1 = p$ giving $p = 3$ . Finally $y = 2$ and $x = 5$ from $x = p^{\beta - 1}k + y$ , which clearly works.

Z K Y

The post below has been deleted. Click to close.

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

Dukejukem

695 posts

Dukejukem

#7 h Jan 12, 2016, 12:47 AM • 2 Y

Y by pog, Adventure10

If $p = 2$ , any pair $(x, y)$ with $x + y$ a power of $2$ works. Henceforth, assume that $p \ne 2$ and write $x^{p - 1} + y = p^{\alpha}$ and $x + y^{p - 1} = p^{\beta}$ with WLOG $1 \le \alpha \le \beta.$ Clearly, $0 \equiv y^{p - 2} \cdot p^{\alpha} - p^{\beta} \equiv x\left[(xy)^{p - 2} - 1\right] \pmod{p^{\alpha}}. \quad (\star)$ If $p \mid xy$ , then evidently $p \nmid (xy)^{p - 2} - 1.$ Hence, $(\star)$ forces $x \equiv 0 \pmod{p^{\alpha}}$ , which is obviously false for size reasons.

Therefore $p \nmid xy$ , so from $(\star)$ we obtain $(xy)^{p - 2} \equiv 1 \pmod{p^{\alpha}}.$ Moreover, Fermat's Little Theorem applied to $x^{p - 1} + y = p^{\alpha}$ and $x + y^{p - 1} = p^{\beta}$ gives $x \equiv y \equiv -1 \pmod{p}.$ Hence, $p \mid xy - 1$ , so LTE yields $\alpha \le \nu_p\left[(xy)^{p - 2} - 1\right] = \nu_p(xy - 1) \implies xy \equiv 1 \pmod{p^{\alpha}}.$ Consequently, $x^{p} + xy = x \cdot p^{\alpha} \implies x^{p} + 1 \equiv 0 \pmod{p^{\alpha}}.$ Lifting the Exponent, $\alpha \le \nu_p(x^p + 1) = 1 + \nu_p(x + 1) \implies p^{\alpha} \le p^{1 + \nu_p(x + 1)} \le p(x + 1).$ Substituting $x^{p - 1} + y = p^{\alpha}$ , it follows that $x(x^{p - 2} - p) \le p - y. \quad (\dagger)$ On account of $y \equiv -1 \pmod{p}$ , we see that $p - y \le 1.$ Therefore, $x^{p - 2} - p \le 1$ , and since $x \equiv -1 \pmod{p}$ , this forces $p - 2 = 1$ and $x = p - 1.$ Thus, $p = 3, x = 2$ and so $-2 \le 3 - y$ by $(\dagger).$ Using $y \equiv -1 \pmod{p}$ , it remains to check $y \in \{2, 5\}$ , which gives the solution $(p, x, y) = (3, 2, 5)$ and its conjugate $(p, x, y) = (3, 5, 2).$

Z K Y

The post below has been deleted. Click to close.

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

navi_09220114

478 posts

navi_09220114

#8 h Apr 26, 2016, 3:55 PM • 2 Y

Y by pog, Adventure10

If $p=2$ , then $x+y$ is power of $2$ , then any triplets in form of $(2,x,2^k-x), x<2^k, k\in \mathbb{N}$ , are the only solutions. So we assume $p\ge 3$ .

Claim 1. $x,y\equiv -1 \pmod p$ .

Proof. If $p\mid x$ , then $x^{p-1}+y$ is a power of $p$ greater than $p^{p-1}$ , so $p^{p-1}\mid x^{p-1}+y \Rightarrow p^{p-1}\mid y$ , and so $x+y^{p-1}$ is a power of $p$ greater than $p^{(p-1)^2}$ , so $p^{(p-1)^2}\mid x+y^{p-1} \Rightarrow p^{(p-1)^2}|x$ , and we can continue this process to get $p^{(p-1)^3}\mid y \Rightarrow p^{(p-1)^4}\mid x \Rightarrow p^{(p-1)^5}\mid y \Rightarrow \cdots$ , a contradiction since $p-1 \ge 2$ we have $v_p(x)\ge (p-1)^{2n}$ for all $n$ which tends to infinity for large $n$ , which cannot hold. So $p$ does not divides $x$ , so as $y$ . By Fermat Little Theorem, $x^{p-1}\equiv 1 \pmod p \Rightarrow y\equiv -1\pmod p$ . Similarly, $x\equiv -1 \pmod p$ .

Claim 2. $p^2$ does not divides $x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1$ .

Proof. By Lifting the Exponent Lemma, since from Claim 1, $p|x+1$ , and $p$ does not divides $x$ and $1$ , we have $v_p(x^{(p-1)^2-1}+1)= v_p(x+1)+v_p((p-1)^2-1)= v_p(x+1)+1$ . Now note that $x^{(p-1)^2-1}+1=(x+1)(x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1)\Rightarrow v_p(x^{(p-1)^2-1}+1)= v_p(x+1)+v_p(x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1) \Rightarrow v_p(x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1)=1$ .

Claim 3. $x^{p-1}+y\mid x^{(p-1)^2-1}+1$ .

Proof. Suppose $x\le y$ , then since $x^{p-1}+y$ and $x+y^{p-1}$ are both distinct powers of $p$ , then $x^{p-1}+y\mid x+y^{p-1}$ , and since $p$ is odd, $x^{p-1}+y\mid x^{p(p-1)}+y^p$ . Together we have $x^{p-1}+y\mid x^{p(p-1)}+y^{p}-y(x+y^{p-1}) \Rightarrow x^{p-1}+y\mid x^{p(p-1)}-xy$ . Since $p$ does not divides $x$ , $(p,x)=1$ , so $x^{p-1}+y\mid x^{p(p-1)}-xy \Rightarrow x^{p-1}+y\mid x^{p(p-1)-1}-y \Rightarrow x^{p-1}+y\mid x^{p(p-1)-1}-y+(x^{p-1}+y) \Rightarrow x^{p-1}+y\mid x^{p(p-1)-1}+x^{p-1} \Rightarrow x^{p-1}+y\mid x^{(p-1)^2-1}+1$ .

Claim 4. $x^{p-1}\le p(x+1)$

Proof. From Claim 3, $x^{p-1}+y\mid x^{(p-1)^2-1}+1=(x+1)(x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1)$ . Since from Claim 2, $p\mid\mid x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1$ , then we have $x^{p-1}+y\mid (x+1)(x^{(p-1)^2-2}-x^{(p-1)^2-3}+\cdots +1) \Rightarrow x^{p-1}+y\mid p(x+1) \Rightarrow x^{p-1}< p(x+1)$ .

Claim 5. The only solutions for odd primes $p$ are $(3,2,5)$ and $(3,5,2)$ .

Proof. From Claim 4, $x^{p-1}< p(x+1) \Rightarrow x^{p-1}-px-1< 0$ . The derivative of the function $f(x)=x^{p-1}-px+1$ is $(p-1)x^{p-2}-p$ , which is greater than $0$ for all $x\ge 2$ and for all $p$ . Since $f(2)\ge 0$ for $p\ge 5$ , $f(x)< 0$ for $x\ge p-1\ge 2$ has no solutions. So the only case is $p=3$ , which we get $x^2< 3(x+1) \Rightarrow x\le 3$ , but since $x\equiv -1 \pmod 3$ , then $x=2$ . Then $4+y, 2+y^2$ is power of $3$ , so $y+4\mid 2+y^2=(y+4)(y-4)+18 \Rightarrow y+4\mid 18$ Since $y+4$ is power of $3$ greater than $4$ and divisor of $18$ , we must have $y+4=9 \Rightarrow y=5$ . So $(3,2,5)$ is a solution for $x\le y$ , and by symmetry, $(3,5,2)$ is also a solution. So the only solutions for odd primes $p$ are $(3,2,5)$ and $(3,5,2)$ .

In conclusion, the only solutions are $(2,x,2^k-x), x<2^k, k\in \mathbb{N}$ , $(3,2,5)$ and $(3,5,2)$ , and these are easily checked to be solutions.

Z K Y

The post below has been deleted. Click to close.

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

tenplusten

1000 posts

tenplusten

#9 h Mar 2, 2017, 6:24 AM • 2 Y

Y by pog, Adventure10

LTE and use some inequalitites Which can be proven by İnduction.

Z K Y

The post below has been deleted. Click to close.

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

tree3

641 posts

tree3

#10 h Jan 20, 2018, 12:22 AM • 3 Y

Y by pog, Adventure10, Mango247

Let's first take the obvious case of $p=2$ . We can just take $x=k, y=2^n-k$ where $n$ and $k$ are positive integers. Suppose that $x^{p-1}+y=p^k \leq y^{p-1}+x=p^r$ . Then $k \leq r$ . Notice that $x^{p-1}+y=p^k$ , so we can say $x^{p-1} \equiv -y \mod p^k$ . Similarly we get $y^{p-1} \equiv -x \mod p^k$ . We can deduce that $x^{(p-1)^2} \equiv -x \mod p$ and since $p$ does not divide $x,y$ for $p>2$ , we can deduce that $x^{2p(p-2)} \equiv 1 \mod p^k$ . By FLT and the gcd lemma, we can see that $x^{gcd((p-1)p^{k-1},2p(p-2)} \equiv x^{2p} \mod p^k$ . For size reasons, we immediately rule out the possibilities of $p^k|x-1,x+1$ , so $p^k|x^p-1$ or $p^k|x^p+1$ . Notice that FLT on the original equations gives $x,y \equiv -1 \mod p$ , so it must be the second case. LTE now gives $k \leq v_p(x+1)+1$ , implying $x \geq p^{k-1}-1$ . This allows us to see that $x^{p-1}+y \geq x^{p-1}+1 \geq (p^{k-1}-1)^{p-1}+1>p^k$ , giving contradiction for all odd primes as long as $k>3$ . First we handle $x^{p-1}+y=p$ . We get that $x<2$ , implying $x+1=2$ , contradiction. Now consider $x^{p-1}+y=p^2$ . We can see that $x$ must be no more than $3$ for $p \geq 3$ , implying that $x+1=2,3,4$ , only the middle of which is divisible by an odd prime. Similarly $x^{p-1}+y=p^3$ , implying that $x \leq 5$ , implying that $x+1=2,3,4,5,6$ , only $3$ and $5$ of which are odd. However $5$ fails because $4^{p-1}>p^3$ for $p>3$ and $(4,11)$ fails. Thus $p=3$ . So $x^2+y$ and $y^2+x$ are both powers of $3$ . $x^2+y$ must then equal $9,27$ . From here, we can easily get the only other solution to be $x=2, y=5$ . Thus all solutions are in the forms $(2,x,y)$ where $x+y$ is a power of two, $(3,2,5),(3,5,2)$ .

This post has been edited 7 times. Last edited by tree3, Oct 3, 2019, 5:25 AM

Z K Y

The post below has been deleted. Click to close.

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

Superguy

354 posts

Superguy

#11 h Apr 10, 2018, 8:37 AM • 3 Y

Y by AlastorMoody, pog, Adventure10

Solution

$\boxed{Claim-1}$

$\boxed{p\mid x \implies no solution}$

Proof::if $p\mid x$ then $p\mid y$
but we can see that $v_p({x^{p-1}})=v_p({y})$ and $v_p({y^{p-1}})=v_p({x})$ which is absurd. $\square$

$\boxed{Claim-2}$

$\boxed{p\nmid x\implies p=2,3 }$

Proof :we assume W.L.O.G $y>x$ and $p\geq 3$
Denote $x^{p-1}+y=p^k$ , $y^{p-1}+x=p^l$
$x^{p-1}+y\equiv 1+y\pmod{p}$
$y^{p-1}+x\equiv 1+x\pmod{p}$
Now as $y>x$
$x^{p-1}+y \mid y^{p-1}+x$
$\implies x^{p-1}+y \mid x^{p-2}y^{p-1}+x^{p-1}$ $\implies x^{p-1}+y \mid x^{p-2}y^{p-1}+x^{p-1}-(x^{p-1}+y)$ $\implies x^{p-1}+y \mid (xy)^{p-2}-1$ By F.L.T, $(xy)^{p^{k-1}.(p-1)}\equiv 1\pmod {p^k}$
$(p^{k-1}.(p-1),(p-2))=1$ for $p\geq 3$
$\implies (xy)\equiv 1\pmod {p^k}$
$\implies x^p+xy\equiv 0\pmod {p^k}$ $\implies x^p\equiv -1\pmod {p^k}$ Lifting the exponent ,
$v_p({x^{2p}-1})=v_p({x+1})+1$ $\implies p(x+1)\geq x^{p-1}+y$ Case-1
Case-2
THUS our claims are proved and Now we are left with case $p=2$
we have infinite solutions with $x+y=2^k$ $\blacksquare$
$Q.E.D$

This post has been edited 1 time. Last edited by Superguy, Apr 10, 2018, 8:40 AM

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

#12 h Apr 10, 2018, 2:23 PM • 3 Y

Y by pog, 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.

yayups

1614 posts

yayups

#13 h Dec 4, 2018, 8:42 AM • 3 Y

Y by AlastorMoody, pog, Adventure10

Bashy solution:

The solutions are $p=2$ and any $x,y$ with $x+y$ is a power of $2$ , and the solution $(p=5,\{x,y\}=\{2,5\})$ . It is easy to check that these work. Firstly, if $p=2$ , then we must have $x+y$ is a power of $2$ , and we have that solution. From now on, we assume $p\ge 3$ .

Claim 1: If $p\nmid x,y$ .
Proof of Claim 1: Suppose $p^k\mid x,y$ with $k\ge 1$ , and furthermore suppose this is the largest $k$ with the previous properties. Let $x=p^ka$ and $y=p^kb$ . Then,
$p^r=x^{p-1}+y=(p^ka)^{p-1}+p^kb.$ Firstly, note that $r>k(p-1)$ . Note that $k(p-1)\ge 2k>k$ , so taking mod $p^{k(p-1)}$ , we have that
$p^{k(p-1)}\mid p^k b,$ so in particular, $p\mid b$ . We can very similarly show that $p\mid a$ , so we have $p^{k+1}\mid x,y$ , which is the desired contradiction. $\blacksquare$

Note by Fermat's little theorem, we must have that $y+1,x+1\equiv 0\pmod{p}$ . Let $x=p^ka-1$ and $y=p^kb-1$ where $k\ge 1$ , and is again the greatest $k$ with given properties.

Claim 2: Unless $p=3$ and $k=1$ and $(a=1\text{ or }b=1)$ , we have that $x^{p-1}+y,y^{p-1}+x> p^{k+1}$ .
Proof of Claim 2: Suppose $x^{p-1}+y\le p^{k+1}$ . Therefore, $x^{p-1}<p^{k+1}$ , so
$(p^k a-1)^{p-1}<p^{k+1}.$ If $a\ge 2$ , then
$(p^ka-1)^{p-1}\ge p^{k(p-1)}\ge p^{2k}\ge p^{k+1},$ which is a contradiction. Therefore, $a=1$ , so
$(p^k-1)^{p-1}<p^{k+1}.$ If $k\ge 3$ , then
$(p^k-1)^{p-1}\ge p^{2(k-1)}\ge p^{k+1},$ which is a contradiction, so $k\le 2$ . If $k=2$ , then we have
$(p^2-1)^{p-1}\ge (p^2-1)^2,$ and it is easy to see that for $p\ge 3$ , we have $(p^2-1)^2\ge p^3$ , so there is a contradiction. Thus, $k=1$ , so
$(p-1)^{p-1}<p^2.$ It is easy to see that the only solution for $p\ge 3$ is $p=3$ , so we must have $p=3$ . Therefore, in this case $p=3,k=1,a=1$ . In the case $y^{p-1}+x<p^{k+1}$ , we have $p=3,k=1,b=1$ , so the claim is proved. $\blacksquare$

We will revisit the case $p=3,k=1,(a=1\text{ or }b=1)$ later, so for now assume that $x^{p-1}+y,y^{p-1}+x\ge p^{k+1}$ . We see that for $r\ge k+2$ , we have that
$p^r=(p^ka-1)^{p-1}+(p^kb-1)=p^k(a+b)+ap^{k+1}\left[-1+a\binom{p-1}{2}p^{k-1}\right]+p^{k+2}(\text{other integer terms}).$ Therefore, taking mod $p^{k+1}$ , we see that $p\mid a+b$ , and taking mod $p^{k+2}$ , we have that
$a\left[-1+a\binom{p-1}{2}p^{k-1}\right]\equiv -\frac{a+b}{p}\pmod{p}.$ Doing the same for $y^{p-1}+x$ , we see that
$a\left[-1+a\binom{p-1}{2}p^{k-1}\right]\equiv b\left[-1+b\binom{p-1}{2}p^{k-1}\right]\pmod{p}.$ If $k=1$ , then $a(a-1)\equiv b(b-1)\pmod{p}$ , so $a^2-b^2\equiv b-a\pmod{p}$ , so $a\equiv b\pmod{p}$ . Combined with $p\mid a+b$ , this means that $p\mid a,b$ . If $k\ge 2$ , then this simply says that $-a\equiv -b\pmod{p}$ , so again $p\mid a,b$ . However, this violates the maximality of $k$ , which is a contradiction.

Therefore, we must have that $p=3,k=1$ , and WLOG $a=1$ . Therefore, $x=2$ and $y=3b-1$ . Thus, $2^2+(3b-1)=3(b+1)$ is a power of $3$ , so $b+1$ is a power of $3$ . Let $b=3^h-1$ . We also have that $(3b-1)^2+2$ is a power of $3$ , or that $9b^2-6b+3=3(3b^2-2b+1)$ is, so $3b^2-2b+1$ is a power of $3$ . Therefore,
$3(3^h-1)^2-2(3^h-1)+1=3^{2h+1}-2\cdot 3^{h+1}+3-2\cdot 3^h+2+1$ is a power of $3$ . If $h\ge 2$ , then taking mod $9$ is a contradiction, so we must have $h=1$ , so $b=2$ . Therefore, $x=2,y=5,p=3$ , which is the only other claimed solution. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

math_pi_rate

1218 posts

math_pi_rate

#14 h Dec 28, 2018, 7:21 PM • 7 Y

Y by AlastorMoody, Aryan-23, GammaBetaAlpha, pog, Zaro23, Adventure10, Mango247

ANSWER: The answers are $(p,x,y)=(2,x,2^z-x) \text{ or } (3,2,5) \text{ or } (3,5,2)$ . It's easy to see that this works.

SOLUTION: The case $p=2$ easily gives the first set of answers. So from now on assume that $p$ is an odd prime. Let $x^{p-1}+y=p^m \text{ and } x+y^{p-1}=p^n \text{ where } m,n \in \mathbb{N}$ It's easy to see that $x=y$ gives no solutions, cause then $x(x^{p-2}+1)$ is a power of $p$ , which is not possible for $p>2$ (as $x(x^{p-2}+1)$ must be an even integer). So WLOG assume that $x>y$ , which also gives $m>n$ . Our solution uses the following important claim-

CLAIM| The integers $x$ and $y$ are of the form $x=ap^{n-1}-1$ and $y=bp^{n-1}-1$ for some positive integers $a$ and $b$ such that $p \nmid a,b$ .

Proof of Claim Our proof to this claim is divided into three parts as given below.

We first show that $p \nmid x,y$ . Suppose, to the contrary, that $p \mid x$ . Then $p \mid y$ must also hold true. WLOG take $\nu_p(x) \geq \nu_p(y)$ . Then this means that $\nu_p(x^{p-1})>\nu_p(y)$ , and so we get that $\nu_p(x^{p-1}+y)=\nu_p(y)$ , or equivalently that $\nu_p(y)=m$ . However, $p^m=x^{p-1}+y>y \Rightarrow m>\nu_p(y)$ , and so we arrive at a contradiction. Thus, we must have that $p \nmid x,y$ .
$\text{ }$
Now we will show that $\nu_p(x+1)=\nu_p(y+1)>0$ . Note that, as $p \nmid x,y$ , so by FLT, we have $0 \equiv x^{p-1}+y \equiv 1+y \pmod{p}$ , and so $p \mid y+1$ . In a similar fashion, we get that $p \mid x+1$ . Again (for brevity) take and $\nu_p(y+1)=s$ . Then we wish to prove that $r=s$ . So let us assume to the contrary that $r \neq s$ . Now, by Lifting The Exponent Lemma, we have Similarly, we get that $\nu_p(y^{p-1}+y)=s$ . Then, using our assumption (i.e. $r \neq s$ ), we have
1. If $r=n$ , then $x+1=kp^n \Rightarrow x+1=k(x+y^{p-1})$ , which is not possible unless $y=k=1$ . But then $p^m=x^{p-1}+y=(p^n-1)^{p-1}+1 \Rightarrow 0 \equiv (p^n-1)^{p-1}+1 \equiv 2 \pmod{p} \rightarrow \text{CONTRADICTION}$
2. If $s=n$ , then $y+1=kp^n \Rightarrow y+1=k(x+y^{p-1})$ , which is not possible because $x>y$ .
Thus, we arrive at a contradiction in both the cases, and so we must have $r=s$ .
Take $\nu_p(x+1)=\nu_p(y+1)=e$ , i.e. $x+1=ap^e$ and $y+1=bp^e$ , where $\nu_p(a)=\nu_p(b)=0$ . We wish to show that $e=n-1$ . Note that $p^e \leq x+1<x+y^{p-1}=p^n$ , and so we must have $e<n$ . As $n<m$ , so we have $e<n<m$ . Then we get that $p^m=x^{p-1}+y=(ap^e-1)^{p-1}+(bp^e-1)=(1-a(p-1)p^e+ \dots +(ap^e)^{p-1})+(bp^e-1)=p^e(b-a(p-1)+wp^e)$ where $w$ is a positive integer. As $m>e>0$ , this gives that $a+b-ap+wp^e=p^{m-e} \Rightarrow p \mid a+b$ Now, notice that $p \nmid a-b$ , since otherwise $p \mid (a-b)+(a+b) \Rightarrow p \mid 2a$ , which is not possible as $\nu_p(2)=\nu_p(a)=0$ . So this means that $\nu_p(x-y)=\nu_p(p^e(a-b))=e$ . Then, by LTE, we have that $\nu_p(x^p-y^p)=\nu_p(x-y)+\nu_p(p)=e+1$ But, using our original equations, we get $x^p-y^p=x(x^{p-1}+y)-y(x+y^{p-1})=xp^m-yp^n=p^n(xp^{m-n}-y) \Rightarrow p^n \mid x^p-y^p$ $\Rightarrow n \mid \nu_p(x^p-y^p) \Rightarrow n \mid e+1 \Rightarrow n \leq e+1 \Rightarrow \text{As } e<n \text{, so we must have } e=n-1 \text{.}$

Summarizing our three steps, we get that $x=ap^{n-1}-1$ and $y=bp^{n-1}-1$ .

Return to the problem at hand. Note that our Lemma gives that $x,y \geq p^{n-1}-1$ . Also, $n \geq 2$ , since otherwise $p \nmid x+1,y+1$ . Now, with a bit of brute force calculations (I'll probably write them down later), one can easily show that this inequality is not true for $p \geq 5$ and $n \geq 3$ (For the diligent reader, try proving this by contradiction). So we get that $p=3$ and $n=2$ . This gives $x=3a-1$ and $y=3b-1$ . Thus, we have $x+y^2=3^2 \Rightarrow 9b^2-6b+3a=9 \Rightarrow b<2 \Rightarrow b=1,a=2 \Rightarrow x=5,y=2 \text{ } \blacksquare$

This post has been edited 2 times. Last edited by math_pi_rate, Dec 28, 2018, 7:25 PM

Z K Y

The post below has been deleted. Click to close.

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

Wizard_32

1566 posts

Wizard_32

#15 h Oct 28, 2019, 5:33 PM • 4 Y

Y by Aryan-23, pog, Adventure10, Funcshun840

Really nice, but surprisingly easy for a N5.

hajimbrak wrote:

Find all triples $(p, x, y)$ consisting of a prime number $p$ and two positive integers $x$ and $y$ such that $x^{p -1} + y$ and $x + y^ {p -1}$ are both powers of $p$ .

Proposed by Belgium

We claim that the only solutions are $(p,x,y)=(3,2,5),(3,5,2),(2,n,2^n-1),$ $(2,2^n-1,n).$ These clearly work. Now we prove these are the only ones. Assume that
$x^{p-1}+y=p^k, \qquad y^{p-1}+x=p^\ell$ where $x<y$ and $k<\ell.$ Treat with the case $p=2$ seperately.

Claim: We have $\nu_p(y-x) \ge k-1.$
Proof: Firstly, by Fermat $x \equiv -1 \equiv y \pmod{p}$ and so $p \nmid x,y$ and $p \mid y-x.$ We have
$x^{p-1}+y \mid y^{p}+xy-x(x^{p-1}+y)=y^p-x^p$ So by LTE $\nu_p(x-y)+1 \ge k.$

Suppose $k>2.$

Claim: We have $x \equiv -1 \pmod{p^2}.$
Proof: Since $k>2,$ hence $p^2 \mid x-y$ and hence
$0 \equiv p^k=x^{p-1}+y \equiv x^{p-1}+x \pmod{p^2}$ Thus $x^p \equiv -x^2 \pmod{p^2}.$ (notice that $\gcd(x,p)=1$ so this is all valid).

But also, by Euler we have $x^{p(p-1)} \equiv 1 \pmod{p^2}$ and thus
$\begin{align*} -x \equiv y^{p-1} \equiv \left( -x^{p-1} \right)^{p-1} \equiv x^{(p-1)^2} \pmod{p^2} \\ \implies x^{p^2-2p} \equiv -1 \overset{\text{Euler}}{\equiv} -x^{p^2-p} \implies x^{p} \equiv -1 \pmod{p^2} \end{align*}$ So, $-1 \equiv x^p \equiv -x^2$ and so $x^2 \equiv 1 \pmod{p^2}.$ Write $x=pm-1$ for some $m>0.$ Then $1 \equiv (pm-1)^2 \equiv 2pm+1$ and so $m \equiv 0 \pmod{p}.$ So $x \equiv -1 \pmod{p^2},$ as desired. $\square$

Now, we get
$x^{p-1}+y \mid p(x-y)+p(x^{p-1}+y)=px(x^{p-2}+1)$ Now, clearly $\gcd(x,y)=1$ else we must have $\gcd(x,y)=p^z$ but then $p^k=x^{p-1}+y=p^z(\alpha),$ where $\gcd(\alpha,p)=1$ and $\alpha>1,$ which is not possible. Hence, we get $x^{p-1}+y \mid p(x^{p-2}+1)$ and so $x^{p-2}(x-p)+y \le p.$ If $x>p \ge 3,$ then this gives $x^{p-2}<p.$ This is impossible since $p>x^{p-2} \ge x>p.$

Thus, $x \le p$ and so $x=p-1.$ Thus the second claim gives $p-1 \equiv -1 \pmod{p^2}$ which is impossible.

Thus, $k=2$ which gives $p=x^{p-1}+y > (p-1)^{p-1}$ and so $p=3.$ Then $x=3-1=2$ and so $y=5,$ and we get the solution, and we are done. $\blacksquare$

This post has been edited 1 time. Last edited by Wizard_32, Oct 28, 2019, 5:34 PM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1711 posts

awesomeming327.

#48 h May 25, 2023, 7:32 PM

Y by

If $p=2$ then clearly any $(x,y)$ whose sum is a power of two works. Suppose $p>2$ . If $p\mid x$ then let $\nu_p(x)$ . Clearly, $\nu_p\left(x^{p-1}\right)=\nu_p(y)$ and thus the same thing can be applied to $y$ , which gives a contradiction.

If $x^{p-1}+y=y^{p-1}+x$ then $x^{p-1}-x=y^{p-1}-y$ . However, this function is increasing on $(1,\infty)$ so $x=y$ , which gives $x^{p-1}+x$ is a power of $p$ . However, then $x$ is a power of $p$ , so $x=1$ . Absurd. The smaller one is divisible by the bigger.

Suppose $x<y$ , so $x^{p-1}+y\mid y^{p-1}+x$ . We have $y\equiv -x^{p-1}\pmod {x^{p-1}+y}$ so
$0\equiv \left(-x^{p-1}\right)^{p-1}+x\equiv x^{p^2-2p+1}+x\pmod x^{p-1}+y$ We have $\gcd(x^{p-1}+y,x)=1$ because the former is a power of $p$ . Note that $y^{p-1}\equiv 1\pmod p$ so $x\equiv -1\pmod p$ . Indeed, we can write $\nu_p(x^{p-1}+y)\le \nu_p(x^{p^2-2p}+1^{p^2-2p})=\nu_p(x+1)+1$ Since $x^{p-1}+y$ is actually a power of $p$ , $x^{p-1}+x\le x^{p-1}+y\le p(x+1)$ . Note that the difference, $x^{p-1}-(p-1)x-p$ , has a derivative that is nonnegative on $x\ge 1$ . Clearly, for $p\ge 5$ we have $2^{p-1}+2\le 3p$ . Thus, we must have $p=3$ , so $x^2+x\le 3(x+1)\implies x\le 3$ so $x=2$ . We have $4+y\mid 2 + y^2$ . Thus, $4+y\mid 18$ . $y$ is equal to one of the following: $2$ , $5$ , $14$ . Clearly, only only $5$ works. 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

#49 h Jun 9, 2023, 6:38 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.

popop614

271 posts

popop614

#50 h Jun 14, 2023, 4:05 AM

Y by

o wow didn't expect to solve this so soon after last post (how so oar)
$p=2$ is trivial and is left as an exercise to the reader.

The only other solution is $(x,y,p) = (2,5,3)$ up to switching $x$ and $y$ .

Henceforth assume that $p$ is an odd prime. WLOG assume $x^{p - 1} + y \mid y^{p - 1} + x$ . Then it is easy to obtain the relations

$x^{p - 1} + y \mid y^{p - 1} + x - (y^{p - 1} + x^{p - 1}y^{p-2})$ and
$x^{p - 1} + y \mid y^{p-1}x^{p-2} + x^{p-1} - x^{p-1} - y$
which imply that

$x^{p-1} + y \mid \gcd{(x,y)}((xy)^{p-1} - 1).$
Let $x=da$ , $y=db$ with $\gcd{(a,b)}=1$ . Then we obtain

$d^{p-1}a^{p-1} + b \mid (d^2ab)^{p-1} - 1.$ Now observe that $p$ must divide the left hand side, since we are dealing with positive integers and we divided out a power of $p$ . If $d > 1$ then $p \mid d$ , and it cannot divide right hand side, contradiction. Hence, we obtain
$x^{p-1} + y \mid (xy)^{p-1} - 1.$ With a bit of fiddling around, one obtains $x^{p-1} + y \mid y^p + 1,$ and with Fermat's Little Theorem it is clear that $y \equiv -1 \pmod{p}$ .
Moreover by dividing out the other way, one obtains $x^{p-1} + y \mid x^{p(p-2)} + 1.$ (multiply lefthandside by $(xy)^{p-1} \cdot y^{-1}$ and go from there)
Fermat's Little Theorem again says that $x^{-1} \equiv -1 \pmod{p}$ , hence $x \equiv -1 \pmod{p}$ . Now observe that we need
$\nu_p(x^{p(p-2)} + 1) \ge \nu_p(x^{p-1} + y).$ By LTE since $p \nmid x$ , we obtain
$\nu_p(x^{p(p-2)} + 1) = 1 + \nu_p(x + 1) \ge \nu_p(x^{p-1} + y).$ Let $x + 1 = kp^r$ . Then since $x^{p-1} + y$ is a perfect power of $p$ we require that
$(kp^r - 1)^{p-1} < p^{r + 1}$ for the $\nu_p$ inequality to hold at all ( $y$ is a positive integer). However this becomes trivially false for $k>1$ , and even considering $k=1$ limits the options greatly; $p>3$ clearly does not work. For $p=3$ , $r=1$ provides the only solution of $x=2$ , $y=5$ .

Z K Y

The post below has been deleted. Click to close.

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

trinhquockhanh

522 posts

trinhquockhanh

#51 h Jul 13, 2023, 2:52 PM

Y by

Somehow I missed the case when p is equal to 3 - 80% completed

This post has been edited 2 times. Last edited by trinhquockhanh, Jul 13, 2023, 3:12 PM

Z K Y

The post below has been deleted. Click to close.

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

andyxpandy99

365 posts

andyxpandy99

#52 h Aug 20, 2023, 2:11 AM

Y by

$p = 2$ is trivial since we just take $(n,2^k-n)$ for positive integers $n$ and $k$ .

The initial idea is to get a divisibility relation in the form of $c \mid f(n)$ i.e the RHS is just in one variable for $p > 2$ .

Now assume $p > 2$ . WLOG $x \geq y$ , which is the same thing as saying $x^{p-1}+y \geq x+y^{p-1}$ . It follows that $y^{p-1}+x \mid x^{p-1}+y$ which is the same thing as saying $x^{p-1}+y \equiv 0 \pmod {y^{p-1}+x}$ However, in lieu of the idea we can also rewrite this as $(-y^{p-1})^{p-1}+y \equiv 0 \pmod{y^{p-1}+x}$ and simplifying yields $y^{p-1}+x \mid y(y^{p(p-2)}+1)$
Now note that clearly $p \nmid x,y$ . FLT gives us $x^{p-1} + y \equiv 1+y \equiv 0 \pmod p$ which means $y \equiv -1 \pmod p$ . Similarly $x \equiv -1 \pmod p$ . This means that LTE gives us $v_p(y(y^{p(p-2)}+1)) = v_p(y^{p(p-2)}+1) = v_p(y+1)+1$ It follows that $v_p(y^{p-1}+x) \leq v_p(y+1)+1$ . Now the key step is that since $y^{p-1}+x$ is actually a power of $p$ , we can say that $y^{p-1}+x \mid p(y+1)$ However, this means that $y^{p-1} + x \leq p(y+1)$ but $y \equiv -1 \pmod p \geq p-1$ so we must have $p=3$ and $y=p-1 = 2$ . Plugging this back into the equation and working out some details that I will omit yields that $x=5$ so the only triple is $(3,5,2)$ and we're done.

remark - usually we simply add and subtract stuff from RHS to simplify a divisibility relation but in this case we had to use $v_p$ at the end. I guess I should've known $v_p$ would come up at some point given the "power of prime" in the problem statement haha

This post has been edited 3 times. Last edited by andyxpandy99, Aug 20, 2023, 2:19 AM

Z K Y

The post below has been deleted. Click to close.

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

huashiliao2020

1292 posts

huashiliao2020

#53 h Aug 23, 2023, 2:22 AM

Y by

Notice p=2 we take (x,y)=(k,2^n-k), so henceforth assume p>2; it's pretty easy to prove x,y are relatively prime to p. (For example, $\nu_p(x) \ge \nu_p(y)\implies\nu_p(y)\ge p-1$ from $x^{p-1}+y=p^{x_0},x+y^{p-1}=p^{y_0},x_0,y_0\ge p-1$ . Now observe that $0\equiv y^{p-1}+x\equiv x\pmod {p^{y_0}}$ , which is infinite "inscent" in the sense that x is now divisible by p-1th power, which henceforth increases the $\nu_p$ in y from the first equation.)

If both of them are relatively prime, then mod p we find $1+y\equiv 0\equiv 1+x\implies x\equiv y\implies x(x^{p-2}+1)\equiv 0\pmod p\implies ord_{\{x,y\}}|\text{gcd}(2p-4,2p-2)=2\implies \{x,y\}\equiv\{-1,1\}\pmod p.$ Checking, none of these permutations work mod p, unless p=3; this is the most bashy case yet. Prepare yourself!

(x,y)=(2,5) works, and we prove it's the only one. Indeed, it's obvious taking mod 3 that x,y are 2 mod 3; mod 9, $x^2$ or $y^2$ can be 1,4,7 mod 9, so $(x,y)\equiv(2,5)\pmod 9$ is the only pair that works. Then, it's obvious if (at least) one of the expressions in the original problem=9 or 27, (2,5) is only solution. If one of them is divisible by 81, $(x^2,y^2)\equiv(4,25)\pmod 81$ ; it's obvious that this doesn't work because we would need $(x,y)\equiv(56,77)$ , but plugging this in mod 81 doesn't actually work.

In conclusion, the only solutions are $(p,x,y)=(2,k,2^n-k),(3,2,5)$ with switching x,y allowed.

This post has been edited 4 times. Last edited by huashiliao2020, Sep 7, 2023, 5:52 AM

Z K Y

The post below has been deleted. Click to close.

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

thdnder

196 posts

thdnder

#54 h Oct 8, 2023, 3:51 PM

Y by

Isn't it easy for N5?
Answer: $(x, y, p) = (x, 2^k - x, 2), (2, 5, 3)$ .

If $p = 2$ , then $x + y$ and $y + x$ are power of 2, so $y = 2^k - x$ for some $k$ . Now assume $p \ge 3$ .

Note that $\gcd(p, x) = \gcd(p, y) = 1$ , so $x^{p-1} + y \neq x + y^{p-1}$ . Let $p^a = x^{p-1} + y$ and $p^b = x + y^{p-1}$ .By Fermat's little theorem, we have $x + 1 \equiv y + 1 \equiv 0 (p)$ . WLOG assume $a < b$ . Then since $p^a \mid p^b$ , so $x^{p-1} + y \mid x + y^{p-1}$ ,so $p^a \mid x^{p^2 - 2p} + 1$ , so by lifting the exponent we have $\nu_p(x + 1) + \nu_p(p^2 - 2p) \ge a$ , so $\nu_p(x + 1) \ge a - 1$ . So by lifting the exponent we have $\nu_p(x^{p-1} - 1) = a - 1$ , therefore $\nu_p(y + 1) = a - 1$ . So $p^a = x^{p-1} + y \ge (p^{a-1} - 1)^{p-1} + (p^{a-1} - 1)$ . Assume $a \ge 3$ . Then $p^a > (p^{a-1} - 1)^{p-1} \ge (p^{a-1} - 1)^2 > (p^{a-1} - 1)(p + 1) = p^a + p^{a-1} - p - 1 > p^a$ , a contradiction.

Note that $a \neq 1$ , since $x^{p-1} + y > p$ . So $a = 2$ . Then we have $(p-1)^{p-1} + (p-1) \le p^2$ , so $(p-1)^{p-1} < p^2 - 1$ . Assume $p \ge 5$ . Then $(p-1)^3 \le (p-1)^{p-2} < p + 1$ , a contradiction.

So $p = 3$ and $a = 2$ . It follows that $x = 2$ and $y = 5$ , and it's not hard to check that $(x, y, p) = (2, 5, 3)$ is answer. This completes proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#55 h Dec 18, 2023, 7:27 PM

Y by

The only answers are $(x, 2^k-x)$ when $p=2$ and $(2, 5)$ when $p=3$ .

Note that when $p=2$ the problem is tautological. Hence assume $p \geq 3$ . Note that if $p \mid x$ and $p \mid y$ , then we have an obvious contradiction when $\nu_p(x) \geq \nu_p(y)$ . It follows that $x, y \equiv -1 \pmod p$ .

Notice that when $x=y$ , $x(x^{p-2} + 1)$ must be a power of $p$ , which is impossible as $p \nmid x$ . Thus assume $y > x$ and set $\nu_p(x+1) = k$ . It follows that $x^{p-1} + y \mid x^{(p-1)^2}-y^{p-1} + y^{p-1} + x = x(x^{(p-1)^2-1}+1).$ However, by LTE $\nu_p(x^{(p-1)^2-1}+1) = \nu_p(x+1) + 1 = k+1.$ On the other hand, because $x^{p-1}+y$ is a power of $p$ , it follows that $(p^k-1)^{p-1} + y \leq x^{p-1} + y \leq p^{k+1}.$ The only solutions to this are found when $p=3$ , which gives the desired pair $(2, 5)$ .

Z K Y

The post below has been deleted. Click to close.

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

L13832

265 posts

L13832

#56 h Sep 24, 2024, 12:31 PM • 1 Y

Y by radian_51

Nice Question! took some time to solve it though
If $p=2$ then $x+y=2^k$ for some $k\in \mathbb{N}$ . So the triple would be $\boxed{(2,l,2^k-l)}$ .
For $p\geq 3$ let $x^{p-1}+y=p^a$ and $y^{p-1}+x=p^b$ .
If $p\mid x\implies p\mid y$ so let $\nu_p(x)=r$ and $\nu_{p}(y)=s$ . From this we get $(p-1)s=r$ and $(p-1)r=s$ which is obviously a contradiction. Now by FLT we get $x,y\equiv -1 \pmod{p}$ .
WLOG assume $x>y$ , then we have $y^{p-1}+x \mid x^{p-1} +y \implies y^{p-1}+x \mid \left(-y^{p-1}\right)^{p-1}+y\implies y^{p-1}+x \mid y^{p(p-2)}+1$ By applying LTE we have $v_p(y^{p-1}+y)<\nu_{p}(y^{p-1}+x)\leq \underbrace{\nu_{p}(p(p-2))}_{1}+\nu_{p}(y+1)$ , so we have $y^{p-1}+x \mid p(y+1)\implies y^{p-1}+y<p(y+1)$ , because $y\equiv -1 \pmod{p}$ we have $y\geq p-1$ , so we get $p=3,5$ so the triples are $\boxed{(3,5,2), (3,2,5)}$

This post has been edited 1 time. Last edited by L13832, Sep 24, 2024, 12:32 PM

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1729 posts

OronSH

#57 h Feb 26, 2025, 8:14 PM

Y by

We claim $(2,n,2^t-n),(3,2,5),(3,5,2)$ is the answer.

If $p=2$ it is clear. If $p>2$ then $p\mid x\implies x^{p-1}+y>p^{p-1}\implies p^{p-1}\mid y\implies x+y^{p-1}>p^{(p-1)^2}\implies p^{(p-1)^2}\mid x$ and so on, contradiction. Thus by FLT it is clear $x,y\equiv -1\pmod p$ .

WLOG $x<y$ . Then $x^{p-1}+y\mid x+y^{p-1}$ but $x^{p-1}+y\mid x^{(p-1)^2}-y^{p-1}$ so $x^{p-1}+y\mid x^{(p-1)^2}+x\implies x^{p-1}+y\mid x^{p^2-2p}+1$ . By LTE $\nu_p(xp+p)=\nu_p(x+1)+1=\nu_p(x^{p^2-2p}+1)\ge\nu_p(x^{p-1}+y)$ implying $x^{p-1}+y\mid xp+p$ .

For $p=3$ we have $x^2+y\mid 3p+3\implies x^2-3x-3\le 0\implies x=2$ which gives $(x,y)=(2,5)$ which works. For $p\ge 5$ we have $x^{p-1}+y> x^3\ge x(p-1)^2=x(p-1)(p-2)+x(p-1)\ge xp+p$ so there are no solutions as desired.

Z K Y

The post below has been deleted. Click to close.

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

InterLoop

280 posts

InterLoop

#58 h Apr 15, 2025, 12:29 AM

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.

SimplisticFormulas

102 posts

SimplisticFormulas

#59 h Apr 15, 2025, 5:20 PM

Y by

solution
remark

This post has been edited 1 time. Last edited by SimplisticFormulas, Apr 15, 2025, 5:23 PM

Z K Y

The post below has been deleted. Click to close.

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

Jupiterballs

42 posts

Jupiterballs

#60 h Apr 23, 2025, 11:43 AM

Y by

Took a day and a half (not continuously)
Also not as smart as @above so took this long :omighty:

Attachments:

ISL 2014 N5.pdf (31kb)

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

607 posts

Ilikeminecraft

#61 h Apr 25, 2025, 4:18 PM

Y by

If $p = 2,$ we clearly have that the solutions are $(p, (x, y)) = (2, (x, 2^k - x))$ for some $x, k \in \mathbb N_0.$ Assume $p$ is an odd prime.

First, note that neither can be 1. Hence, by taking modulo $p,$ we see that $x\equiv y \equiv -1\pmod p.$ Hence, we also have that $(x, y) = 1.$ Assume that $y \geq x,$ we have that $x^{p - 1} + y \mid (-x^{p - 1})^{p - 1} + x = x^{(p - 1)^2 - 1} + 1$ Since $(p-1)^2- 1$ is odd, we can use LTE. We have that $\nu_p(x^{p-1} + y) \leq 1 + \nu_p(x + 1).$ Hence, $x^{p - 1} + y\leq p\cdot(x + 1).$ By $y\geq x,$ we have that $x^{p - 1} + x \leq p \cdot(x + 1).$ Combining this with the fact that $x\equiv -1\pmod p,$ the only solution is when $x = 2, p = 3.$ Hence, $4 + y \mid 9.$ Clearly, $y = 5.$ Thus, the only other solution is $(3, (2, 5))$ and $(3, (5, 2)).$

Z K Y

The post below has been deleted. Click to close.

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

sansgankrsngupta

137 posts

sansgankrsngupta

#62 h Apr 25, 2025, 5:10 PM

Y by

OG! If $p=2$ then $(p,x,y)= (2, k, 2^m-k )$ work where $m, k \geq 1 \in \mathbb{Z}$
If $p>2$ then,
$\blacksquare$ ; $p \nmid x,y$ since if $p \mid x \implies p \mid y$ then WLOG $v_p(x) \geq v_p(y)$ gives the immidiate contradiction: $v_p(x^{p-1})> v_p(y)$

$\blacksquare$ $gcd(x,y) | x^p-1+y = p^k$ since $p \nmid x, y$ ; $gcd(x,y)= 1$
$\blacksquare$ $x+1 \equiv x+y^{p-1} \equiv 0 \pmod{p}$ . Similarly, we get $x,y \equiv -1 \pmod{p}$ .

Now, WLOG, $x \geq y$ then we have that $x^{p-1}+y \geq x+y^{p-1}$ ; since both are powers of $p$ ; $x+y^{p-1} | y+ x^{p-1} \iff x+y^{p-1}| y+y^{(p-1)^2} \iff x+y^{p-1}| y^{(p-1)^2-1}+1^{(p-1)^2-1}$ ;
then using LTE, $v_p(x+y^{p-1}) \leq v_p((p-1)^2-1)+v_p(y+1)= 1+v_p(y+1) \implies$ $y^{p-1}< x+y^{p-1} \leq p(y+1) \iff \frac{y^{p-1}}{(y+1)}< p$
but since $y \equiv -1 \pmod{p}, y>0$ we have that $y \geq p-1$ which clearly is a contradiction due to size issues unless $p=3$ .
For $p=3$ , if $y \geq 2p-1$ we shall again have a contradiction due to size issues, hence we must have that $y=p-1=2$
since, $y \equiv -1 \pmod{p}$ . Then $x^2+2, 4+x$ both are powers of 3.
Since $4+x| x^2+2$ ( $x \geq y$ and both are powers of 3.) This means $4+x|18 \iff x=2, 5, 14$ and only $x=5$ works which gives
$(p,x,y)=(3,5,2)$ .

Hence the only solutions are: $(p,x,y)= (2, k, 2^m-k ); (3,5,2)$ where $m, k \geq 1 \in \mathbb{Z}$

This post has been edited 1 time. Last edited by sansgankrsngupta, Apr 25, 2025, 5:13 PM
Reason: -

Z K Y