Let $ m,n$ be integers such that $ 0\le m\le 2n$. Then prove that the number $ 2^{2n + 2} + 2^{m + 2} + 1$ is perfect square iff $ m = n$.
Problem
Source: IZO 1 Junior Problem 2
Tags: number theory, greatest common divisor, number theory proposed
The QuattoMaster 6000
16.12.2008 07:58
Let $ x = 2^{n + 1} + 1$, so $ x^2 = 2^{2n + 2} + 2^{n + 2} + 1$ and $ y^2 = 2^{2n + 2} + 2^{m + 2} + 1$. Now, if $ m < n$, then we would have that\[ (2^{n + 1})^2 < y^2 < 2^{2n + 2} + 2^{n + 2} + 1 = (2^{n + 1} + 1)^2\]so $ y^2$ cannot be a perfect square, which is a contradiction. Now assume that $ m > n$. We have that $ (x + y)(y - x) = y^2 - x^2 = 2^{n + 2} (2^{m - n} - 1)$. This means that $ 2^{n + 2} | (x + y)(y - x)$. However, we see have that $ y$ and $ x$ are odd. This means that either $ x - y$ or $ x + y$ is congruent to $ 2\bmod 4$, so $ 2|| (x + y)$ or $ 2||(y - x)$. Either way, we see that $ 2^{n + 1}||(x + y)$ or $ 2^{n + 1} ||(x - y)$. This implies that $ x + y \ge 2^{n + 1} > 2^{m - n + 1} - 2$ since $ m\le 2n$. Now, if $ 2^{n + 1}||(y - x)$, then $ x + y \le 2^{m - n + 1} - 2$, which is impossible, so $ 2^{n + 1}||(x + y)$. Letting $ x + y = l2^{n + 1}$, we have that $ 2^{n + 1} + 1 + y = l2^{n + 1}$, so $ y = (l - 1)2^{n + 1} - 1$. This means that $ y - x = (l - 2)2^{n + 1} - 2$, which means that \[ 2^{n + 2}(2^{m - n} - 1) = y^2 - x^2 = l2^{n + 2}[(l - 2)2^n - 1]\] so $ l[(l - 2)2^n - 1] = 2^{m - n} - 1$. Since $ m\le 2n$, we have that $ 2^{m - n} \le 2^n$, which implies that if $ l\ge 3$, then $ l[(l - 2)2^n - 1] > 2^{m - n} - 1$, which is impossible. Hence, $ l\le 2$. Yet, this means that $ l[(l - 2)2^n - 1] < 0$, which is a contradiction since $ 2^{m - n} - 1 > 0$. Hence, we have a contradiction and it follows that $ m = n$. This gives that $ 2^{2n + 2} + 2^{m + 2} + 1 = (2^{n + 1} + 1)^2$.
hsbhatt
16.12.2008 11:56
Note that $ 2^{2n + 2}$ is a perfect square. If $ 2^{2n + 2} + 2^{m + 2} + 1$ is a perfect square, we must have $ 2^{2n + 2} + 2^{m + 2} + 1 \ge (2^{n + 1} + 1)^2$ from which we get $ m \ge n$ Now, since the given expression is odd, we can write $ 2^{2n + 2} + 2^{m + 2} + 1 = 4k^2 + 4k + 1 \Rightarrow 2^{2n} + 2^m = k(k + 1)$ or $ 2^m(2^{2n - m} + 1) = k(k + 1)$ We must factorise LHS into two consecutive factors. This can be done as $ (2^m p) (q)$ where $ pq = 2^{2n - m} + 1$ and q is odd However, if m>n, then $ 2^m - 2^{2n - m} > 1$. Hence this factorisation is rendered impossible. If m = n then the expression is $ (2^{n + 1} + 1)^2$ which is a perfect square. Hence $ 2^{2n + 2} + 2^{m + 2} + 1$ is a perfect square iff m = n
befuddlers
16.12.2008 20:37
Nice solution quatto. But ur arguement can be simplified We see $ y^2-1$ = $ 2^2n+2$+$ 2^m+2$ Then observing that y+1 and y-1 have gcd max of 2 We can prove that m=n by proving that m cannot be less than or greater than n by plugging in the above equation. Will complete my proof later coz i am in school.
jgnr
25.12.2008 11:04
If $ m=n$, then $ 2^{2n+2}+2^{m+2}+1=2^{2n+2}+2^{n+2}+1=(2^{n+1}+1)^2$. Hence the "if" part is true. Now we shall prove the converse.
Assume that $ m\ne n$, by way of contradiction. Consider two cases:
(i) $ m<n$, we have $ 2^{2n+2}<2^{2n+2}+2^{m+2}+1<2^{2n+2}+2^{n+2}+1$, i.e., $ (2^{n+1})^2<2^{2n+2}+2^{m+2}+1<(2^{n+1}+1)^2$. Hence $ 2^{2n+2}+2^{m+2}+1$ lies strictly between two consecutive perfect squares. Contradiction.
(ii) $ m>n$.
Let $ 2^{2n+2}+2^{m+2}+1=(2^{n+1}+a)^2$. Since $ m\le 2n$, we have $ (2^{n+1}+a)^2\le 2^{2n+2}+2^{2n+2}+1=2^{2n+3}+1$.
$ 2^{n+1}+a\le2^{n+2}$
$ a\le2^{n+1}$
It's obvious that $ a$ is odd, so let $ a=2k+1$.
$ 2k+1\le 2^{n+1}$
$ 2k\le 2^{n+1}-1\rightarrow 2k\le 2^{n+1}-2$
$ k\le 2^n-1$
We also have $ (2^{n+1}+2k+1)^2=2^{2n+2}+2^{m+2}+1$
$ 2^{2n+2}+4k^2+1+k\cdot 2^{n+3}+4k+2^{n+2}=2^{2n+2}+2^{m+2}+1$
$ k^2+k\cdot 2^{n+1}+k+2^n=2^m$
$ k(k^2+2^{n+1}+1)=2^m-2^n=2^n(2^{m-n}+1)$
Since $ k$ is odd, $ k^2+2^{n+1}+1$ must be divisible by $ 2^n$, and hence $ k^2+1$ is divisible by $ 2^n$. So $ k+1\ge 2^n$. But we have proved that $ k\le 2^n-1$. So equality must holds, i.e., $ k=2^n-1$. Sub this back to the equation, we have
${ (2^{n+1}+2(2^n-1}+1)^2=2^{2n+2}+2^{m+2}+1$
$ (2^{n+2}-1)^2=2^{2n+2}+2^{m+2}+1$
$ 2^{2n+4}-2^{n+3}+1=2^{2n+2}+2^{m+2}+1$
$ 2^{n+3}(2^{n+1}-1)=2^{m+2}(2^{2n-m}+1)$
The highest power of 2 which divides lhs is $ n+3$, and the highest power of 2 which divides rhs is $ m+2$. Hence $ n+3=m+2$, i.e., $ m=n+1$. Sub this again, we have $ 2^{2n+2}+2^{n+3}+1$ is a perfect square. Note that $ (2^{n+1}+1)^2=2^{2n+2}+2^{n+2}+1<2^{2n+2}+2^{n+3}+1$. Also note that $ (2^{n+1}+3)^2=2^{2n+2}+3\cdot2^{n+2}+1>2^{2n+2}+2^{n+3}+1$. Hence, $ 2^{2n+2}+2^{n+3}+1$ lies strictly between two consecutive odd perfect squares. Since $ 2^{2n+2}+2^{n+3}+1$ cannot be even, we have a contradiction. So we have done.
MathIsHellaCool
02.06.2013 22:52
Let 'i' be some number 2^(2n+2) + 2^(m+2) + 1 = i^2 I factored a 4 out of the left side to make it simpler 4 ( 2^(2n) + 2^(m) + (1/4) ) = i^2 2^(2n) + 2^(m) + (1/4) = (i/2)^2 Since n = m, I plugged in m for n 2^(2m) + 2^(m) + (1/4) = (i/2)^2 Then you can factor the left side (2^(m) + (1/2))^2 = (i/2)^2 By taking the square root of both sides 2^m + (1/2) = (i/2) Multiply both sides by 2 i = 2^(m+1) + 1 Since m is an integer, i must also be an integer. I think that would work as a proof, but I didn't use the initial condition 0<m<=2n at all.
mavropnevma
02.06.2013 23:04
No, that will not work as a proof. You only took a large number of lines to prove that, if $m=n$, then $2^{2n+2} + 2^{m+2} + 1$ is a perfect square, which is obvious since $2^{2n+2} + 2^{n+2} + 1 = \left (2^{n+1} + 1\right )^2$. But the problem asked for if and only if (iff is shorthand for it). No wonder you did not use $0\leq m \leq 2n$, since for $m= 4n$ we again have $2^{2n+2} + 2^{4n+2} + 1 \left (2^{2n+1} + 1\right )^2$.
MathIsHellaCool
03.06.2013 00:35
Oops I thought they just spelled 'if' wrong when they copied the problem down
lazizbek42
06.12.2021 19:29
inequality