Determine all pairs of natural numbers $(x; n)$ that satisfy the equation \[x^{3}+2x+1 = 2^{n}.\]
Problem
Source: Serbian Mathematical Olympiad 2007
Tags: modular arithmetic, inequalities, quadratics, number theory, greatest common divisor, number theory proposed
10.06.2007 23:55
Correct me if I'm wrong. There is one simple solution $(1,2)$ with $x>1$ $2^{n}=x^{(nlog_{x}2)}$ but the esponent is irrational because $x$ must be odd.
11.06.2007 08:58
Vinxenz wrote: Correct me if I'm wrong. There is one simple solution $(1,2)$ with $x>1$ $2^{n}=x^{(nlog_{x}2)}$ but the esponent is irrational because $x$ must be odd. For all $x>1$ we have that equality
12.06.2007 17:30
Maybe this helps: n=1 x^3+2x = 1 x(x^2+2)=1 no solution then n>=2 take mod 2 on the equation then x odd take mod 4 then x=4 k + 1 k>=0 thus m=n-2 (m>=0) 16 k^3 + 12 k^2 + 3 k + 1/4 + 2 k + 2/4 + 1/4 = 2^m 16 k^3 + 12 k^2 + 5 k + 1 = 2^m m=0 then k=0 Solution (2,1) m=1 no solution m=2 no solution missing to analyze for m>=3
12.06.2007 21:35
Another approach: n=3 k , k>=1 f(x)=x^3+2 x +1 x= 2^k 2^(3k) + 2 2^k + 1> 2^(3k) x= 2^k – 1 (2^k – 1)^3+ 2 (2^k – 1) +1 = 2^(3k) – 3 2^(2k) + 5 2^k – 2 < 2^(3k) iff 5 2^k < 3 2^(2k) + 2 iff 5 < 3 2^k + 2/ 2^k then f(x) > 2^n > f(x-1) there is no solution
12.06.2007 22:03
mszew wrote: Another approach: n=3 k , k>=1 f(x)=x^3+2 x +1 x= 2^k 2^(3k) + 2 2^k + 1> 2^(3k) x= 2^k – 1 (2^k – 1)^3+ 2 (2^k – 1) +1 = 2^(3k) – 3 2^(2k) + 5 2^k – 2 < 2^(3k) iff 5 2^k < 3 2^(2k) + 2 iff 5 < 3 2^k + 2/ 2^k then f(x) > 2^n > f(x-1) there is no solution I don't quite understand this approach and the last. There is a solution with $x=1,n=2$. Also, any solution must have even $n$ (not odd like you claimed in the last one), which can be verified using mod 3. This approach (showing when $n$ is divisible by 3, then there's no solution) works when $x$ is divisible by 7, and when $x\not\equiv 0,1\pmod{7}$ then there are no solutions mod 7... but this doesn't work when $x\equiv 1\pmod{7}$ and $n\equiv 2\pmod{3}$... combining this with easy mod 2 and mod 3 checks, we require $x\equiv 1\pmod{14}$ and $n\equiv 2\pmod{6}$, so any other solutions, if they exist, will be large. However, mods alone will not destroy the problem, and I can't seem to get anywhere with the equation $x^{3}+2x+1=y^{2}$, even though it seems like a logical step after proving $n$ even...
13.06.2007 14:56
Thanks for your remarks. I have edited my previous post, I made a mistake putting n instead of x. I try to construct the natural x such f(x) > 2^n > f(x-1) for the two other cases of n=3k+1 or 3k+2. k>=1
13.06.2007 16:29
$2^{n}-1=\sum_{i=0}^{n-1}{2^{i}}=(111...11)_{2}$ Let $k$ be the most significant bit of $x$ then: $x^{3}\geq 2^{3k}$ $(2x)_{2}^{negate}+\sum_{i=k+2}^{m}{2^{i}}=(x^{3})$ The max value of $(2x)_{2}^{negate}$ is $\sum_{i=2}^{k}{2^{i}}+1$ then: $\sum_{i=2}^{k}{2^{i}}+1+\sum_{i=k+2}^{m}{2^{i}}=\sum_{i=2}^{m}{2^{i}}-2^{k+1}+1\leq 2^{3k}=\sum_{i=0}^{3k-1}{2^{i}}+1\leq x^{3}\Leftrightarrow m<3k$ The inequality holds becouse m=3k-2 in this case. Correct me if I'm wrong!
21.06.2007 08:31
This problem is quite nice,It cost me nearly one hour... I am sorry that I didn't read the above posts carefully,But I think there is not a complete solution. Let me give mine: Let me assume that $n\ge 3$ then we easily get that $x\equiv 5(mod 8)$ Case 1:$n$ is odd. Then we have that $x^{2}(x+2)=2^{n}-1=2*(2^\frac{n-1}{2})^{2}-1$ suppose that $q$ is a prime fractor of $x$ such that $q\not \equiv 1,-1(mod 8)$(becuase $x\equiv 5$ ,there exist such a $q$) then $2*(2^\frac{n-1}{2})^{2}-1\equiv 0(\mod q)$ then$\left (\frac{2}{q}\right )=1$ but this is a contradution with $q\not \equiv 1,-1(mod 8)$ Case 2:$n$ is even . We have that $(x+1)(x^{2}-x+3)=x^{3}+2x+3=2(2^{n-1}+1)=2(2*(2^{\frac{n-2}{2}})^{2}+1)$ Because $x\equiv 5(mod 8)$,$x^{2}-x+3\equiv-1(\mod 8)$.So there exist a prime fractor$q$ of $x^{2}-x+3$ such that $q\not\equiv 1,3(\mod 8)$(Notice that $3^{l}\equiv 1 or 3(\mod 8)$) Then we have that $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod 8).$ Then $\left ( \frac{-2}{q}\right )=1$ but this is a contradition with $q\not\equiv 1,3(\mod 8)$ Now we deduce that when $n\ge 3$,there is no solution. I hope I am right. scorpius119 wrote: mszew wrote: Another approach: n=3 k , k>=1 f(x)=x^3+2 x +1 x= 2^k 2^(3k) + 2 2^k + 1> 2^(3k) x= 2^k – 1 (2^k – 1)^3+ 2 (2^k – 1) +1 = 2^(3k) – 3 2^(2k) + 5 2^k – 2 < 2^(3k) iff 5 2^k < 3 2^(2k) + 2 iff 5 < 3 2^k + 2/ 2^k then f(x) > 2^n > f(x-1) there is no solution I don't quite understand this approach and the last. There is a solution with $x=1,n=2$. Also, any solution must have even $n$ (not odd like you claimed in the last one), which can be verified using mod 3. This approach (showing when $n$ is divisible by 3, then there's no solution) works when $x$ is divisible by 7, and when $x\not\equiv 0,1\pmod{7}$ then there are no solutions mod 7... but this doesn't work when $x\equiv 1\pmod{7}$ and $n\equiv 2\pmod{3}$... combining this with easy mod 2 and mod 3 checks, we require $x\equiv 1\pmod{14}$ and $n\equiv 2\pmod{6}$, so any other solutions, if they exist, will be large. However, mods alone will not destroy the problem, and I can't seem to get anywhere with the equation $x^{3}+2x+1=y^{2}$, even though it seems like a logical step after proving $n$ even... I don't quite understand you.(totally becuase my English is too bad... ) But Can you share the soluiton of the equaiton $x^{3}+2x+1=y^{2}$?Or there doesn't exist an elementry soluiton of this equation?Thanks
22.06.2007 22:07
Hawk Tiger wrote: Then we have that $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod 8).$ Then $\left ( \frac{-2}{q}\right )=1$ Could you explain this part? I don't quite get why $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod 8).$
23.06.2007 03:19
Hawk Tiger wrote: I don't quite understand you.(totally becuase my English is too bad... ) But Can you share the soluiton of the equaiton $x^{3}+2x+1=y^{2}$?Or there doesn't exist an elementry soluiton of this equation?Thanks I thought it would be possible to show that $x^{3}+2x+1=y^{2}$ has a limited number of solutions (probably only (1,2)?), but wasn't sure how to proceed. Actually now, I found a solution! It's surprisingly similar to yours.
23.06.2007 05:41
Joao Guerreiro wrote: Hawk Tiger wrote: Then we have that $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod 8).$ Then $\left ( \frac{-2}{q}\right )=1$ Could you explain this part? I don't quite get why $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod 8).$ Sorry ,there is a typo.it should be $2*(2^{\frac{n-2}{2}})^{2}\equiv-1(\mod q).$
23.06.2007 20:05
Why if $2\times \left(2^{\frac{n-2}{2}}\right)^{2}\equiv-1 \mod q$ then we know $-2$ is quadratic residue $\mod q$ ? thx..
23.06.2007 21:48
Because $-2 \equiv \left(\frac{1}{2^{\frac{n-2}{2}}}\right)^{2}\pmod q$
05.03.2008 23:58
scorpius119 wrote: Rewrite as $ (x + 1)(x^{2} - x + 3) = y^{2} + 2$. In particular, if $ p$ is a prime divisor of $ x^{2} - x + 3$, then $ y^{2} + 2\equiv 0\pmod{p}$. This, along with the fact that $ p$ is odd, requires $ p\equiv 1,3\pmod{8}$. This results in $ x^{2} - x + 3\equiv 1,3\pmod{8}$ and so $ x\equiv 3,1\pmod{8}$. [/hide] Can anybody explain why $ p\equiv 1,3\pmod{8}$?
19.11.2009 16:35
It's such an easy question and I can't understand how it can be third on the National Olympiad. From Fermat's little theorem we have $ x^3 + 2x + 1\equiv x - x + 1 (mod 3) \Rightarrow 2^n\equiv 1(mod 3)$ and so $ n$ is even. Set $ n = 2n_{1}$. Now, the equation can be rewritten like: $ x(x^2 + 2) = (2^{n_{1}} - 1)(2^{n_{1}} + 1)$. We have $ gcd(2^{n_{1}} - 1,2^{n_{1}} + 1)|(2^{n_{1}} + 1) - (2^{n_{1}} - 1) = 2$. It's obvious that gcd can't be 2 so it is 1. It's easy to see that $ gcd(x,x^2 + 2) = 1$ because $ x = 2$ doesn't lead to a solution. Since we have $ x^2 + 2 > x$ we obtain: \begin{tabular}{|l}2^{n_{1}} + 1 = x^2 + 2 \\ 2^{n_{1}} - 1 = x \end{tabular} which leads to $ x^2 = x$ and so $ x = 1$ is the only natural solution. Finally, the unique $ (n,s)$ which is solution to the problem is $ (2,1)$.
19.11.2009 16:48
broniran wrote: It's such an easy question and I can't understand how it can be third on the National Olympiad. From Fermat's little theorem we have $ x^3 + 2x + 1\equiv x - x + 1 (mod 3) \Rightarrow 2^n\equiv 1(mod 3)$ and so $ n$ is even. Set $ n = 2n_{1}$. Now, the equation can be rewritten like: $ x(x^2 + 2) = (2^{n_{1}} - 1)(2^{n_{1}} + 1)$. We have $ gcd(2^{n_{1}} - 1,2^{n_{1}} + 1)|(2^{n_{1}} + 1) - (2^{n_{1}} - 1) = 2$. It's obvious that gcd can't be 2 so it is 1. It's easy to see that $ gcd(x,x^2 + 2) = 1$ because $ x = 2$ doesn't lead to a solution. Since we have $ x^2 + 2 > x$ we obtain: \begin{tabular}{|l}2^{n_{1}} + 1 = x^2 + 2 \\ 2^{n_{1}} - 1 = x \end{tabular} You cant conclude from $ xy=zt$ with $ x<y$ and $ z<t$ and $ (x,y)=(z,t)=1$ that $ x=z$ and $ y=t$ : for example, we have $ 3\cdot 85=15\cdot 17=(2^4-1)(2^4+1)$ with $ (3,85)=(15,17)=1$ .... But maybe I missed something since you said that it was such an easy question ....
20.11.2009 00:59
Isn't it even simplier? Let's assume $ n \geq 3$. It is clear that $ x$ is odd, so $ x^3 \equiv x \pmod{8}$. Taking our equation $ \mathrm{mod} 8$, we get $ x \equiv 5 \pmod{8}$. Now, taking it $ \mathrm{mod} 3$, as $ x^{3} \equiv x$, we get $ 2^{n} \equiv 1$, which is true only if $ n$ is even, so we can write $ n=2m$. Than we can paraphrase our equation into the form:\[ (x+1)(x^{2}-x+3)=2(2^{2m-1}-1)\] (it's simple to guess using Horner's scheme). Taking it $ \mathrm{mod} 8$ once again, we get $ 5 \cdot 7 \equiv 2 \cdot 7 \pmod{8}$ (when $ 2m-1\geq3$). As it is a contradiction, we get $ 2m-1<3$, and therefore $ n=2$. Now it is elementary to prove the unity of pair $ (1,2)$.
20.11.2009 07:13
L-b wrote: Isn't it even simplier? Let's assume $ n \geq 3$. It is clear that $ x$ is odd, so $ x^3 \equiv x \pmod{8}$. Taking our equation $ \mathrm{mod} 8$, we get $ x \equiv 5 \pmod{8}$. Now, taking it $ \mathrm{mod} 3$, as $ x^{3} \equiv x$, we get $ 2^{n} \equiv 1$, which is true only if $ n$ is even, so we can write $ n = 2m$. Than we can paraphrase our equation into the form: \[ (x + 1)(x^{2} - x + 3) = 2(2^{2m - 1} - 1)\] (it's simple to guess using Horner's scheme). Taking it $ \mathrm{mod} 8$ once again, we get $ 5 \cdot 7 \equiv 2 \cdot 7 \pmod{8}$ (when $ 2m - 1\geq3$). As it is a contradiction, we get $ 2m - 1 < 3$, and therefore $ n = 2$. Now it is elementary to prove the unity of pair $ (1,2)$. Maybe simplier, but not with your proof ... I dont know what could be Horner's sheme but according to me the equation $ x^3+2x+1=2^{2m}$ may be written $ (x+1)(x^2-x+3)=2(2^{2m-1}+1)$ and not $ (x + 1)(x^{2} - x + 3) = 2(2^{2m - 1} - 1)$ And with this new equation, taking mod $ 8$ (when $ 2m - 1\geq3$) implies $ 6\cdot (-1)=2\pmod 8$ which is rather useless, IMHO.
16.08.2012 15:35
If $ n \ge 3$ then $ x\equiv 5\pmod{8} $. We have \[ (x+1)(x^{2}-x+3) = 2(2^{n-1}+1) \] If $n-1$ is even we have that left side does not have primes of form $4k+3$ and this is impossible because $x^{2}-x+3 \equiv 7 \pmod 8$. If $n-1$ is odd then $-2$ is quadratic residue mod any odd prime that divides left side. This means for every prime $p$ that divides $x^{2}-x+3$, $p$ is either $8k+1$ or $8k+3$, but again we have $x^{2}-x+3 \equiv 7 \pmod 8$ so this also isn't possible. So $n=1,2$ and checking gives $x=1$, $n=2$
11.03.2015 12:42
Let us first mention $theorem$: If $-2$ is quadratic resideu $(mod p)$ then $p=8k+1$ or $p=8k+3$.$(***)$ For $n>2$ : $x^{3}+2x+1 = 2^{n}$ $\Longrightarrow$ $x$ is odd.$(**)$ If $3|x$ then $3|x^3+2x$ If $x\equiv 1(mod 3)$ then $ x^3+2x\equiv 0(mod 3)$ if $x\equiv 2(mod 3)$ then $x^3+2x\equiv 0 (mod 3)$ $\Longrightarrow$ $2^n\equiv 1 (mod 3)$ $\Longrightarrow 2|n$(because $ord_2(3)=2$). So let $n=2m$ Now by easy transformations we get starting equation transform into: $\boxed{(x+1)(x^2-x+3)=2^{2m}+2}$ Now by we have that every prime factor divide $RHS$ so $2^{2m}\equiv -2 (mod p)$ where $p>2$ can be every prime number from $LHS$. Now by $(***)$ $\Longrightarrow$. Every prime factor $p>2$ from $LHS$ is of the form $p=8k+1$ or $p=8k+3$.$(***)$. So every prime factor of $x^2-x+3$ is in the given form.So $x^2-x+3 \equiv 1 \veebar 3 (mod 8)$ Now if $x^2-x+3\equiv 3(mod8)$ then $x^2-x\equiv 0(mod 8)$, so from this $x$ is odd $contradiction$ with $(**)$. We have that $x^{3}+2x+1\equiv 0 (mod 8)$ $\Longrightarrow x\equiv 5 (mod 8)$. So $x^2-x+3\equiv 7 (mod 8)$ $\Longrightarrow$ $x^2-x+3\equiv 1 (mod 8)$ is impossible. $\Longrightarrow$ $n\le 2$. For $n=2$, $x=1$. For $n=1$, no solution for x. Thus only solution is $\boxed{(x,n)=(1,2)}$
01.02.2016 18:05
mihajlon wrote: Let us first mention $theorem$: If $-2$ is quadratic resideu $(mod p)$ then $p=8k+1$ or $p=8k+3$.$(***)$ Can you please prove this theorem ?
02.02.2016 17:01
Any solution ??!!!
02.02.2016 17:29
First of all if $(-2/p)=1$ and $p$ odd prime then $p\equiv{1,3}mod8$ It is well known that $(2/p)=(-1)^{\dfrac{p^2-1}{8}}$ so easy get the result. Also $(-2/p)=(-1/p)(2/p)$
21.04.2020 20:01
There is only one solution for $ x\ge1$ $(x,n)=(1,2) $.Consider $ x\ge2$. From $x^3+2x+1=2^n $ we get $x^3<2^n$ .Obvious $ x \le2^{[n/3] }$.Easily we observe that $(x+1)^3>2^n$. So we obtain from this inequalities that $ x =2^{[n/3]}$.So ,next we consider $ n(mod3)$ ,which implies that the only solution is $ (x,n)=(1,2) $.