mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Basic Number Theory 12: sums of two squares (https://www.mersenneforum.org/showthread.php?t=21829)

 Nick 2016-12-11 11:30

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}$$.

[U]Proposition 60[/U]
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.

[U]proof[/U]
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.

[U]Proposition 61[/U]
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}$$.

[U]proof[/U]
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.

[U]Theorem 62[/U]
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$$.

[U]proof[/U]
(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}$$). ∎

[U]Example[/U]
All Mersenne primes remain prime in the Gaussian integers.

[U]Propostion 63[/U]
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$$.

[U]proof[/U]
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 [B]order[/B] 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.

[U]Theorem 64[/U]
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.

[U]proof[/U]
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. ∎

[U]Exercises[/U]
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$$.

 All times are UTC. The time now is 01:08.