Solving Prime p Equation - x²+px-444p = 0

[nonequilibrium]

I bumped into this problem on the net, and the question is as follows:

We have a prime p and the solutions of x²+px-444p = 0 are integers.
What do we know about p:

A) 0 < p [tex]\leq[/tex] 11
B) 11 < p [tex]\leq[/tex] 21
C) 21 < p [tex]\leq[/tex] 31
D) 31 < p [tex]\leq[/tex] 41
E) 41 < p [tex]\leq[/tex] 51

How would you go on to solve this?

Here are the solutions for the given equation:

p = [tex]\frac{-x^2}{x-444}[/tex]

x = (-p [tex]\pm[/tex][tex]\sqrt{p^2+1776p}[/tex])/2

Remember x must be an integer, so there must be an integer q = np+m and q² = p²+1776p, making

x = ( -p [tex]\pm[/tex](np+m) )/2

= ( -p [tex]\pm[/tex]np [tex]\pm[/tex]m )/2

= [tex]\pm[/tex]p.(n[tex]\mp[/tex]1)/2 [tex]\pm[/tex]m/2

We see:

• m is either even or zero (when divided by two it is an integer)
• as p is a prime number, (n[tex]\mp[/tex]1) must be dividable by two, so n is odd

This is as far as I can reason... I probably calculated unnecessary information.

The site I got this problem from seems to have neglected to add a solution, so I can't check for answers. I'm curious what you think is the easiest way to solve this.

 

[dodo]

Well, there are not so many primes p between 2 and 51, in order to test if p^2+1776p is a square.
Actually, only one of them will work. ;)

I have one objection to the logic above: you go from a sum of the form (a+b)/2 and distribute the division into a/2+b/2, but then you cannot make statements about the individual parity of a or b. If (a+b) is even, then a and b have the same parity, either both odd or both even, but nothing else can be said about that (unless you know the actual parity of one of them, which is not the case).

I see the intuition beyond splitting q into np+m, but I believe that what you'd like is to split p into 10n+m, with m in [1,10], since then n would directly tell you in which category A,B,C,D,E the prime p lies in. I tried to substitute this in the quadratic solution, but didn't get anywhere and recurred to brute force. :)

 

[mda]

You can show that 444 mod x = 0, and x mod p = 0, and 444 mod p = 0, so
444 = 2^2 3 37 which narrows the possibilities quite quickly.

 

[mda]

Further, denoting the roots in x as rp & sp, where r & s are integers,
you can show that r s = -444 / p, and r + s = 1.

Since 4-3=1, p=37.

 

[dodo]

Hey, that's cool.

I followed up to r+s=1, but I don't see why rp . sp = -444.

 

[mda]

(x+rp)(x+sp) = x^2 + xp - 444p

Expand the product and equate the x^0 terms

 

[dodo]

Oh, wait. Correct me if I'm wrong. I would have written the factorization as (x-rp)(x-sp)... and after checking, I see r+s = -1, which matches. (The solution for x starts with minus p/2, plus/minus the square root of blah blah / 2)

 

[mda]

Yes, I should have written (x-rp)(x-sp), but it doesn't affect p.
Only affects which of the roots should be negative.

 

[nonequilibrium]

So the easiest way (?) of solving it would be dividing the original equation by p:

[tex]\frac{x²+px-444p}{p}[/tex] = x²/p + x - 444

We now know p|x² and thus p|x, and we now divide the original equation by p²:

[tex]\frac{x²+px-444p}{p^2}[/tex] = [tex]\frac{x^2}{p^2}[/tex] + [tex]\frac{x}{p}[/tex] - [tex]\frac{444}{p}[/tex]

As x/p is an integer, p|444, meaning the prime fractorization of 444 (= 2.2.3.37) will contain p. Now we equalize

(x-rp)(x-sp) = x²+px-444p

x² + (-r-s)px + (rsp)p = x² + px - 444p

Giving -r-s=1 and 444/(rs)=p

Looking at the factorization of 444, only r=4 and s=3 will do, giving p=37

 

[Werg22]

The easiest way is certainly easier. It is apparent that the discriminant p^2 + 1776p must be a perfect square. Since p divides into the discriminant, so must p^2. Hence p divides into 1776. The primes of 1776 are 2, 3 and 37.

 

[mda]

The easiest way is certainly easier. It is apparent that the discriminant p^2 + 1776p must be a perfect square. Since p divides into the discriminant, so must p^2. Hence p divides into 1776. The primes of 1776 are 2, 3 and 37.

I'm not sure how this is easier... I think this is pretty much the same as what we've done except that it does not show which one is p. Note that the method summarized by mr vodka also predicts whether or not this will happen... the x^0 must be a product of only three numbers: p and two numbers that differ by exactly one.

 

[Werg22]

A thousand apologies, I judged the solution by its length rather than its content.

 

[nonequilibrium]

Thanks for the help, guys