Can Pythagorean Triples Help Find Integer Roots of Quadratics?

[approx]

Hello,
I'm playing with a set of quadratics x^2 + bx + c, where b is fixed, and c is allowed to be any integer image of a particular exponential function. As a simplistic example, I might have
x^2 + 100x + 3
x^2 + 100x + 9
x^2 + 100x + 27
x^2 + 100x + 81
etc.
and I'm trying to show that at least one of these quadratics has integer roots. Has anyone seen any results along these lines that might help?

Note that these are not the exact b's and c's I'm working with, it's only a simplistic example. I'm just looking for anything with a similar "flavor".

Approx

 

[mathman]

I'm trying to show that at least one of these quadratics has integer roots. Has anyone seen any results along these lines that might help?

Note that these are not the exact b's and c's I'm working with, it's only a simplistic example. I'm just looking for anything with a similar "flavor".

In your case it is easy to show that the answer is no. Let a and be be the roots. Then a+b=-100, while ab must be a power of 3 implying a and b are powers of 3 (or -3). Impossible conditions. Therefore a necessary condition is that b be a multiple of the first c.

 

[approx]

Actually

Actually, that was just a bad example because I don't want to get bogged down with the details, I just wanted to know if anybody knew of any research that would be helpful. A better example would be x^2 - 127x - c

where c = 2^d * 3^e * 5^f * 7^g * 11^h
where d,e,f,g, and h are integers greater than zero

Now, the question is, can we show that there is some set of d,e,f,g,h which will make this quadratic equation, or others like it, have integer roots, without actually having to find them? By the way, the roots are 567 and -440. I'm just wondering if anyone can remember where they might have seen anything similar.

One thing I've noticed is that, for quadratic x^2 + bx + c, it is easy to see that for it to have integer roots, b^2 + 4c must be a square. Now, since b^2 is a square and since 4 is a square, if it happened to be true that c were a square we would find ourselves in a right triangle situation, with legs b and root(4c) and hypoteneuse root(b^2+4c).

A tough one to crack is x^2 - 167x - c, where c is the same set of numbers as above. The program I wrote on my TI85 hasn't solved that one yet. Good luck!

 

[approx]

BTW, here is the TI85 program I mentioned. The only thing it also needs is a matrix with the first few primes (in order) in the first column and a second column. When it prompts "number" you will enter the linear term (127 in the example above) and when it prompts "highexp" enter the highest exponent of any prime factor that you want to be present in c. It actually goes one higher than you enter, but okay. Most numbers you enter for a linear term need only a "3" entered for highest exponent, but a very few need a 5.

Note: "the square root" needs to be replaced with the square root key, use the "sto>" key for ->, and go to the test menu to get the proper >= key. What follows is case-sensitive.


Prompt NUMBER
NUMBER -> N
Prompt HIGHEXP
HIGHEXP -> HE
"the square root of" N -> RN
0 -> C
1 -> PRML
Lbl CT1
If P(C+1,1) >= RN
Goto CT1OUT
C+1 -> C
P(C,1)*PRML -> PRML
Goto CT1
Lbl CT1OUT
C -> CP1
0 -> CT
Lbl S
CT+1 -> CT
Disp CT
100 -> P(CT,2)
If CT<CP1
Goto S
PRML -> PT
Lbl ATEST
1 -> CT
Lbl ATEST2
If P(CT,2)==101+HE
P(CT+1,2)+1 -> P(CT+1,2)
If P(CT,2)==101+HE
100 -> P(CT,2)
If P(CP1,2)==101+HE
Goto OUT2
PT*P(CT,1)^mod(P(CT,2),100) -> PT
CT+1 -> CT
If CT<CP1+1
Goto ATEST2
PT -> W
PRML -> PT
(-N+"the square root"(N^2+4*W))/2 -> W1
(-N-"the square root"(N^2+4*W))/2 -> W2
abs W1 -> AW1
abs W2 -> AW2
If AW1==1
Goto BYPASS1
If AW2==1
Goto BYPASS1
If W1==int (W1)
Goto OUT2
Lbl BYPASS1
P(1,2)+1 -> P(1,2)
Goto ATEST
Lbl OUT2
Disp N
Disp AW1
Disp AW2

 

[approx]

by the way

By the way, if you want to implement this program on a TI83 or a TI86 (not sure about the TI89) you will have to use variables of only one character. For some reason, the '85 is the only one I know of that allows vars like AW1 and such. And I think they quit making the TI85 calculators for some reason. Boooo! They are the most comfortable to me.
approx

 

[kamerling]

suppose r_1 and r_2 are the two roots of the equation. then r_1+r_2 = 167 and
r1*r2 = c. Combine those and you get c = r_1(167 + r_1). c is of the form 2^d * 3^e * 5^f * 7^g * 11^h if and only if both r_1 and 167+r_1 are of this form.
r_1 = 1 produces x^2 - 167x - 168 = (x+1)(x-168) with -1 and +168 as roots
168 = 2^3*3*7.

 

[approx]

You made two mistakes, though only one is important

suppose r_1 and r_2 are the two roots of the equation. then r_1+r_2 = 167 and
r1*r2 = c. Combine those and you get c = r_1(167 + r_1). c is of the form 2^d * 3^e * 5^f * 7^g * 11^h if and only if both r_1 and 167+r_1 are of this form.
r_1 = 1 produces x^2 - 167x - 168 = (x+1)(x-168) with -1 and +168 as roots
168 = 2^3*3*7.

Sorry, but it should be c = r_1(167 - r_1), not plus. Also, your conclusion is in error. For example, the roots of the equation with b=127 are, as I said, 567 and -440, and so c is of the form stated, though each of r_1 and 127 - r_1 are not of that form. In fact, they are relatively prime, as they must be since 127 is prime.

 

[kamerling]

Sorry, but it should be c = r_1(167 - r_1), not plus. Also, your conclusion is in error. For example, the roots of the equation with b=127 are, as I said, 567 and -440, and so c is of the form stated, though each of r_1 and 127 - r_1 are not of that form. In fact, they are relatively prime, as they must be since 127 is prime.

I should have said if -r_1 is a root. It doesn't matter for the values that c can take.
I didn't notice that d,e,f,g,h could be nonzero, so the conclusion is indeed wrong. sorry.

 

[approx]

Program

Hey, sorry if I sounded abrupt or harsh, shouldn't be typing if I don't have much time to think-over what I'm saying.

Would anybody out there know how to use the program Maxima? I recently downloaded it but I haven't had time to learn the lingo. It uses much bigger numbers than my TI85, and I'm sure it's much quicker, and I was wondering if anyone would be willing to convert my '85 program to the language of Maxima, or at least give me a quick lesson on the commands that I'll need know in order to do it myself? I would greatly appreciate it.

Thanx,
Approx

 

[approx]

Last attempt at asking for help!

Hello, I'm really surprised that nobody has come up with any advice on how to prove such a beast. I've been working on it, in a slightly different form, for about 13 years and I thought for certain that when I came up with a quadratic formulation of my conjecture that there would be some ideas out there. I've googled "quadratic integer sequence" and all sorts of things like that. My last class before getting my Master's degree was complex analysis, though I'm certain I didn't deserve the "B" I got in the class, but if you have any ideas, no matter how crazy, please lay them on me and I'll try to keep up if they are complex analysis - anything easier and I know I can keep up. Thanks in advance for any ideas - please let me know on here or PM me. 'Bye
approx

ps. The general form that I'm actually trying to prove is that there are integer roots for any prime p for the quadratic x^2 + p - c, where c is the product of any positive integer powers of all the primes less than the square root of p.

 

[Pere Callahan]

Ot

How come you got your master's without taking anything harder than complex analysis...ok that\s subjective and there might be really hard complex analysis courses...

 

[Hurkyl]

The general form that I'm actually trying to prove is that there are integer roots for any prime p for the quadratic x^2 + p - c, where c is the product of any positive integer powers of all the primes less than the square root of p.

It looks like that should only very rarely be true.


The problem is the following:

There are approximately (p / (4 k^2))^k possibilities for c that are less than p^k. (see here)

On the other hand, there are approximately p^{k/2} possible values for x^2 + px in the same range.

However, the smallest value you've allowed for c is \sqrt{p}\#, which means k must be larger than around \sqrt{p} / \ln p. (See here)

It's virtually impossible for a match to occur when k is near its minimum: you have about (\sqrt{p} (\ln p)^2 / 4)^k pairs of numbers, but the odds of any particular pair being a match is one in p^k, so a match is very unlikely.

As k grows, the odds of a match are roughly 1 in (4 k^2 / \sqrt{p})^k that you get a match with c smaller than p^k.

So, looking at it probabilistically, the odds of finding a c start off absolutely terrible, and rapidly get worse as you try larger possibilities. (assuming my approximations are sufficiently good)

(This, of course, doesn't preclude something happening for systematic reasons)

 

[approx]

Thank you, Hurkyl, for your assistance in this matter and for the links to smooth numbers and primorials. Though I haven't looked into your computations in detail, they seem sound. I do appreciate you having an open mind at the end:

It looks like that should only very rarely be true.

The problem is the following:
...

So, looking at it probabilistically, the odds of finding a c start off absolutely terrible, and rapidly get worse as you try larger possibilities. (assuming my approximations are sufficiently good)

(This, of course, doesn't preclude something happening for systematic reasons)

You seem to recognize that that each event of finding each root is super-unlikely, and that thus the chances of finding roots for all such quadratics would be nearly zero Unless, as you say, there were some systematic reason. By which, I assume you mean that the only way it is conceivable that my conjecture is true is that the primes are distributed in a very precise way which allows such roots to be found. But that is precisely my conjecture: that the primes are precisely distributed so as to allow such roots to be found. So we agree, I think, that this is highly unlikely, but we also agree, I think, that its unlikely-ness is not a counter-proof. I just have to wonder, what new theorems and/or applications might come about if my conjecture were actually True? Such thinking is, or course, not enough to make us arbitrarily decide that it is true, but it is enough, in my opinion, to make the subject warrant further investigation. I do have some mathematical arguments that suggest the possibility that it might be true, however my faith in my conjecture, I have to admit, boils down to a gut-feeling, in the end.
BTW, in reference to Pere Callahan's comment, I agree that it is a very subjective thing. I believe I had a good professor in that class (maybe too good), it just was a kind of math that seemed too different than anything else I had done, and I had a hard time grasping the basic "meaning" of a contour integral and such. I had a somewhat easier time of it when I finally decided to just memorize and take on faith a bunch of stuff. Other classes I took which stand out in my mind include real analysis, abstract algebra II, and point-set topology (not the introductory one), all of which I conquered fairly well. For my research project, I made a program to find the Jordan Canonical forms for all invertible 2X2 matrices mod 2, mod 3, and mod 5. Unfortunately, instead of using a computer so that I could print them, I made the program on my TI85, so I had to write them down each time one was found. It took a long time. I think I changed the parameters of what I was assigned to do a bit, but by the end of it I understood the subject a lot better because of having to "tweak" the program to get it to "understand" the modular matrices and the field extensions. Lots of work, but great fun!
approx

 

[Hurkyl]

Your conjecture is clearly false for p=2 and p=3. I can disprove your conjecture for p=5:.

Suppose your conjecture is true; then there exists some positive integer a and some positive integer k such that

a^2 + 5 a = 2^k

Write a = 2^n b where b is an odd integer. Then, we have

2^{2n} b^2 + 2^n 5 b = 2^k

Case 1: 0 < n < k[/size]
We have

2^n b^2 + 5b = 2^{k-n}

This implies b is even, which is a contradiction.

Case 2: n > k[/size]
We have

2^{2n - k} b^2 + 2^{n - k} 5b = 1

But the left hand side is even, which is a contradiction.

Case 3: n = k[/size]
We have

2^k b^2 + 5 b = 1

By the rational root theorem, the only possible integer solutions are b = \pm 1. And so we must have

2^k + 5 = 1

or

2^k - 5 = 1,

but neither of these are possible for an integer k.


Case 4: n = 0[/size]
Then we have

a^2 + 5a \equiv 0 \pmod{2^k}

and so a = c 2^k - 5 for some positive integer c. However, this implies

a^2 + 5a = 2^k c (2^k c - 5)

which means we must have both c = 1 and 2^k c - 5 = 1, which cannot happen.


These four cases exhaust all the possibilities, and therefore our hypothesis is incorrect -- there cannot exist an integer solution to x^2 + 5x = 2^k.

 

[approx]

very good point: I have noticed that the conjecture only "kicks-in" for p>9, when p<9 we sometimes need x^2 + px + c = 0
in that case x^2 + 5x + 4 = 0 has the roots 1 and 4.
I know this seems kind of arbitrary, and it is. The original version of my conjecture said "plus or minus c" but I quickly realized that for large p we only use the minus, so I quit worrying about the "plus" version. I should have mentioned it, though. I guess the easy way is to just say that c can be positive or negative. The conjecture still holds for all primes inspected so far.

 

[approx]

likewise, x^2+3x+2 has integer roots, 1 and 2.

 

[Hurkyl]

likewise, x^2+3x+2 has integer roots, 1 and 2.

2 isn't less than the square root of 3, though.

 

[uart]

Approx, it would have been nice if you'd given a decent concise definition of your conjecture right at the beginning of this thread. Can we just get this straight now, is the following exactly what you're trying to prove?

Let p be prime number greater than or equal to 11, and let n denote the largest integer such that the nth prime (p_n) is less than \sqrt{p}.

Conjecture : For each such p there exists n +ive integers, (k_1,\,k_2, \ldots k_n), such that the equation x^2 - px + c = 0 has integer roots, where c=2^{k_1}\, 3^{k_2}\, 5^{k_3} \ldots p_n^{k_n}

 

[CRGreathouse]

So you're trying to show that x^2-px+c has integer roots, where p is prime and at least 11, and c = k\sqrt p\# with k \sqrt p-smooth. A quick appeal to the quadratic formula says that this happens when
p^2-4c=p^2-4k\sqrt p\#
is an odd square. But this clearly fails for large p -- certainly for all p > 17² = 289, since then the discriminant will be negative and there are no real solutions.

 

[uart]

Well that conjecture didn't stand or very long. Just going through the first few in my head it came unstuck at p=23 (worked only for p=11,13,,17,19). So if that's not your conjecture then please state it *properly* for us. If some of the coefficients should be plus or minus \pm then please say so. If some other assumptions are need then please state them ALL.

 

[uart]

Hi CRGreathouse, I didn't see your reply as we posted about the same time. I'm not entirely sure if that is exactly his conjecture, I'm just trying to get him to state it properly for us.

 

[CRGreathouse]

Hi CRGreathouse, I didn't see your reply as we posted about the same time. I'm not entirely sure if that is exactly his conjecture, I'm just trying to get him to state it properly for us.

You know, looking through his (her) posts it seems that that is exactly what he states, but his (her) examples seem to look for a solution 2^{a_1}3^{a_2}\cdots p_k^{a^k} with the a_i nonnegative, rather than positive.

 

[approx]

So you're trying to show that x^2-px+c has integer roots, where p is prime and at least 11, and c = k\sqrt p\# with k \sqrt p-smooth. A quick appeal to the quadratic formula says that this happens when
p^2-4c=p^2-4k\sqrt p\#
is an odd square. But this clearly fails for large p -- certainly for all p > 17² = 289, since then the discriminant will be negative and there are no real solutions.

I truly apologize for not having this conjecture organized when I wrote it - it was an old idea for me, but put into a new form and I hadn't ironed out everything I needed to have to make it clear when I first wrote it.

Here is how it should go, only slightly different than it started out:

I'm trying to show that x^2+px-c has integer roots (notice where the plus and the minus are, this fixes the problem for the quadratic formula since we will get a positive number under the square root), when p is greater than 7, and where the prime factors of c include all the primes less than the square root of p, each factor to any positive integer power.

Then x^2+23x-108 has roots -27 and 4 and
and x^2+23x-288 has roots -32 and 9.

I don't think you will find any *small* primes that provide a contradiction, but if you do I will finally have an answer - even if it wouldn't be the answer I'd like.

Thanks for all the help.

Approx

 

[approx]

put another way, your quote (below) is completely right, except use x^2 + px - c = 0. Thanks again.

Let p be prime number greater than or equal to 11, and let n denote the largest integer such that the nth prime (p_n) is less than \sqrt{p}.

Conjecture : For each such p there exists n +ive integers, (k_1,\,k_2, \ldots k_n), such that the equation x^2 - px + c = 0 has integer roots, where c=2^{k_1}\, 3^{k_2}\, 5^{k_3} \ldots p_n^{k_n}

 

[approx]

CRGreathouse,
thanks for the consideration for gender - it's "he" by the way.
approx

 

[Hurkyl]

where the prime factors of c include all the primes less than the square root of p

And excludes all other primes, I assume.

 

[approx]

correct

 

[0bydefinition]

Has anyone considered a more general conjecture? Like x^n + x^(n-1) + x^(n-2)... x*p - c = 0, x^n + x^(n-1) *p + x^(n-2) * p ... x*p - c = 0, or x^n + x * p - c = 0 ?

 

[approx]

thanks for the ideas, Obydefinition. I will have to think a bit about them. Actually, the reason I came up with my quadratic form is because it can be proven that forming a quadratic x^2 + bx - c, where c is as described before (highest prime factor of c is greatest prime p less than square root of b, and every prime less than p is a factor of c) and where the two roots are relatively prime to each other, can only be done if b is prime. The only question remaining is can it be done for b = any prime, or just for some primes?

 

[approx]

Approx, it would have been nice if you'd given a decent concise definition of your conjecture right at the beginning of this thread. Can we just get this straight now, is the following exactly what you're trying to prove?

Let p be prime number greater than or equal to 11, and let n denote the largest integer such that the nth prime (p_n) is less than \sqrt{p}.

Conjecture : For each such p there exists n +ive integers, (k_1,\,k_2, \ldots k_n), such that the equation x^2 - px + c = 0 has integer roots, where c=2^{k_1}\, 3^{k_2}\, 5^{k_3} \ldots p_n^{k_n}

put another way, your quote (below) is completely right, except use x^2 + px - c = 0. Thanks again.

So, lately I haven't been able to give it a lot of thought, but recently I realized that there are large lists of pythagorean triples which might help find my "c" since p^2+4c must be a perfect square in order for the quadratic formula to work out right, and since pythagorean triples are of the form m^2-n^2 2mn m^2+n^2. Any input here?