Difference between revisions of "2000 OIM Problems/Problem 3"

Latest revision as of 18:49, 29 April 2025

Problem

Find all solutions to the equation

$(x + 1)^y - x^z = 1$

for $x, y, z$ integers greater than 1.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Solution. We split this problem into cases.

Case 1. $y$ is odd. Notice that if we take mod $x+1$ , we get: $1-(-1)^z\equiv1\pmod{x+1}$ $\Rightarrow(-1)^z\equiv-1\pmod{x+1}$ Since $x\ge2$ , this is clearly only possible if $z$ is odd.

Case 1.1. $x$ is odd. Then we can rearrange: $(x+1)^y-1^y=x^z$ Let $p$ be some odd prime such that $p|x$ ; there will always exist such a prime because $x\ge2$ . Then, we can lift the exponent: $v_{p}(x+1-1)+v_{p_0}(y)=v_{p}(x^z)$ $\iff v_{p}(x)+v_{p_0}(y)=zv_{p}(x)$ $\iff v_{p}(y)=(z-1)v_{p}(x)$ where $v_{p}(x)$ is understood to represent the $p$ -adic valuation of $x$ . Clearly this holds for all primes $p$ such that $p|x$ , so we can let $y=x^{z-1}m$ for a positive integer $m$ such that $\gcd(x,m)=1$ from the above. Therefore, substituting: $\Rightarrow(x+1)^{x^{z-1}m}-1=x^z$ Lemma. For all positive integers $z\ge3$ , we have $x^{z-1}m>z$ .

Proof. Clearly, proving the case for $m=1$ will prove the other cases since $x^{z-1}m\ge x^{z-1}$ ; thus, we need to prove: $x^{z-1}>z$ We use induction. First, for $z=3$ , we have: $x^2>3$ which is clearly true since $x\ge2$ . Next, for our inductive step, assume that the claim holds for some positive integer $n=k$ ; in other words, $x^{k-1}>k$ $\Rightarrow x^k>xk>2x>x+x>x+1$ which proves the claim for $n=k+1$ , thus completing the inductive step and proving the statement. $\blacksquare$

We return to: $(x+1)^{x^{z-1}m}-1=x^z$ which we will prove has no solutions for $z\ge3$ . First, it is clear that $(x+1)^{x^{z-1}m}>(x+1)^z$ from our claim above. Since both are integers, it follows that $(x+1)^{x^{z-1}m}\ge(x+1)^z+1$ It is also clear that $(x+1)^z>x^z$ since $x$ is greater than $1$ . Both are integers, so $(x+1)^z\ge x^z+1$ Combining the statements, we find that $(x+1)^{x^{z-1}m}\ge (x+1)^z+1\ge x^z+2$ $\Rightarrow (x+1)^{x^{z-1}m}-1\ge x^z+1>x^z$ $\Rightarrow (x+1)^{x^{z-1}m}-1>x^z$ hence there are no solutions for $z\ge3$ .

We know that $z$ must be odd, so $z\ne2$ , and thus there are no solutions in this case.

Case 1.2. $x$ is even. We show that there are no solutions in this case. Assume for the sake of contradiction that there exists a solution $x$ such that $x=2^k x_0$ , where $x_0$ is odd and $k$ is a positive integer. In other words, $v_2(x)=k$ . Then we can substitute: $(2^kx_0+1)^y-(2^kx_0)^z=1$ Let $y=2a+1$ since $y$ is odd. Then, $\Rightarrow (2^kx_0+1)^{2a+1}-(2^kx_0)^z=1$ $\Rightarrow (2^kx_0+1)\cdot((2^kx_0+1)^2)^a-2^{kz}x_0^z=1$ $\Rightarrow (2^kx_0+1)\cdot(2^{2k}x_0^2+2^{k+1}x_0+1)-2^{kz}x_0^z=1$ Take the equation mod $2^{k+1}$ : $\Rightarrow (2^kx_0+1)\cdot(0+0x_0+1)-0x_0^z\equiv1\pmod{2^{k+1}}$ $\Rightarrow 2^kx_0+1\equiv1\pmod{2^{k+1}}$ $\Rightarrow 2^kx_0\equiv0\pmod{2^{k+1}}$ implying that $x_0$ is even, a contradiction. Thus there exist no solutions in this case.

Case 2. $y$ is even. Then let $y=2b$ , where $b$ is a positive integer. Rearranging and using difference of squares: $((x+1)^b+1)((x+1)^b-1)=x^z$

Case 2.1. $x$ is odd. Then both $(x+1)^b+1$ and $(x+1)^b-1$ are odd. However, by the Euclidean Algorithm, they must be relatively prime.

Let $p|x$ be a given odd prime ( $x$ is odd so $p\ne2$ ). Then, we have: $(x+1)^b+1\equiv 1^b+1\equiv2\pmod{p}$ Thus $p\nmid (x+1)^b+1$ . However, this holds for all such $p$ , and since the factors of $(x+1)^b+1$ must also be factors of $x^z$ due to the product, $(x+1)^b+1$ cannot be divisible by any of the factors of $x^z$ and thus any odd prime, so we must have $(x+1)^b+1=1$ . As a result, $x=-1$ , which is invalid, so there are no solutions in this case.

Case 2.2. $x$ is even. Then let $x=2^kx_0$ , where $k$ is a positive integer and $x_0$ is odd; in other words, $v_2(x)=k$ . We substitute: $(2^kx_0+1)^y-1^y=2^{kz}x_0^z$ Next, we lift the exponent with $p=2$ : $\Rightarrow v_2(2^kx_0)+v_2(2^kx_0+2)+v_2(y)-1=v_2(2^{kz}x_0^z)=kz$ $\Rightarrow k+v_2(2^kx_0+2)+v_2(y)-1=kz$ First consider $k\ge 2$ . Then $v_2(2^kx_0+2)=v_2(2(2^{k-1}x_0+1))=1$ since $2^{k-1}x_0+1$ is odd, so $\Rightarrow k+1+v_2(y)-1=kz$ $\Rightarrow v_2(y)=k(z-1)$ $\Rightarrow v_2(y)=(z-1)\cdot v_2(x)$ Similarly, we can lift the exponent for any odd prime $p$ such that $p|x$ : $v_p(x)+v_p(y)=v_p(x^z)=z\cdot v_p(x)$ $\Rightarrow v_p(y)=(z-1)\cdot v_p(x)$ From the above, we have $v_p(y)=(z-1)\cdot v_p(x)$ for all primes $p$ such that $p|x$ ; thus we can write $y=x^{z-1}n$ for some positive integer $n$ such that $\gcd(x,n)=1$ . Substituting: $\Rightarrow(x+1)^{x^{z-1}n}-1=x^z$ But we showed that this is true for $z\ge3$ in Case 1.1. Additionally, we know that $z\ne2$ once again because if we return to $(x+1)^y-x^z=1$ $\Rightarrow -(-1)^z\equiv1\pmod{x+1}$ $\Rightarrow (-1)^z\equiv-1\pmod{x+1}$ which is clearly only true if $z$ is odd; thus $z\ne2$ and we are done for $k\ge2$ .

Finally, we consider $k=1$ . Then the equation becomes $(2x_0+1)^y-1=2^zx_0^z$ $\Rightarrow ((2x_0+1)^b+1)((2x_0+1)^b-1)=2^zx_0^z$ for odd $x_0$ . Again, let $p$ be some odd prime such that $p|x_0$ . Then, $(2x_0+1)^b+1\equiv 1^b+1\equiv2\pmod{p}$ Thus, since $(2x_0+1)^b+1$ can only be divisible by factors of $2^zx_0^z$ (and thus cannot be divisible by any odd primes), we must have $(2x_0+1)^b+1=2^t$ for some nonnegative integer $t$ . Furthermore, notice that $2^t=(2x_0+1)^b+1\ge (2+1)^b+1=3^b+1\ge 4$ so $t\ge2$ . This implies that $(2x_0+1)^b-1=2^t-2$ , so $\Rightarrow 2^t(2^t-2)=2^zx_0^z$ $\Rightarrow 2^{t-1}-1=2^{z-t-1}x_0^z$ The left-hand side is odd, so $z-t-1=0$ . Therefore, $t=z-1$ , implying: $\Rightarrow 2^{z-2}-1=x_0^z$ But clearly, $2^{z-2}-1<2^z$ and since $x_0$ is a positive integer, this forces $x_0=1$ , so $\Rightarrow 2^{z-2}-1=1$ $\Rightarrow 2^{z-2}=2$ $\Rightarrow z=3$ Additionally, we have $x=2^kx_0=2\cdot1=2$ . Therefore, plugging back in to our original equation: $(2+1)^y-2^3=1$ $\Rightarrow 3^y=9$ $\Rightarrow y=2$ Thus, our only solution is $(x,y,z)=\boxed{(2,2,3)}$ , which clearly works upon substitution. $\blacksquare$

Remark. The solution follows trivially from Catalan's conjecture, which was proven in 2002. However, the competition was held before the proof of the conjecture, so we assume that we are unable to use the conjecture.

~ eevee9406

@@ Line 9: / Line 9: @@
 == Solution ==
-{{solution}}
+<b>Solution.</b> We split this problem into cases.
+<b>Case 1. <math>y</math> is odd.</b> Notice that if we take mod <math>x+1</math>, we get:
+<cmath>1-(-1)^z\equiv1\pmod{x+1}</cmath>
+<cmath>\Rightarrow(-1)^z\equiv-1\pmod{x+1}</cmath>
+Since <math>x\ge2</math>, this is clearly only possible if <math>z</math> is odd.
+<b>Case 1.1. <math>x</math> is odd.</b> Then we can rearrange:
+<cmath>(x+1)^y-1^y=x^z</cmath>
+Let <math>p</math> be some odd prime such that <math>p|x</math>; there will always exist such a prime because <math>x\ge2</math>. Then, we can lift the exponent:
+<cmath>v_{p}(x+1-1)+v_{p_0}(y)=v_{p}(x^z)</cmath>
+<cmath>\iff v_{p}(x)+v_{p_0}(y)=zv_{p}(x)</cmath>
+<cmath>\iff v_{p}(y)=(z-1)v_{p}(x)</cmath>
+where <math>v_{p}(x)</math> is understood to represent the <math>p</math>-adic valuation of <math>x</math>. Clearly this holds for all primes <math>p</math> such that <math>p|x</math>, so we can let <math>y=x^{z-1}m</math> for a positive integer <math>m</math> such that <math>\gcd(x,m)=1</math> from the above. Therefore, substituting:
+<cmath>\Rightarrow(x+1)^{x^{z-1}m}-1=x^z</cmath>
+<b>Lemma.</b> For all positive integers <math>z\ge3</math>, we have <math>x^{z-1}m>z</math>.
+<i>Proof.</i> Clearly, proving the case for <math>m=1</math> will prove the other cases since <math>x^{z-1}m\ge x^{z-1}</math>; thus, we need to prove:
+<cmath>x^{z-1}>z</cmath>
+We use induction. First, for <math>z=3</math>, we have:
+<cmath>x^2>3</cmath>
+which is clearly true since <math>x\ge2</math>. Next, for our inductive step, assume that the claim holds for some positive integer <math>n=k</math>; in other words,
+<cmath>x^{k-1}>k</cmath>
+<cmath>\Rightarrow x^k>xk>2x>x+x>x+1</cmath>
+which proves the claim for <math>n=k+1</math>, thus completing the inductive step and proving the statement. <math>\blacksquare</math>
+We return to:
+<cmath>(x+1)^{x^{z-1}m}-1=x^z</cmath>
+which we will prove has no solutions for <math>z\ge3</math>. First, it is clear that
+<cmath>(x+1)^{x^{z-1}m}>(x+1)^z</cmath>
+from our claim above. Since both are integers, it follows that
+<cmath>(x+1)^{x^{z-1}m}\ge(x+1)^z+1</cmath>
+It is also clear that
+<cmath>(x+1)^z>x^z</cmath>
+since <math>x</math> is greater than <math>1</math>. Both are integers, so
+<cmath>(x+1)^z\ge x^z+1</cmath>
+Combining the statements, we find that
+<cmath>(x+1)^{x^{z-1}m}\ge (x+1)^z+1\ge x^z+2</cmath>
+<cmath>\Rightarrow (x+1)^{x^{z-1}m}-1\ge x^z+1>x^z</cmath>
+<cmath>\Rightarrow (x+1)^{x^{z-1}m}-1>x^z</cmath>
+hence there are no solutions for <math>z\ge3</math>.
+We know that <math>z</math> must be odd, so <math>z\ne2</math>, and thus there are no solutions in this case.
+<b>Case 1.2. <math>x</math> is even.</b> We show that there are no solutions in this case. Assume for the sake of contradiction that there exists a solution <math>x</math> such that <math>x=2^k x_0</math>, where <math>x_0</math> is odd and <math>k</math> is a positive integer. In other words, <math>v_2(x)=k</math>. Then we can substitute:
+<cmath>(2^kx_0+1)^y-(2^kx_0)^z=1</cmath>
+Let <math>y=2a+1</math> since <math>y</math> is odd. Then,
+<cmath>\Rightarrow (2^kx_0+1)^{2a+1}-(2^kx_0)^z=1</cmath>
+<cmath>\Rightarrow (2^kx_0+1)\cdot((2^kx_0+1)^2)^a-2^{kz}x_0^z=1</cmath>
+<cmath>\Rightarrow (2^kx_0+1)\cdot(2^{2k}x_0^2+2^{k+1}x_0+1)-2^{kz}x_0^z=1</cmath>
+Take the equation mod <math>2^{k+1}</math>:
+<cmath>\Rightarrow (2^kx_0+1)\cdot(0+0x_0+1)-0x_0^z\equiv1\pmod{2^{k+1}}</cmath>
+<cmath>\Rightarrow 2^kx_0+1\equiv1\pmod{2^{k+1}}</cmath>
+<cmath>\Rightarrow 2^kx_0\equiv0\pmod{2^{k+1}}</cmath>
+implying that <math>x_0</math> is even, a contradiction. Thus there exist no solutions in this case.
+<b>Case 2. <math>y</math> is even.</b> Then let <math>y=2b</math>, where <math>b</math> is a positive integer. Rearranging and using difference of squares:
+<cmath>((x+1)^b+1)((x+1)^b-1)=x^z</cmath>
+<b>Case 2.1. <math>x</math> is odd.</b> Then both <math>(x+1)^b+1</math> and <math>(x+1)^b-1</math> are odd. However, by the Euclidean Algorithm, they must be relatively prime.
+Let <math>p|x</math> be a given odd prime (<math>x</math> is odd so <math>p\ne2</math>). Then, we have:
+<cmath>(x+1)^b+1\equiv 1^b+1\equiv2\pmod{p}</cmath>
+Thus <math>p\nmid (x+1)^b+1</math>. However, this holds for all such <math>p</math>, and since the factors of <math>(x+1)^b+1</math> must also be factors of <math>x^z</math> due to the product, <math>(x+1)^b+1</math> cannot be divisible by any of the factors of <math>x^z</math> and thus any odd prime, so we must have <math>(x+1)^b+1=1</math>. As a result, <math>x=-1</math>, which is invalid, so there are no solutions in this case.
+<b>Case 2.2. <math>x</math> is even.</b> Then let <math>x=2^kx_0</math>, where <math>k</math> is a positive integer and <math>x_0</math> is odd; in other words, <math>v_2(x)=k</math>. We substitute:
+<cmath>(2^kx_0+1)^y-1^y=2^{kz}x_0^z</cmath>
+Next, we lift the exponent with <math>p=2</math>:
+<cmath>\Rightarrow v_2(2^kx_0)+v_2(2^kx_0+2)+v_2(y)-1=v_2(2^{kz}x_0^z)=kz</cmath>
+<cmath>\Rightarrow k+v_2(2^kx_0+2)+v_2(y)-1=kz</cmath>
+First consider <math>k\ge 2</math>. Then <math>v_2(2^kx_0+2)=v_2(2(2^{k-1}x_0+1))=1</math> since <math>2^{k-1}x_0+1</math> is odd, so
+<cmath>\Rightarrow k+1+v_2(y)-1=kz</cmath>
+<cmath>\Rightarrow v_2(y)=k(z-1)</cmath>
+<cmath>\Rightarrow v_2(y)=(z-1)\cdot v_2(x)</cmath>
+Similarly, we can lift the exponent for any odd prime <math>p</math> such that <math>p|x</math>:
+<cmath>v_p(x)+v_p(y)=v_p(x^z)=z\cdot v_p(x)</cmath>
+<cmath>\Rightarrow v_p(y)=(z-1)\cdot v_p(x)</cmath>
+From the above, we have <math>v_p(y)=(z-1)\cdot v_p(x)</math> for all primes <math>p</math> such that <math>p|x</math>; thus we can write <math>y=x^{z-1}n</math> for some positive integer <math>n</math> such that <math>\gcd(x,n)=1</math>. Substituting:
+<cmath>\Rightarrow(x+1)^{x^{z-1}n}-1=x^z</cmath>
+But we showed that this is true for <math>z\ge3</math> in Case 1.1. Additionally, we know that <math>z\ne2</math> once again because if we return to
+<cmath>(x+1)^y-x^z=1</cmath>
+<cmath>\Rightarrow -(-1)^z\equiv1\pmod{x+1}</cmath>
+<cmath>\Rightarrow (-1)^z\equiv-1\pmod{x+1}</cmath>
+which is clearly only true if <math>z</math> is odd; thus <math>z\ne2</math> and we are done for <math>k\ge2</math>.
+Finally, we consider <math>k=1</math>. Then the equation becomes
+<cmath>(2x_0+1)^y-1=2^zx_0^z</cmath>
+<cmath>\Rightarrow ((2x_0+1)^b+1)((2x_0+1)^b-1)=2^zx_0^z</cmath>
+for odd <math>x_0</math>. Again, let <math>p</math> be some odd prime such that <math>p|x_0</math>. Then,
+<cmath>(2x_0+1)^b+1\equiv 1^b+1\equiv2\pmod{p}</cmath>
+Thus, since <math>(2x_0+1)^b+1</math> can only be divisible by factors of <math>2^zx_0^z</math> (and thus cannot be divisible by any odd primes), we must have <math>(2x_0+1)^b+1=2^t</math> for some nonnegative integer <math>t</math>. Furthermore, notice that
+<cmath>2^t=(2x_0+1)^b+1\ge (2+1)^b+1=3^b+1\ge 4</cmath>
+so <math>t\ge2</math>. This implies that <math>(2x_0+1)^b-1=2^t-2</math>, so
+<cmath>\Rightarrow 2^t(2^t-2)=2^zx_0^z</cmath>
+<cmath>\Rightarrow 2^{t-1}-1=2^{z-t-1}x_0^z</cmath>
+The left-hand side is odd, so <math>z-t-1=0</math>. Therefore, <math>t=z-1</math>, implying:
+<cmath>\Rightarrow 2^{z-2}-1=x_0^z</cmath>
+But clearly,
+<cmath>2^{z-2}-1<2^z</cmath>
+and since <math>x_0</math> is a positive integer, this forces <math>x_0=1</math>, so
+<cmath>\Rightarrow 2^{z-2}-1=1</cmath>
+<cmath>\Rightarrow 2^{z-2}=2</cmath>
+<cmath>\Rightarrow z=3</cmath>
+Additionally, we have <math>x=2^kx_0=2\cdot1=2</math>. Therefore, plugging back in to our original equation:
+<cmath>(2+1)^y-2^3=1</cmath>
+<cmath>\Rightarrow 3^y=9</cmath>
+<cmath>\Rightarrow y=2</cmath>
+Thus, our only solution is <math>(x,y,z)=\boxed{(2,2,3)}</math>, which clearly works upon substitution. <math>\blacksquare</math>
+<i>Remark.</i> The solution follows trivially from Catalan's conjecture, which was proven in 2002. However, the competition was held before the proof of the conjecture, so we assume that we are unable to use the conjecture.
+~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
 == See also ==
 https://www.oma.org.ar/enunciados/ibe15.htm

Page

Toolbox

Search

Difference between revisions of "2000 OIM Problems/Problem 3"

Latest revision as of 18:49, 29 April 2025

Problem

Solution

See also