Numbers of the form (1+cX)^1/2

[drwhat]

I was curious if there was any way to solve this equation for integers given a specific constant C.

For example (1+24x)^1/2 is obviously an integer when x=1 ( 25) and x=2 (49).

Another way to state it is.. when is 1+24x a perfect square.

Am I just stuck trying every X from 1 to N, or is there some method to make it faster.

Any help would be appreciated.

[jaap]

z^2 = 1+24x

Clearly z has to be odd, and cannot be a multiple of 3.
In other words z==1( modulo 2) and z==1 or 2 (modulo 3)

Combining this, modulo 6=2*3 we must have
z==1 or 5 (6).
i.e. we must have z=6k+1 or z=6k+5 for some integer k.

To check that this works, looking at z^2 we see that
z^2 = (6k + 1)^2 = 36k^2 + 12k + 1 = 12k(3k + 1) + 1
or
z^2 = (6k + 5)^2 = 36k2 + 60k + 25 = 12k(3k+5) + 25

If k is even the rhs is obviously one more than a multiple of 24.
If k is odd, then 3k+1 and 3k+5 are even, and the rhs is again one more than a multiple of 24.
So z=6k+1 and 6k+5 works for any k.

From the above we see that x must be either k*(3k+1)/2 or k*(3k+5)/2 + 1

[Lord_Farin]

You should check out some of the theory on quadratic residues. I suspect they will be at least of some help', as they reduce your equations modulo some primes. Further solving then may be easier.

[wrongrook]

You may want to consider this factorisation:
z^2 = 1 +cx
cx=z^2-1
cx=(z-1)(z+1)

For example, suppose c is a prime p.
=> p|(z-1) or p|(z+1)
=>z=kp+1 or z=kp-1 gives all the solutions. (Solutions for x given by x=(z-1)(z+1)/c)

If c is composite, then you could consider all factorisations c=a.b
You can then solve for a|(z-1) and b|(z+1).
This is equivalent to z=1 modulo a and z=-1 modulo b.
This kind of equation can be solved using the Chinese remainder theorem.

Note that for some a,b these equations might have none, or repeated solutions.

[Lord_Farin]

You may want to consider this factorisation:
z^2 = 1 +cx
cx=z^2-1
cx=(z-1)(z+1)

For example, suppose c is a prime p.
=> p|(z-1) or p|(z+1)
=>z=kp+1 or z=kp-1 gives all the solutions. (Solutions for x given by x=(z-1)(z+1)/c)

If c is composite, then you could consider all factorisations c=a.b
You can then solve for a|(z-1) and b|(z+1).
This is equivalent to z=1 modulo a and z=-1 modulo b.
This kind of equation can be solved using the Chinese remainder theorem.

Note that for some a,b these equations might have none, or repeated solutions.

Good post, explains my ideas somewhat more thoroughly and explicitly.

[drwhat]

Thanks for all the help. I am looking the Chinese remainder theorem now. Also thanks jaap for your take on the solution. Gave me new insight into ways of looking at things to solve a problem

[euler]

Interestingly, solving $8x+1=y^2$ leads to $x=\dfrac{k(k+1)}{2}$, which is the sequence of Triangle numbers.

Below is using the same idea as jaap, but I do the analysis on evenness and divisibility by 3 in separate stages.

Given that $24x + 1 = y^2$ it is clear that $y$ must be odd.
Let $y = 2i + 1 \implies 24x + 1 = 4i^2 + 4i + 1 \implies 6x = i(i+1)$
As LHS is divisible by 3 then either $i$ or $i+1$ must be divisible by 3.
Let $i = 3k \implies 6x = 3k(3k+1) \implies x = \dfrac{k(3k+1)}{2}$, leading to $x = 2,7,15,...$.
Let $i+1 = 3k \implies 6x = (3k-1)3k \implies x = \dfrac{k(3k-1)}{2}$, leading to $x = 1,5,12,...$.

You may recognise the second sequence as Pentagonal numbers, and, in fact, the first sequence is related to Pentagonal numbers.

This has nothing to do with your original question, but as you may know I am quite a fan of Euler. His investigations do not always lead anywhere, but the link below is to one of his papers and it gives an example of how the genius starts off with one idea (the two sequences above) and experiments to see where he can take it.
http://arxiv.org/pdf/math/0505373v1

[drwhat]

Ah.. your too clever Euler. hehe you outed me. The problem is related to pentagonal numbers. I was solving a pentagonal number releated problem and got to the 1+24x=y^2 point

However, this was another example of my favorite thing about Project Euler. I got to dive into a lot of new territory and learn some things (some of which may not be applicable to the problem) that I had not known before.

[drwhat]

This has nothing to do with your original question, but as you may know I am quite a fan of Euler. His investigations do not always lead anywhere, but the link below is to one of his papers and it gives an example of how the genius starts off with one idea (the two sequences above) and experiments to see where he can take it.
http://arxiv.org/pdf/math/0505373v1

That article was very interesting. I paticularly liked the section he did on diffrences. I never thought of reducing sequences like that. I investigated a lot of sequences using that technique and though i'm sure its much covered ground was pretty interesting.

I've been searching cornell's site for other papers by euler and reading those.