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
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top