# Interesting problem from a Putnam student

1. Apr 16, 2004

### philosophking

I'm taking the Putnam next fall, and decided to pick up a copy of Larson's problem solving book for practice. I'm having trouble, though, with one of the problems. It goes as follows.

A well known theorem states that for a prime p>2, p=x^2+y^2 iff p is one more than a multiple of 4.

Show: every prime one more than a multiple of 8 can be written in the form x^2 + 16y^2

:every prime five more than a multiple of 8 can be written in the form (2x+y)^2 + 4y^2

In all of these, x,y are integers. I think what might be confusing me is that I haven't taken a number theory course yet, so I don't know too much about mods. But if anyone can post solutions for these (as step-by-step as you can get please!!!) that would be very much appreciated.

Thanks again.

2. Apr 16, 2004

### matt grime

I'd prefer you to think it up yourself: the two kinds of prime you're asked to consider are of the form given in the questio. consider whether you can deduce anything about the decomposition there, such as if anything is divisible by 2,4, or so on.