A diophantine puzzle for students

[mathwonk]

a diophantine puzzle for abstract algebra students

A Diophantine Puzzle

We give an application of ring theoretic methods to study a classical problem: which primes p in Z are sums of two squares? Trial and error suggests that the answer is p = 2 = 1^2+1^2, and those p which are congruent to 1(mod 4), such as 5 = 1^2+2^2, 13 = 2^2+3^2, 17 = 1^2+4^2, 29 = 5^2+2^2, 37 = 6^2+1^2, 41 = 5^2+4^2, 53 = 2^2+7^2,...

Assume the elementary fact from number theory that x^2+1 has roots in Z/p for precisely such p. Can we make a link between these two problems? I.e. can we prove somehow that p is a sum of two squares iff X^2+1 has roots mod p? Consider the following argument:
Notice that if p=a^2+b^2, then using complex numbers we get p = (a+bi)(a-bi), so p is no longer prime in the ring Z. Conversely, if p = (a+bi)(c+di) in Z then taking absolute values on both sides and squaring, we get p^2 = (a^2+b^2)(c^2+d^2), and by uniqueness of prime factorization in Z, there are only two prime factors on the right, both equal to p, hence p = a^2+b^2. Thus a prime p in Z is no longer prime in Z iff p is a sum of two squares.

Now introduce (Z/p) as follows: Since Z/(p) isom to (Z/p) isom to (Z/p)[X]/(X^2+1), then p is a sum of two squares iff p not prime in Z iff (Z/p) is not a domain iff X^2+1 is not prime in (Z/p)[X] iff X^2+1 has roots mod p iff p = 2 or p cong to 1(mod 4). Ok?

Now consider:
Puzzle: If we use these ideas to analyze the equation X^2+5Y^2 = p, we seem to get that p = a^2+5b^2 for some a,b iff p is not prime in Z[sqrt(-5)] iff (Z/p)[sqrt(-5)] not a domain iff X^2+5 not prime in (Z/p)[X] iff X^2+5 has roots mod p. But what about p = 3? Then X = 1 is a root of X^2+5 (mod 3), but obviously X^2+5Y^2 = 3 has no integral solution. What gives?

 

[mathwonk]

the question about finding solutions of x^2 + x + 1, encouraged me to challenge again with the little problem above.

 

[robert Ihnot]

I wonder about this: Mthwonk: can we prove somehow that p is a sum of two squares iff X^2+1 has roots mod p?
The fact that a^2+b^2 ==0 Mod(p), does not tell us that there is a minimal solution such that m^2+n^2=p.

 

[mathwonk]

so you want to assume a^2 + b^2 is divisible by p, where a,b, are minimal in some sense, and deduce that in fact a^2 + b^2 = p.

well how to do it?

and if you can do it here, then why does it fail for the second case? I.e. why does the fact that X^2 + 5Y^2 ==0 (mod3), does have the solution (1,1), not yield a more minimal solution such that X^2 + Y^2 = 3?

 

[robert Ihnot]

Regarding a^2+b^2 = p, well, when I used "Theory of Numbers" by Harriet Griffin, it was called Gauss's proof and consisted of using inequality to sharpen the result.

You can look at: http://www.maths.lancs.ac.uk/department/study/years/third/modules/math328/ntss.pdf under "Sum of Two Squares.

Then if you read further there is a second method involving the Gaussian integers, but you still have to use inequality.

Obviously X^2+5Y^2 is going to exceed 3 for Y>0. After all, consider:
X^2+29^2 ==0 Mod 5.

 

[mathwonk]

i am asking for your argument. are you saying i need to go read it on that site?

I realize the result is false for the second equation, I am asking how your approach fails for that case. i.e. if your approach is valid, then it should fail when the result is false.

there is a subtle but key distinction between those two exampels, which you have not mentioned except peripherally.

I.e. gaussian integers are certainly involved in the first case.

my original question was whether you followed my argument above for the first case, and whether you could see why the same argument word for word, must fail for the second case.

here is that argument again:

"Since Z/(p) isom to (Z/p) isom to (Z/p)[X]/(X^2+1),

then p is a sum of two squares

iff p not prime in Z

iff (Z/p) is not a domain

iff X^2+1 is not prime in (Z/p)[X]

iff X^2+1 has roots mod p."


OK, thanks, I read that proof at least quickly. My question is simply this: if you can understand some proof of this theorem, can you also see where your proof breaks down in attempting to use it on the second false result?

I.e. the point is not merely to prove the theorem of fermat, but to understand what lies behind the theorem.

i have given a somewhat glib description above of one proof, but in a way that apprently makes it very hard to see why it should not also work on the second case. Since the second case is false, it must fail, but where?

I.e. I am challenging the reader to understand the proof above, which no doubt is also due to gauss. I have spelled out explicitly the steps. which one fails?

 

[robert Ihnot]

By the time we get to the Gaussian integers, we have to define the nature of a prime, and the natue of units, and we have to consider a Euclidean domain. That you have not gone into.

 

[mathwonk]

you are right. i am assuming the solver of this puzzles know about these things. You have put your finger on exactly the key concept. the definition fo the word prime.

this is what differs for the two cases. the distinction between "prime" and "irreducible".

this is very subtle to students. so far, no students, only professors, have observed this point in this puzzle. should I assume you are the latter?

 

[mathwonk]

I once claimed on this site that questions were more in demand in mathematics than answers. I was immediately contradicted by someone, but I submit that this site itself supports my thesis. I.e. there are not that many questions coming in, compared to the fairly large number of answers.

Most threads attract dozens of responses, and I find myself hovering over the site waiting for someone to ask something of interest. This site is too addictive. I have even started asking questions like this whose answers I already know, just for fun. see also my poser on "line geometry" in general math.

 

[Hurkyl]

I haven't had a chance to really look at it until now. I'm familiar with this particular number field... 2*3 = (1+√-5)(1-√-5) is the canonical example of something not a unique factorization domain, isn't it?

It works for the form m^2 + n^2 becaue Z[ i ] is a UFD. If p is irreducible in Z[ i ], then if any element np of (p) factors into jk, p must divide one of j or k. Thus (p) is a prime ideal.

And, of course, the example above shows that Z[ √-5 ] is not a UFD. In particular, (3) isn't prime because 6 is an element, and we have an example of two numbers not in (3) whose product is 6.

 

[mathwonk]

yes that is exactly the point. the properties of being "prime" and "irredudible" differ in a no unqiue factorization domain.

Thus the step in the argument above where a non prime polynomial is assumed to also be reducible, is false. (and you have given the relevant counterexample.)