mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Basic Number Theory 11: Gaussian primes (https://www.mersenneforum.org/showthread.php?t=21799)

 Nick 2016-12-03 11:42

Basic Number Theory 11: Gaussian primes

1 Attachment(s)
We are looking at the set $$\mathbb{Z}[i]$$ of all Gaussian integers, which are the numbers expressible in the form $$a+bi$$ where $$a,b$$ are integers (and $$i^2=-1$$).
To gain insight into this number system, we defined the norm $$N(z)$$ of a Gaussian integer $$z=a+bi$$ to be the integer $$N(z)=a^2+b^2$$.

The units of $$\mathbb{Z}[i]$$ are precisely the Gaussian integers $$z$$ with $$N(z)=1$$ (exercise 49).
And if $$a^2+b^2=1$$ then $$a=\pm 1$$ with $$b=0$$ or $$a=0$$ with $$b=\pm 1$$ so the units are precisely the numbers $$1,i,-1,-i$$.

Our first goal this time is to prove that any non-zero Gaussian integer can be written as a product of Gaussian primes in an essentially unique way.
Our train of thought will echo what we did for the ordinary integers, adjusted where necessary.

For Gaussian integers $$z,w$$, we say $$z$$ is an [B]associate[/B] of $$w$$ and write $$z\sim w$$ if $$z=uw$$ for some unit $$u$$ of $$\mathbb{Z}[i]$$.

[U]Example[/U]
$$1+i\sim 1-i$$ since $$1+i=i(1-i)$$.

[U]Proposition 50[/U]
The relation $$\sim$$ defined above is an equivalence relation on $$\mathbb{Z}[i]$$.

[U]proof[/U]
Take any Gaussian integers $$z,w,t$$.
As $$z=1z$$ and $$1$$ is a unit of $$\mathbb{Z}[i]$$, we have $$z\sim z$$.
If $$z\sim w$$ then $$z=uw$$ for some unit $$u$$ and (by the definition of a unit) $$vu=1$$ for some $$v\in\mathbb{Z}[i]$$ so $$w=vuw=vz$$ hence $$w\sim z$$ too.
Finally, if $$z\sim w$$ and $$w\sim t$$ then there exist units $$u,v$$ in $$\mathbb{Z}[i]$$ such that $$z=uw$$ and $$w=vt$$. By proposition 18, $$uv$$ is also a unit and $$z=uvt$$ so $$z\sim t$$. ∎

[U]Proposition 51[/U]
For all Gaussian integers $$z,w$$, if $$z|w$$ and $$w|z$$ then $$w$$ is an associate of $$z$$.

[U]proof[/U]
If $$z|w$$ and $$w|z$$ then $$zt=w$$ and $$wt'=z$$ for some Gaussian integers $$t,t'$$, so $$ztt'=z$$.
If $$z=0$$ then $$w=zt=0=1z$$ so $$w\sim z$$, and if $$z\neq 0$$ then $$tt'=1$$ so $$t$$ is a unit in $$\mathbb{Z}[i]$$ with $$w=zt$$ and therefore $$w\sim z$$. ∎

An [B]ideal[/B] of $$\mathbb{Z}[i]$$ is a set $$I$$ of Gaussian integers which contains 0, is closed under subtraction, and also satisfies the following condition:
for all Gaussian integers $$z,w$$, if $$z\in I$$ then $$zw\in I$$ too.

[U]Proposition 52[/U]
Let $$I,J$$ be ideals of $$\mathbb{Z}[i]$$.
Then $$I+J$$ is also an ideal of $$\mathbb{Z}[i]$$.

[U]proof[/U]
By definition, $$I+J=\{i+j:i\in I,j\in J\}$$.
As $$I$$ and $$J$$ are ideals, they each contain zero so $$0=0+0\in I+J$$.
For any $$z,z'\in I+J$$, $$z=i+j$$ and $$z'=i'+j'$$ for some $$i,i'\in I$$ and some $$j,j'\in J$$.
As $$I$$ and $$J$$ are ideals, they are closed under subtraction so $$i-i'\in I$$ and $$j-j'\in J$$ and therefore $$z-z'=(i+j)-(i'+j')=(i-i')+(j-j')\in I+J$$.
Thus $$I+J$$ is closed under subtraction as well.
Take any Gaussian integers $$z,w$$ and suppose $$z\in I+J$$.
Then $$z=i+j$$ for some $$i\in I$$ and some $$j\in J$$.
As $$I$$ and $$J$$ are ideals, we have $$iw\in I$$ and $$jw\in J$$ hence $$zw=(i+j)w=iw+jw\in I+J$$. ∎

[U]Notation[/U]
For any Gaussian integer $$w$$, we define
$$w\mathbb{Z}[i]=\{wz:z\in\mathbb{Z}[i]\}$$.

[U]Example[/U]
$(1+i)\mathbb{Z}[i]=\{(1+i)(a+bi):a,b\in\mathbb{Z}\} =\{m(1+i)+n(1-i):m,n\in\mathbb{Z}\}.$
[ATTACH]15220[/ATTACH]

[U]Proposition 53[/U]
Let $$w$$ be a Gaussian integer.
Then $$w\mathbb{Z}[i]$$ is an ideal of $$\mathbb{Z}[i]$$ containing $$w$$,
and if $$I$$ is any ideal of $$\mathbb{Z}[i]$$ containing $$w$$ then $$w\mathbb{Z}[i]\subset I$$.

[U]proof[/U]
We have $$0=w\cdot 0\in w\mathbb{Z}[i]$$.
For any $$z,z'\in w\mathbb{Z}[i]$$, $$z=wt$$ and $$z'=wt'$$ for some Gaussian integers $$t,t'$$.
As $$t-t'$$ is also a Gaussian integer, it follows that $$z-z'=w(t-t')\in w\mathbb{Z}[i]$$.
Hence $$w\mathbb{Z}[i]$$ contains 0 and is closed under subtraction.
Now take any Gaussian integers $$z,z'$$ and suppose $$z\in w\mathbb{Z}[i]$$. Then $$z=wt$$ for some Gaussian integer $$t$$.
As $$tz'$$ is also a Gaussian integer, it follows that $$zz'=wtz'\in w\mathbb{Z}[i]$$.
This completes the proof that $$w\mathbb{Z}[i]$$ is an ideal of $$\mathbb{Z}[i]$$, and $$w=w\cdot 1\in w\mathbb{Z}[i]$$ so this ideal contains $$w$$.

Take any ideal $$I$$ of $$\mathbb{Z}[i]$$ with $$w\in I$$.
For any $$z\in w\mathbb{Z}[i]$$, $$z=wt$$ for some Gaussian integer $$t$$.
As $$w\in I$$ and $$I$$ is an ideal, it follows that $$wt\in I$$ too, i.e. $$z\in I$$.
This holds for all $$z\in w\mathbb{Z}[i]$$ hence $$w\mathbb{Z}[i]\subset I$$. ∎

We can use division with remainder in $$\mathbb{Z}[i]$$ (proposition 49 from last time) to show that every ideal of $$\mathbb{Z}[i]$$ has this form:

[U]Proposition 54[/U]
Let $$I$$ be an ideal of $$\mathbb{Z}[i]$$.
Then there exists a Gaussian integer $$w$$ such that $$I=w\mathbb{Z}[i]$$.

[U]proof[/U]
As $$I$$ is an ideal, we have $$0\in I$$.
If this is the only element of $$I$$ then putting $$w=0$$ suffices.
Otherwise, $$I$$ contains non-zero elements, and we may choose $$w\in I$$ with $$w\neq 0$$ such that the positive integer $$N(w)$$ is as small as possible.
By proposition 53, $$w\mathbb{Z}[i]\subset I$$.
Conversely, for any $$z\in I$$, there exist Gaussian integers $$q,r$$ such that $$z=qw+r$$ and $$N(r)<N(w)$$ by proposition 49 (since $$w\neq 0$$).
The ideal $$I$$ contains $$w$$ so it contains $$qw$$ as well.
It also contains $$z$$ and is closed under subtraction, so $$r=z-qw\in I$$.
But $$N(r)<N(w)$$ and we chose $$w$$ with $$N(w)$$ as small as possible (amongst the non-zero elements of $$I$$). It follows that $$r=0$$ and therefore $$z=wq\in w\mathbb{Z}[i]$$.
This holds for all $$z\in I$$, so $$I\subset w\mathbb{Z}[i]$$.
We have shown that $$w\mathbb{Z}[i]\subset I$$ and $$I\subset w\mathbb{Z}[i]$$ so the sets $$I$$ and $$w\mathbb{Z}[i]$$ contain precisely the same elements, making them equal. ∎

We call a Gaussian integer $$p$$ [B]irreducible[/B] if it has the following 2 properties:
[LIST=1][*]$$p$$ is not a unit in $$\mathbb{Z}[i]$$;[*]for all Gaussian integers $$z,w$$, if $$p=zw$$ then $$z$$ or $$w$$ is a unitin $$\mathbb{Z}[i]$$.[/LIST]We call a Gaussian integer $$p$$ [B]prime[/B] if it has the following 2 properties:
[LIST=1][*]$$p$$ is non-zero and not a unit in $$\mathbb{Z}[i]$$;[*]for all Gaussian integers $$z,w$$, if $$p|zw$$ then $$p|z$$ or $$p|w$$.[/LIST]Proving that every prime is irreducible is quite easy. Proving that every irreducible Gaussian integer is also prime is harder (there exist other number systems in which this is not true, which is why the properties have distinct names).
We do both in the following proposition.

[U]Proposition 55[/U]
Let $$p$$ be a Gaussian integer.
Then $$p$$ is prime if and only if $$p$$ is irreducible.

[U]proof[/U]
Suppose $$p$$ is prime. Then $$p$$ is not a unit in $$\mathbb{Z}[i]$$.
Take any Gaussian integers $$z,w$$, and suppose $$p=zw$$.
Then $$p|zw$$ and $$p$$ is prime so $$p|z$$ or $$p|w$$.
If $$p|z$$ then $$pt=z$$ for some Gaussian integer $$t$$.
Thus $$ptw=p$$ and $$p\neq 0$$ (as it is prime) so $$tw=1$$ making $$w$$ a unit.
Similarly if $$p|w$$ then $$z$$ is a unit. Hence $$p$$ is irreducible.

Suppose instead that $$p$$ is irreducible.
Then $$p$$ is not a unit in $$\mathbb{Z}[i]$$, and $$p\neq 0$$ (0 is not a unit and 0x0=0 so 0 is not irreducible).
Take any Gaussian integers $$z,w$$ and suppose that $$p|zw$$ but that $$p$$ does not divide $$z$$.
By proposition 52, $$p\mathbb{Z}[i]+z\mathbb{Z}[i]$$ is an ideal of $$\mathbb{Z}[i]$$ so, by proposition 54, it equals $$d\mathbb{Z}[i]$$ for some Gaussian integer $$d$$.
Thus $$p=p+0\in p\mathbb{Z}[i]+z\mathbb{Z}[i]=d\mathbb{Z}[i]$$ so $$p=dt$$ for some Gaussian integer $$t$$.
And $$p$$ is irreducible (by assumption) so $$d$$ or $$t$$ is a unit.
Suppose $$t$$ is a unit. Then $$tu=1$$ for some Gaussian integer $$u$$, so $$pu=d$$.
And $$z=0+z\in p\mathbb{Z}[i]+z\mathbb{Z}[i]=d\mathbb{Z}[i]$$ so $$z=dt'$$ for some Gaussian integer $$t'$$.
Thus $$put'=dt'=z$$ so $$p|z$$, a CONTRADICTION.
It follows that $$d$$ is a unit, i.e. $$dv=1$$ for some Gaussian integer $$v$$.
Thus $$1\in d\mathbb{Z}[i]=p\mathbb{Z}[i]+z\mathbb{Z}[i]$$ so $$1=px+zy$$ for some Gaussian integers $$x,y$$ and therefore $$w=wpx+wzy$$.
As $$p|zw$$ we have $$p|wzy$$, and $$p|wpx$$ too, hence $$p|w$$.
This completes the proof that $$p$$ is prime. ∎

We are now in a position to show that any Gaussian integer can be written as a product of prime (i.e. irreducible) Gaussian integers, and that this product is unique if we disregard the order in which the factors are written and view associates as being equivalent.

[U]Theorem 56[/U]
(i) For all Gaussian integers $$z\neq 0$$, there exist a unit $$u$$ of $$\mathbb{Z}[i]$$, a non-negative integer $$n$$, and irreducible Gaussian integers $$p_1,p_2,\ldots,p_n$$ such that $$z=up_1p_2\ldots p_n$$.
(ii) If $$z=vq_1q_2\ldots q_m$$ as well, where $$v$$ is a unit of $$\mathbb{Z}[i]$$, $$m$$ a non-negative integer, and $$q_1,q_2,\ldots q_m$$ are irreducible Gaussian integers, then $$m=n$$ and (after renumbering if necessary) $$q_i\sim p_i$$ for each $$i\in\{1,2,\ldots,n\}$$.

[U]proof[/U]
(i) We use induction on $$N(z)$$. By proposition 48(i), $$N(z)>0$$.
In the case $$N(z)=1$$, $$z$$ is a unit (exercise 49) so putting $$u=z$$ and $$n=0$$ suffices.
Take any integer $$M>1$$ and suppose that (i) holds for all Gaussian integers $$z$$ with $$N(z)<M$$.
In the case $$N(z)=M$$, if $$z$$ is irreducible then we may set $$u=1,$$ $$n=1$$ and $$p_1=z$$.
Otherwise $$z$$ is not irreducible but not a unit either (since $$N(z)>1$$) so $$z=wt$$ for some Gaussian integers $$w,t$$, both not units.
Thus $$N(w)>1$$ and $$N(t)>1$$, and $$N(z)=N(w)N(t)$$ by proposition 48(ii) so $$N(w)<N(z)$$ and $$N(t)<N(z)$$.
By our assumption, $$w=up_1p_2\ldots p_m$$ for some unit $$u$$, integer $$m\geq 0$$ and some irreducible Gaussian integers $$p_1,p_2,\ldots p_m$$. Similarly, $$t=vp_{m+1}p_{m+2}\ldots p_n$$ for some unit $$v$$, integer $$n\geq m$$ and irreducible Gaussian integers $$p_{m+1},p_{m+2},\ldots p_{n}$$.
And $$uv$$ is also a unit (by proposition 18) so $$z=(uv)p_1p_2\ldots p_n$$ has the required form.
By induction, every non-zero Gaussian integer $$z$$ can be written in this way.

(ii) Suppose $$z=up_1p_2\ldots p_n$$ and $$z=vq_1q_2\ldots q_m$$ where $$u,v$$ are units, $$m,n$$ non-negative integers and $$p_1,\ldots,p_n,q_1,\ldots,q_m$$ irreducible Gaussian integers.
We use induction on $$n$$.
In the case $$n=0$$, $$z$$ is a unit. If $$m>0$$ then $$q_1$$ divides a unit so is a unit itself, and therefore not irreducible, a CONTRADICTION.
Hence $$m=0$$ too.
Take any integer $$M>0$$ and suppose (ii) holds for all $$n<M$$.
In the case $$n=M$$, we have $$n>0$$ so $$p_n|vq_1q_2\ldots q_m$$, and $$p_n$$ is prime by proposition 55 so $$p_n$$ divides at least one of $$v,q_1,q_2,\ldots,q_m$$ (just as in lemma 14).
As $$p_n$$ is not a unit, it does not divide the unit $$v$$, therefore (renumbering if necessary) we may say that $$p_n$$ divides $$q_m$$.
Thus $$p_nt=q_m$$ for some Gaussian integer $$t$$.
But $$q_m$$ is irreducible and $$p_n$$ is not a unit (since it is irreducible too) so $$t$$ is a unit and $$q_m\sim p_n$$.
Thus $$up_1p_2\ldots p_{n-1}=tvq_1q_2\ldots q_{m-1}$$ and, by our assumption, it follows that $$m-1=n-1$$ and (after renumbering if necessary) $$q_i\sim p_i$$ for each $$i\in\{1,2,\ldots,n-1\}$$.
Hence $$m=n$$, and $$q_m\sim p_n$$ too so $$q_i\sim p_i$$ for each $$i\in\{1,2,\ldots,n\}$$.
By induction, (ii) holds for all $$n\geq 0$$. ∎

The ordinary integers (i.e. elements of $$\mathbb{Z}$$) are sometimes referred to as [B]rational integers[/B] in order to distinguish them from the Gaussian integers (or any other types of integers).
Similarly, the ordinary prime numbers are called the [B]rational primes[/B] if we need to avoid ambiguity with the prime Gaussian integers (or primes in any other number system).

We now have unique factorization in the Gaussian integers, just as we had in the rational integers.
But what are the prime Gaussian integers? And do rational prime numbers remain prime when we switch from $$\mathbb{Z}$$ to $$\mathbb{Z}[i]$$?

[U] Proposition 57[/U]
Let $$z$$ be a Gaussian integer for which $$N(z)$$ is a prime number (in $$\mathbb{Z}$$).
Then $$z$$ is prime (in $$\mathbb{Z}[i]$$).

[U] proof[/U]
As $$N(z)$$ is a prime number, we have $$N(z)>1$$ so $$z$$ is not a unit (exercise 49).
Take any Gaussian integers $$w,t$$ and suppose $$z=wt$$.
Then $$N(z)=N(w)N(t)$$ by proposition 48(ii) but $$N(z)$$ is a prime number so $$N(w)=1$$ or $$N(t)=1$$ and therefore $$w$$ or $$t$$ is a unit in $$\mathbb{Z}[i]$$.
Thus $$z$$ is an irreducible Gaussian integer, hence prime by proposition 55. ∎

[U] Example[/U]
$$1+i$$ and $$1-i$$ are prime Gaussian integers since $$N(1+i)=N(1-i)=2$$, which is a rational prime.

[U] Proposition 58[/U]
Let $$p\in\mathbb{Z}$$ be a prime number.
Then, in $$\mathbb{Z}[i]$$, either $$p$$ is prime or $$p=q\bar{q}$$ for some prime Gaussian integer $$q$$.

[U] proof[/U]
Suppose $$p$$ is not prime in the Gaussian integers, so also not irreducible (propostion 55).
As a prime number in $$\mathbb{Z}$$, $$p$$ is not one of the 4 units of $$\mathbb{Z}[i]$$ so $$p=qr$$ for some Gaussian integers $$q,r$$, both non-units.
Thus $$N(p)=N(q)N(r)$$ by proposition 48(ii) with $$N(q)>1$$ and $$N(r)>1$$.
But $$N(p)=p^2$$ (since $$p\in\mathbb{Z}$$) so it follows that $$N(q)=p$$, and $$q$$ is therefore a prime Gaussian integer by proposition 57.
And $$p=N(q)=|q|^2=q\bar{q}$$ by proposition 46. ∎

[U] Example[/U]
In the Gaussian integers, $$2=(1+i)(1-i)$$ so 2 is no longer prime.

[U] Proposition 59[/U]
Let $$p$$ be a prime Gaussian integer.
Then (i) there exists a prime number $$q\in\mathbb{Z}$$ such that $$p|q$$;
and (ii) either $$N(p)$$ is a prime number in $$\mathbb{Z}$$ or $$N(p)=q^2$$ for some prime number $$q\in\mathbb{Z}$$.

[U] proof[/U]
(i) As $$p\neq 0$$, we have $$N(p)\neq 0$$ by proposition 48(i) so $$N(p)=q_1q_2\ldots q_n$$ for some non-negative integer $$n$$ and prime numbers $$q_1,q_2,\ldots,q_n\in\mathbb{Z}$$.
And $$p\bar{p}=|p|^2=N(p)$$ by proposition 46 so $$p$$ divides $$N(p)$$ in $$\mathbb{Z}[i]$$.
Also $$p$$ is prime, hence $$p|q_i$$ for some $$i\in\{1,2,\ldots,n\}$$.
(ii) By part (i) above, $$p|q$$ in $$\mathbb{Z}[i]$$ for some prime number $$q\in\mathbb{Z}$$. So $$N(p)|N(q)$$ by proposition 48(iii).
Now $$N(p)>1$$ as $$p$$ is a prime Gaussian integer, and $$N(q)=q^2$$ as $$q$$ is a rational integer, so it follows that $$N(p)=q$$ or $$N(p)=q^2$$. ∎

[U] Exercises[/U]
50. Show for all Gaussian integers $$z,w$$ that $$w\mathbb{Z}[i]\subset z\mathbb{Z}[i]\Leftrightarrow z|w$$.
Conclude that $$w\mathbb{Z}[i]=z\mathbb{Z}[i]\Leftrightarrow z\sim w$$.
51. Show that if $$p\in\mathbb{Z}[i]$$ is prime and $$p\sim q$$ then $$q$$ is also prime.
52. Show that if $$p\in\mathbb{Z}[i]$$ is prime then so is $$\bar{p}$$.
53. Factorize 90 into a product of prime numbers in $$\mathbb{Z}$$ and then factorize further into a product of prime Gaussian integers.
54. Is it possible to write 90 as $$a^2+b^2$$ where $$a,b$$ are integers?

 All times are UTC. The time now is 10:43.