You know what it is

So I figured I'd turn this into a sort of rant / journal / math blog. Unfortunately, I don't have a good rant for today. So here's the problem:

Oh, by the way, this problem is part of an entrance exam for a math camp which is STILL TAKING APPLICATIONS. So if any of you feel the desire to apply, heres the answer to #1.

Write 1,000,000 as a sum of a prime and a perfect square

Obviously this could be solved through guess and check(cough cough), but that's a lot of numbers to go through. Doing it algebraically is a lot faster:
Let p be the prime and n be the integer that is being squared.
Also realize that




We've seen this enough, it should be apparent. Factor the right side as difference of squares:



Now we can use our definition of a prime number to help us. The only factors of a prime number are 1 and itself. From our equation above, our two factors are (1,000 + n) and (1,000 - n). Which means one must be 1, and one must be a prime number. Let's say 1,000 + n is the prime, and 1,000 - n is 1. (Note: Obviously the only way 1,000 + n could be 1 is if n is negative, which makes 1,000 + (-n) become 1,000 - n, and makes 1,000 - (-n) become 1,000 + n. Since negative or positive n results in the same thing, we'll just have n be positive, it's easier to work with.)

So now we have:

which is easily solved as:


Now we have to check to see if 1000 + n is a prime.

Check this against a list of primes, and it fits. So,

Rewritten as a sum of a prime and a perfect square,


Not too difficult. Hopefully you're seeing a pattern. When you have two squares, you can usually factor them and then analyze the factors in some way.

I have another proof which I really want to type up, but I have to show some self discipline and go do homework, so I'll get to that some other time. Btw, it's also another answer to the entrance exam.