A 8

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A 8

G H J

Reveal topic tags

modular arithmetic

Divisibility Theory

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 6 Y

Y by Davi-8191, Wizard_32, Ramanujan_math, EulersTurban, Adventure10, Mango247

The integers $a$ and $b$ have the property that for every nonnegative integer $n$ the number of $2^n{a}+b$ is the square of an integer. Show that $a=0$ .

Z K Y

The post below has been deleted. Click to close.

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

667 posts

#2 h May 25, 2007, 12:24 AM • 8 Y

Y by Viswanath, vsathiam, Wizard_32, Ramanujan_math, Adventure10, Mango247, and 2 other users

$2^n a+b=x_n^2$
then $x_{n+2}^2-b=4(x_n^2-b)$
$x_{n+2}^2-(2x_n)^2=-3b$
but equation $x^2-y^2=c$ has finite solution.thus $x_k=x_l$ for some $k\not= l$ hence $a=0$

Z K Y

The post below has been deleted. Click to close.

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

334 posts

#3 h May 25, 2007, 12:24 AM • 6 Y

Y by fractals, Viswanath, Adventure10, Mango247, and 2 other users

A proof from first principles.

Let $(a,b)$ be a counterexample with smallest $|a|+|b|$ .

Theorem: b is odd.

Proof

1. $b\ne 0$ .

For otherwise $a$ is a non-zero square with $2a$ square. This contradicts the irrationality of the square root of 2.

2. $b$ is not divisible by 4

If it were, then for all n, $2^na+\frac{b}4=\frac{2^{n+2}a+b}4$ would be square, so $(a,\frac{b}4)$ would be a smaller counterexample.

3. $b$ is odd

Otherwise $4a+b$ is a square which is divisible by 2 but not 4.

QED

Then suppose that for all $n$ , $2^na+b=t_n^2$ where $t_n\ge 0$ .

Theorem: For all $n$ with $2^{n-2}>|a|$ and $n>0$ that there exists some odd factor $x$ of $a$ such that $t_n=2^{n-2}y-x$ where $y=\frac{a}{x}$ .

Proof

Note that $(t_{n+1}+t_n)(t_{n+1}-t_n)=t_{n+1}^2-t_n^2=2^na$ . Furhter, since $b$ is odd, $t_n$ and $t_{n+1}$ are both odd. Thus both of $t_{n+1}+t_n$ and $t_{n+1}-t_n$ are even, but only one is a multiple of 4. Thus there exist $x,y$ with xy=a and with x odd such that $\{t_{n+1}+t_n,t_{n+1}-t_n\}=\{2x,2^{n-1}y\}$ . However, $2^{n-1}y\ge 2^{n-1}>2|a|\ge 2x$ . Thus $t_{n+1}+t_n=2^{n-1}y$ and $t_{n+1}-t_n=2x$ . Subtracting gives the required expression for $t_n$ .

QED

Theorem: For any odd factor x of a, there can be at most 2 n such that $(2^{n-2}y-x)^2=2^na+b$ where $y=\frac{a}{x}$ .

Proof

To see that there are at most 2 such n, expand and multiply by 16 to get $2^{2n}y^2-2^{n+3}a+x^2=2^{n+4}a+b$ . Letting $z=2^n$ , this gives $y^2z^2-(24a)z+x^2-b=0$ , which is a nondegenerate quadratic equation with at most 2 solutions.

QED

We have shown that for all sufficiently large n there is such an x. However, there are only finitely many such x, and each corresponds to at most 2 n. This contradiction shows that there are no counterexamples.

Z K

The post below has been deleted. Click to close.

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

3615 posts

Peter

#4 h Oct 28, 2007, 2:28 AM • 2 Y

Y by Adventure10, Mango247

Can you write your solution a bit better, Hawk Tiger? If it is correct, it's very short.

Z K Y

The post below has been deleted. Click to close.

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

975 posts

#5 h Nov 2, 2007, 1:59 AM • 2 Y

Y by Adventure10 and 1 other user

See at http://www.mathlinks.ro/Forum/viewtopic.php?search_id=600084763&t=145117
http://www.mathlinks.ro/Forum/viewtopic.php?p=150403#150403

Z K Y

The post below has been deleted. Click to close.

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

3615 posts

Peter

#6 h Nov 2, 2007, 1:51 PM • 3 Y

Y by pablock, Adventure10, Mango247

Probably this is what Hawk Tiger meant, written out.

edriv wrote:

For each n:
$2^{n}a + b$ is a perfect square $\Rightarrow 4(2^{n}a + b) = 2^{n + 2}a + 4b$ is a perfect square.
Also $2^{n + 2}a + b$ is a perfect square.
Then we have two perfect squares at distance $3b$ . We con construct arbitrary large perfect squares with distance $3b$ . But this is impossible, then:
- the distance is 0, $b = 0$ , but then $a,2a$ are both perfect squares $\Rightarrow a = 0$
- then our squares are not arbitrary large: $a = 0$ .

Z K Y

The post below has been deleted. Click to close.

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

16 posts

#7 h Apr 29, 2012, 3:12 PM • 2 Y

Y by Adventure10, Mango247

Trying to solve this problem, i found some curious facts about sequences that satisfy the recursive equation
$X_{n+2}=3X_{n+1}-2X_n$ .

It's easy to see that the sequence of $2^n a+b$ where $n$ spans the nonnegative integers satisfy the equation.
It's also easy to prove that $X_n$ can be written as $\alpha_nX_1+\beta_nX_0$ where $\{\alpha_n\}$ and $\{\beta_n\}$ are also such sequences. Namely, $\alpha_n=2^n-1$ and $\beta_n=2-2^n$ .
Another curious fact is that $X_n \equiv X_{n+j} \pmod{\alpha_j}, j\geq 2$

Nevertheless, this facts didn't help me to solve the problem... ;(

Z K Y

The post below has been deleted. Click to close.

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

471 posts

#8 h Oct 18, 2015, 3:05 AM • 1 Y

Y by Adventure10

basically just post #2

Z K Y

The post below has been deleted. Click to close.

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

34 posts

#10 h Aug 21, 2017, 9:14 AM • 2 Y

Y by Adventure10, Mango247

There is an extremely nice generalization of this result:
Let $W(x)$ be a polynomial with integer coefficients such that $W(2^{n})$ is a perfect square for all positive integers $n$ . Then there exist another polynomial $Q(x)$ with integer coefficients such that $W(x)=Q(x)^{2}$

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#11 h Apr 16, 2020, 7:22 AM

Y by

if $a$ is nonzero then $2^n{a}+b$ can be any big which implies :

$x^2=2^n{a}+b , y^2=2^{n+2}{a}+b \implies 4x^2-y^2=3b$

which means we got infinite pair of positive integers like $(2x,y)$ such as that the difference of their squares is a constant which a contradiction...

This post has been edited 1 time. Last edited by H.HAFEZI2000, Apr 16, 2020, 7:27 AM

Z K Y

The post below has been deleted. Click to close.

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

243 posts

pie854

#12 h Sep 14, 2024, 7:23 PM

Y by

Since $b$ is a quadratic residue $\pmod{2^n}$ for every $n$ , it must itself be a perfect square. Let $b=c^2$ , where $c>0$ . Suppose $2^n a+b=d_n^2$ for $n\geq 0$ . Note that this implies that $a\geq 0$ . Suppose that $a\neq 0$ . Then $d_n+c=2^i k_1, \quad d_n-c=2^j k_2$ where $2\nmid k_1 k_2$ , $a\geq k_1,k_2\geq 1$ and $i+j\geq n$ . This implies that $c=2^{i-1}k_1-2^{j-1}k_2 \qquad (1)$ Let $v_2(c)=t$ then $(1)$ implies that $\min(i,j)=t+1$ . So for any $n$ either $c=2^t k_1-2^{j-1}k_2< 2^t a-2^{n-t-2} \qquad \text{or} \qquad c=2^{i-1}k_1-2^t k_2 >2^{n-t-2}-2^t a.$ In any case if we take $n\to \infty$ we get a contradiction, as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a