# Find the Prime

1. Jan 12, 2008

### nonequilibrium

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

How would you go on to solve this?

Here are the solutions for the given equation:

p = $$\frac{-x^2}{x-444}$$

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

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

x = ( -p $$\pm$$(np+m) )/2

= ( -p $$\pm$$np $$\pm$$m )/2

= $$\pm$$p.(n$$\mp$$1)/2 $$\pm$$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$$\mp$$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.

2. Jan 12, 2008

### 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. :)

Last edited: Jan 12, 2008
3. Jan 12, 2008

### 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.

4. Jan 12, 2008

### 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.

5. Jan 12, 2008

### dodo

Hey, that's cool.

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

6. Jan 12, 2008

### mda

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

Expand the product and equate the x^0 terms

7. Jan 12, 2008

### 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)

8. Jan 12, 2008

### 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.

9. Jan 13, 2008

### nonequilibrium

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

$$\frac{x²+px-444p}{p}$$ = x²/p + x - 444

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

$$\frac{x²+px-444p}{p^2}$$ = $$\frac{x^2}{p^2}$$ + $$\frac{x}{p}$$ - $$\frac{444}{p}$$

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

10. Jan 13, 2008

### 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.

Last edited: Jan 13, 2008
11. Jan 13, 2008

### mda

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.

12. Jan 14, 2008

### Werg22

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

13. Jan 14, 2008

### nonequilibrium

Thanks for the help, guys

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook