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

Primes, divisors, arithmetic, number properties, ...
Post Reply
drwhat
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

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

Post by 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.
User avatar
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

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

Post by 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
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

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

Post by 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.
Image
wrongrook
Posts: 480
Joined: Sat Oct 17, 2009 10:39 pm

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

Post by 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.
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

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

Post by Lord_Farin »

wrongrook wrote: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.
Image
drwhat
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

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

Post by 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
User avatar
euler
Administrator
Posts: 3554
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

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

Post by 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
Image
impudens simia et macrologus profundus fabulae
drwhat
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

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

Post by 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
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

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

Post by drwhat »

euler wrote: 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.
Post Reply