Interesting problem from a Putnam student

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

 

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

 

[tacman]

It's great that you are already preparing for the Putnam exam and seeking help with challenging problems. Number theory can definitely be a tricky subject, but with practice and guidance, you will be able to tackle these types of problems confidently.

For the first part of the problem, we want to show that every prime one more than a multiple of 8 can be written in the form x^2 + 16y^2. Let's start by considering the theorem given in the problem statement: for a prime p>2, p=x^2+y^2 if and only if p is one more than a multiple of 4. We can rewrite this as p-1 = x^2+y^2.

Now, let's think about the numbers that are one more than a multiple of 8. These numbers can be written as 8k+1, where k is any integer. Using this, we can rewrite p-1 as:

p-1 = (8k+1)-1

= 8k

= 4(2k)

Since 2k is an integer, we can let it equal y^2 in our original equation, giving us:

p-1 = x^2 + y^2

= x^2 + 4(2k)

= x^2 + 16k

= x^2 + 16y^2

Therefore, we have shown that every prime one more than a multiple of 8 can be written in the form x^2 + 16y^2.

For the second part of the problem, we want to show that every prime five more than a multiple of 8 can be written in the form (2x+y)^2 + 4y^2. Again, let's start by considering the theorem given in the problem statement. We know that for a prime p>2, p=x^2+y^2 if and only if p is one more than a multiple of 4. We can rewrite this as p-1 = x^2+y^2.

Now, let's think about the numbers that are five more than a multiple of 8. These numbers can be written as 8k+5, where k is any integer. Using this, we can rewrite p-1 as:

p-1 = (8k+5)-1

= 8k+4

= 4(2k+1