MHB Proof that x=0 for Integers with Perfect Square Property

AI Thread Summary
The discussion centers on proving that for integers x and y, if the expression 2^n*x + y is a perfect square for all non-negative integers n, then x must equal 0. The proof is noted to be complex and relies on an unproven conjecture, although it has been conditionally proven under the Generalized Riemann Hypothesis (GRH). The conversation highlights the generalization of this property to bases other than 2, suggesting broader implications. Participants express appreciation for the clarity of the solutions provided, indicating a collaborative effort in tackling the problem. The conclusion emphasizes the potential for a more straightforward proof of this mathematical assertion.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
The integers $x$ and $y$ have the property that for every non-negative integer $n$, the number $2^nx+y$ is a perfect square.

Show that $x=0$.
 
Mathematics news on Phys.org
This is far from the simplest proof, as it relies on an open (but very likely true, proven conditionally under GRH, etc) conjecture, but I thought it was neat especially since it generalizes to many bases other than $2$. I think it's correct.

Definition: A pair of integers $(x, y)$ is a solution if and only if $2^n x + y$ is a perfect square for all nonnegative integers $n \geq 0$.

Proposition: There are infinitely many (odd) primes $p$ such that $2$ is a primitive root modulo $p$.

Note: This is Artin's conjecture on primitive roots for the case $g = 2$.

Theorem: If $(x, y)$ is a solution and $p > 3$ is an odd prime such that $2$ is a primitive root modulo $p$ then $x$ must be a multiple of $p$.

Proof: Note that there are exactly $1 + (p - 1)/2$ different quadratic residues modulo $p$ (including zero) however the primitive root $2$ generates $p - 1$ different residues modulo $p$, since it generates the group, that is, $\lvert \langle 2 \rangle_p \rvert = p - 1$. Now if $x$ is coprime to $p$ then $\lvert x \langle 2 \rangle_p \rvert = p - 1$ as the multiplication by $x$ modulo $p$ is invertible, and of course $\lvert x \langle 2 \rangle_p + y \rvert = p - 1$ since addition of $y$ modulo $p$ is also invertible for any integer $y$.

Hence if $x$ is coprime to $p$ then $2^n x + y$ assumes $p - 1$ distinct residues modulo $p$ over all $n \geq 0$ whereas perfect squares can only have $1 + (p - 1)/2$ distinct residues modulo $p$, and $1 + (p - 1)/2 < p - 1$ for all $p > 3$, so that $2^n x + y$ cannot be a perfect square for all $n \geq 0$. Thus if $(x, y)$ is a solution then $x$ must be a multiple of $p$. $\blacksquare$

Corollary: If $(x, y)$ is a solution then $x = 0$.

Proof: This follows immediately from the above theorem and proposition which imply that $x$ must be a multiple of infinitely many primes, and the only way this can hold is if $x$ is zero. $\blacksquare$

The argument generalizes for different (non-square) bases other than $2$ by assuming the validity of Artin's conjecture for different primitive roots and some minor modifications. I think you can also adapt it for the case of perfect cubes and such, but I haven't checked. Anyway this is some heavy machinery and I'm sure there's a more elementary proof for this particular challenge.
 
Bacterius said:
I'm sure there's a more elementary proof for this particular challenge.

Thanks for your well-written solution, Bacterius!

And yes, your intuition is spot on and I would post it (if no one else solved it with elementary method) when this challenge has come close to its "expiration" date. :o
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top