mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-12-11, 11:30   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24×89 Posts
Default Basic Number Theory 12: sums of two squares

Which positive integers can be written as the sum of 2 squares (i.e. in the form \(a^2+b^2\) where \(a,b\) are also integers)?
This time, we use what we have learned about the Gaussian integers to answer this question about the rational (ordinary) integers.

For any real (or complex) numbers \(a,b\) with \(a\neq 0\), there is only one number \(x\) satisfying the equation \(ax+b=0\).
For any numbers \(a,b,c\) with \(a\neq 0\), there are at most 2 distinct values of \(x\) for which \(ax^2+bx+c=0\). (You may know a formula for them.)
For any numbers \(a,b,c,d\) with \(a\neq 0\), there are at most 3 distinct values of \(x\) such that \(ax^3+bx^2+cx+d=0\), and so on.
This holds whether we work in \(\mathbb{Z},\mathbb{Z}[i],\mathbb{Q}, \mathbb{R}\) or \(\mathbb{C}\).
It also works in the integers modulo a prime number, but it need not be true in the integers modulo \(n\) if \(n>1\) but not prime.
For example, the equation \(x^2-\bar{1}=\bar{0}\) has 4 distinct solutions in the integers modulo 8: \(\bar{1},\bar{3},\bar{5}\) and \(\bar{7}\) (or equivalently \(\pm\bar{1},\pm\bar{3}\)).
This stems from the fact that there are zero divisors in the integers modulo 8, e.g. \(\bar{2}\times\bar{4}=\bar{0}\).

Proposition 60
Let \(R\) be a set of numbers including 1 which is closed under subtraction and multiplication and does not contain any zero divisors.
Let \(n\) be a positive integer, and \(a_0,a_1,a_2,\ldots,a_n\) elements of \(R\) with \(a_n\neq 0\).
Define \(Z=\{x\in R:a_0+a_1x+a_2x^2+\ldots +a_nx^n=0\}\).
Then \(Z\) contains at most \(n\) distinct elements.

proof
Induction on \(n\).
In the case \(n=1\), for any \(x,y\in Z\) we have \(a_0+a_1x=0=a_0+a_1y\) so \(a_1(x-y)=0\).
As \(a_1\) and \(x-y\) are elements of \(R\), which has no zero divisors, and \(a_1\neq 0\), it follows that \(x-y=0\) and therefore \(x=y\).
So all elements of \(Z\) are equal, hence \(Z\) contains at most 1 element.
Take any integer \(N>1\) and suppose the proposition holds for all integers \(n<N\).
For the case \(n=N\), take any \(c\in Z\).
Then \(a_0+a_1c+a_2c^2+\ldots +a_nc^n=0\) and, for all \(x\in Z\), \(a_0+a_1x+a_2x^2+\ldots +a_nx^n=0\) so (subtracting)
\[ a_1(x-c)+a_2(x^2-c^2)+a_3(x^3-c^3)+\ldots +a_n(x^n-c^n)=0. \]
Now
\[
\begin{eqnarray*}
x^2-c^2 & = & (x-c)(x+c) \\
x^3-c^3 & = & (x-c)(x^2+cx+c^2) \\
x^4-c^4 & = & (x-c)(x^3+cx^2+c^2x+c^3) \\
& \vdots & \\
x^n-c^n & = & (x-c)(x^{n-1}+cx^{n-2}+c^2x^{n-3}+\ldots +c^{n-2}x+c^{n-1})
\end{eqnarray*}
\]
so we may replace all of these in the above equation and simplify, getting a new equation of the form
\[ (x-c)(b_0+b_1x+b_2x^2+\ldots +b_{n-1}x^{n-1})=0 \]
where \(b_0,b_1,\ldots,b_{n-1}\in R\).
Let \(Z'=\{x\in R:b_0+b_1x+b_2x^2+\ldots +b_{n-1}x^{n-1}=0\}\).
As \(R\) contains no zero divisors, it follows for all \(x\in Z\) that \(x=c\) or \(x\in Z'\).
And by our assumption there are at most \(n-1\) distinct elements in \(Z'\) hence there are at most \(n\) distinct elements in \(Z\).
The proposition follows by mathematical induction. ∎

We formed the Gaussian integers by extending the integers to include square roots of -1.
Using the above we can show that, for certain prime numbers \(p\), the integers modulo \(p\) already have square roots of -1.

Proposition 61
Let \(p\in\mathbb{Z}\) be a prime number such that \(p\equiv 1\pmod{4}\).
Then there exists \(u\in\mathbb{Z}\) such that \(u^2\equiv -1\pmod{p}\).

proof
We have \(p=4m+1\) for some positive integer \(m\).
For each integer \(a\) from 1 to \(p-1\) inclusive, \(a^{p-1}\equiv 1\pmod{p}\) by Corollary 40, so the equation \(x^{4m}-1=0\) has \(p-1=4m\) distinct solutions in the integers modulo \(p\).
Now \(x^{4m}-1=(x^{2m})^2-1^2=(x^{2m}-1)(x^{2m}+1)\) so, for any \(x\in\mathbb{Z}/p\mathbb{Z}\), if \(x^{4m}-1=0\) then \(x^{2m}-1=0\) or \(x^{2m}+1=0\) (as there are no zero divisors).
But by proposition 60 above there are at most \(2m\) distinct solutions in the integers modulo \(p\) for the equation \(x^{2m}-1=0\), and \(4m-2m=2m\geq 2\) so there exists \(x\in\mathbb{Z}/p\mathbb{Z}\) such that \(x^{2m}+1=0\).
Putting \(u=x^m\), it follows that \(u^2=-1\) in the integers modulo \(p\). ∎

We can now determine what happens to prime numbers when we move from working in the integers to working in the Gaussian integers.

Theorem 62
Let \(p\in\mathbb{Z}\) be a prime number.
(i) If \(p=2\) then the prime factorization of \(p\) in \(\mathbb{Z}[i]\) is \(2=-i(1+i)^2\).
(ii) If \(p\equiv 3\pmod{4}\) then \(p\) remains prime in \(\mathbb{Z}[i]\).
(iii) If \(p\equiv 1\pmod{4}\) then the prime factorization of \(p\) in \(\mathbb{Z}[i]\) is \(p=q\bar{q}\) for some prime \(q\in\mathbb{Z}[i]\),with \(\bar{q}\) also prime but not an associate of \(q\).

proof
(i) Direct calculation shows that \(-i(1+i)^2=2\), and \(N(1+i)=2\) so \(1+i\) is a Gaussian prime by propostion 57.
(ii) If \(p\) is not prime in \(\mathbb{Z}[i]\) then \(p=q\bar{q}\) for some prime Gaussian integer \(q\) by propostion 58.
And \(q=a+bi\) for some integers \(a,b\) so \(p=a^2+b^2\).
But, for all integers \(a,b\), \(a^2+b^2\bmod{4}\) is 0, 1 or 2 so \(p\not\equiv 3\pmod{4}\).
Hence if \(p\equiv 3\pmod{4}\) then \(p\) remains prime in \(\mathbb{Z}[i]\).
(iii) Suppose \(p\equiv 1\pmod{4}\).
By proposition 61, there exists \(u\in\mathbb{Z}\) such that \(u^2\equiv -1\pmod{p}\).
So, in \(\mathbb{Z}[i]\), \(p|u^2+1=(u-i)(u+i)\) but \(p\) does not divide either of \(u-i,u+i\).
(For all integers \(a,b\), if \(p(a+bi)=u+i\) then \(pb=1\) so \(p=\pm 1\), a CONTRADICTION.)
Hence \(p\) does not satisfy the defining property of primes in \(\mathbb{Z}[i]\), and by proposition 58 we have \(p=q\bar{q}\) for some prime Gaussian integer \(q\).
Its complex conjugate \(\bar{q}\) is also prime by exercise 52, and not an associate of \(q\) by exercise 55 below (since \(p\) is prime in \(\mathbb{Z}\)). ∎

Example
All Mersenne primes remain prime in the Gaussian integers.

Propostion 63
Let \(p\in\mathbb{Z}\) be a prime number with \(p\equiv 1\pmod{4}\).
Then there exist unique postive integers \(a,b\) with \(a<b\) such that \(p=a^2+b^2\).

proof
EXISTENCE
By theorem 62 part (iii) there exists a prime Gaussian integer \(q\) such that \(p=q\bar{q}\).
So \(q=c+di\) for some integers \(c,d\) and \(p=(c+di)(c-di)=c^2+d^2\).
If \(c=0\) or \(d=0\) then \(p\) is not prime, and if \(c^2=d^2\) then \(p=2c^2\) which is not prime either.
But \(p\) is prime, so \(c,d\) are both non-zero with \(c^2\neq d^2\).
If \(c^2<d^2\), putting \(a=|c|,b=|d|\) suffices.
And if \(c^2>d^2\), then putting \(a=|d|,b=|c|\) is sufficient.

UNIQUENESS
Take any positive integers \(a,b,c,d\) with \(a<b\) and \(c<d\) and suppose that \(p=a^2+b^2=c^2+d^2\).
Then, in \(\mathbb{Z}[i]\), \(p=(a+bi)(a-bi)\) and \(p=(c+di)(c-di)\).
But \(p=q\bar{q}\) is the unique factorization of \(p\) into primes in \(\mathbb{Z}[i]\) so \(a+bi\sim c+di\) or \(a+bi\sim c-di\).
If \(a+bi\sim c-di\) then \(a+bi=v(c-di)\) for some unit \(v\in\mathbb{Z}[i]\), and it follows that \(v=i\) (any other choice gives \(a<0\) or \(b<0\)).
So \(a<b=c<d=a\), a CONTRADICTION.
Thus \(a+bi\sim c+di\) and, in the same way, \(a=c\) and \(b=d\). ∎

For an integer \(n\) and a prime number \(p\), we define the order of \(n\) at \(p\) to be the largest non-negative integer \(r\) such that \(p^r|n\).
For example, the order of 18 at 3 is 2, while the order of 18 at 5 is 0.

Theorem 64
Let \(n\) be a positive integer. Then \(n=a^2+b^2\) for some integers \(a,b\) if and only if the following condition holds:
for all prime numbers \(p\) such that \(p\equiv 3\pmod{4}\) and \(p\) divides \(n\), the order of \(n\) at \(p\) is even.

proof
Suppose \(n=a^2+b^2\) for some integers \(a,b\), and take any prime number \(p\) such that \(p\equiv 3\pmod{4}\) and \(p\) divides \(n\).
Then, in the integers modulo \(p\), we have \(\bar{a}^2+\bar{b}^2=\bar{0}\).
Suppose\(\bar{b}\neq\bar{0}\).
Then \(\bar{b}\) is a unit (by proposition 32) i.e. \(\bar{b}\bar{c}=\bar{1}\) for some integer \(c\).
But then \(\overline{ac}^2=-\bar{1}\) so \(\overline{ac}^2\) has order 4 in the unit group of the integers modulo \(p\) hence 4 divides \(\phi(p)=p-1\) by Corollary 39, a CONTRADICTION.
Thus \(\bar{b}=\bar{0}\), and \(\bar{a}^2+\bar{b}^2=\bar{0}\) so \(\bar{a}=\bar{0}\) as well (since there are no zero divisors).
Hence \(p|a\) and \(p|b\), so \(pa_1=a\) and \(pb_1=b\) for some integers \(a_1,b_1\) and therefore \(n=p^2(a_1^2+b_1^2)\).
If \(p\) divides \(a_1^2+b_1^2\) then, by the same argument with \((a_1,b_1)\) instead of \((a,b)\), we have \(a_1^2+b_1^2=p^2(a_2^2+b_2^2)\) for some integers \(a_2,b_2\), and therefore \(n=p^4(a_2^2+b_2^2)\).
Continuing in this way, we eventually get \(n=p^{2m}(a_m^2+b_m^2)\) for some positive integer \(m\) and some integers \(a_m,b_m\) such that \(p\) does not divide \(a_m^2+b_m^2\) (as the order of \(n\) at \(p\) is finite).
Hence the order of \(n\) at \(p\) is \(2m\), which is even.

For the converse, suppose that, for all prime numbers \(p\) dividing \(n\) with \(p\equiv 3\pmod{4}\), the order of \(n\) at \(p\) is even.
Then \(n=r^2p_1p_2\ldots p_m\) for some integers \(r\geq 1,m\geq 0\) and some distinct prime numbers \(p_1,p_2,\ldots,p_m\) (the primes at which the order of \(n\) is odd).
Thus, for each \(i\in\{1,2,\ldots,m\}\), either \(p_i=2\) or \(p_i\equiv 1\pmod{4}\).
Induction on \(m\).
In the case \(m=0\), we have \(n=r^2+0^2\).
Take any integer \(M\geq 1\) and suppose the theorem holds in all cases with \(m<M\).
In the case \(m=M\), by our assumption, \(r^2p_1p_2\ldots p_{m-1}=a^2+b^2\) for some integers \(a,b\).
If \(p_m\equiv 1\pmod{4}\) then, by proposition 63, \(p_m=c^2+d^2\) for some integers \(c,d\), and otherwise \(p_m=2\) so putting \(c=d=1\) again gives \(p_m=c^2+d^2\). Hence
\[
\begin{eqnarray*}
n & = & (a^2+b^2)(c^2+d^2) = a^2c^2+a^2d^2+b^2c^2+b^2d^2 \\
& = & (ac)^2+2acbd+(bd)^2+(ad)^2-2adbc+(bc)^2 \\
& = & (ac+bd)^2+(ad-bc)^2
\end{eqnarray*}
\]
a sum of two squares. The result follows by mathematical induction. ∎


Exercises
55. Show for all Gaussian integers \(z\) that, if \(z\) and \(\bar{z}\) are associates then the integer \(z\bar{z}\) is not a prime number.
56. Factorize \(7+100i\) into a product of prime Gaussian integers.
57. Let \(f:\mathbb{Z}[i]\rightarrow\mathbb{Z}/13\mathbb{Z}\) be the function given by \(f(a+bi)=a+5b\). Show for all \(z,w\in\mathbb{Z}[i]\) that \(f(z+w)=f(z)+f(w)\) and \(f(zw)=f(z)f(w)\).
Let \(I=\{z\in\mathbb{Z}[i]:f(z)=0\}\). Prove that \(I\) is an ideal of \(\mathbb{Z}[i]\) and find a Gaussian integer \(w\) for which \(I=w\mathbb{Z}[i]\).
58. Let \(r,s\) be coprime integers and \(p\) a prime number.
Show that, if \(p|r^2-s^2\) and \(p|r^2+s^2\) then \(p=2\).
Nick is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Basic Number Theory 20: polynomials Nick Number Theory Discussion Group 5 2017-04-25 14:32
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42
Basic Number Theory 4: a first look at prime numbers Nick Number Theory Discussion Group 6 2016-10-14 19:38

All times are UTC. The time now is 12:07.

Sun Aug 9 12:07:42 UTC 2020 up 23 days, 7:54, 2 users, load averages: 1.72, 1.65, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.