Saturday, 31 May 2014

Complex Prime Numbers

Complex Prime Numbers

We say a complex number $a+ib$ is complex integer or Gaussian integer if both $a,b\in ℤ$, the set of real integers. The set of all Gaussian integers is denoted by $ℤ\left[i\right]$. Intuitively, the notation means adjoining $i=\sqrt{-1}$ to real integers. What are complex prime numbers?

Recall that a real integer p is prime if $p>1$ and is divisible only by $1$ and $p$ (itself). Let us extend the deﬁnition of primes to complex numbers. Suppose we deﬁne a Gaussian integer $z\in ℤ\left[i\right]$ to be a complex prime if $|z|>1$ and is divisible only by $1$ and $z$ (itself). Note that, with such a deﬁnition, no Gaussian integer can be a complex prime.

1.
Note that $i$ is a factor of $1$ in $ℤ\left[i\right]$ and hence will divide all Gaussian integer $a+ib$. This motivates the deﬁnition of unit. An unit is a Gaussian integer which is a factor of $1$ in $ℤ\left[i\right]$. There are exactly four units in $ℤ\left[i\right]$, viz., $1,-1={i}^{2},i,-i={i}^{3}$. This is an outcome of the fact that, in real integers, there are exactly two units, viz., $1$ and $-1$. It can also be shown that units are, precisely, those elements whose modulus is exactly $1$.
2.
Even if units are included as factors in the deﬁnition of complex prime, we still notice that no Gaussian integer can be a complex prime. This is because if $z$ is a Gaussian integer such that $|z|>1$ then all its multiples by units, viz., $-z,iz$ and $-iz$ are all factors of $z$. This motivates the deﬁnition of associate. An associate of a Gaussian integer is a multiple of the units in $ℤ\left[i\right]$.

Deﬁnition 1. A complex prime or Gaussian prime is a Gaussian integer $z$ such that $|z|>1$ and is divisible only by its units and associates in $ℤ\left[i\right]$.

A simple observation from the deﬁnition is that if a Gaussian integer is a Gaussian prime then all of its associates are also Gaussian prime. Further, the conjugate $\stackrel{̄}{z}$ of a Gaussian prime $z$ is also a Gaussian prime because if $w$ is a factor of $\stackrel{̄}{z}$ then $\stackrel{̄}{w}$ is a factor of $z$.

We deﬁne the map $N:ℤ\left[i\right]\to ℕ\cup \left\{0\right\}$ as $N\left(z\right)={a}^{2}+{b}^{2}$ where $z=a+ib$. Note the following properties of $N$:

1.
$N\left(z\right)=N\left(\stackrel{̄}{z}\right)$.
2.
$N\left(z\right)=z\stackrel{̄}{z}$.
3.
$N\left(zw\right)=zw\stackrel{̄}{zw}=z\stackrel{̄}{z}w\stackrel{̄}{w}=N\left(z\right)N\left(w\right)$. The map $N$ is multiplicative.

If $w$ divides $z$ in $ℤ\left[i\right]$, then $N\left(w\right)$ divides $N\left(z\right)$ in $ℕ$ because $z=w{w}_{1}$, for some ${w}_{1}\in ℤ\left[i\right]$, and $N\left(z\right)=N\left(w\right)N\left({w}_{1}\right)$.

Let $z:=a+ib$ be a Gaussian integer such that either $a=0$ or $b=0$ and the non-zero, say $a$, satisﬁes ${a}^{2}>1$, i.e., $z=a$ or $z=ia$. Without loss of generality, we shall assume $a>1$. When is $z$ prime? Equivalently, what are the positive real integers which are Gaussian prime? Obviously, every positive real composite is not a Gaussian prime. Therefore, the question reduces to asking if every real prime is a Gaussian prime. A real prime $p$ can fail to be a Gaussian prime only if there is a non-zero, non-real Gaussian integer $w$ that divides $p$, i.e., $p=N\left(w\right)$. Thus, a real prime fails to be a Gaussian prime only if it is sum of two squares. For instance, the ﬁrst real prime $2={1}^{2}+{1}^{2}$ is not a Gaussian prime because $2=\left(1+i\right)\left(1-i\right)$.

Is every odd prime expressible as sum of squares of integers? For instance, $3$ is not expressible as sum of squares of two integers. Therefore, $3$ is a Gaussian prime. What are the odd primes which can be expressed as sum of two squares? Observe that any odd prime is either $1$ modulo $4$ or $3$ modulo $4$.

Theorem 1 (Fermats theorem on sums of two square). An odd prime $p$ is uniquely expressible as $p={a}^{2}+{b}^{2}$, for some $a,b\in ℕ$, iﬀ .

Proof. Let us suppose $p={a}^{2}+{b}^{2}$, for some $a,b\in ℕ$. $p$ being odd is either $1$ modulo $4$ or $3$ modulo $4$. Any perfect square is either $0$ modulo $4$ or $1$ modulo $4$. Thus ${a}^{2}+{b}^{2}$ is either $0$, $1$ or $2$ modulo $4$. Therefore $p$ is $1$ modulo $4$. The converse part of the proof is quite involved, so we skip it. □

Therefore, we conclude that any odd prime that is $3$ modulo $4$ is a Gaussian prime. For example, $3,7,11,19,\dots$ are all Gaussian primes. Alternately, any odd prime that is $1$ modulo $4$ is not a Gaussian prime. For example, $2,5,13,17,29,\dots$ are all not Gaussian primes. So, what are the complex primes other than these real primes?

Theorem 2. A Gaussian integer $z$ with $|z|>1$ and non-zero real and imaginary parts is a Gaussian prime iﬀ $N\left(z\right)$ is a prime in $ℕ$.

Proof. Let $z$ be a Gaussian prime. Then $\stackrel{̄}{z}$ is also a Gaussian prime. If $N\left(z\right)$ is not a prime in $ℕ$ then it has a positive divisor $1 which also divides either $z$ or $\stackrel{̄}{z}$ because $N\left(z\right)=z\stackrel{̄}{z}$ contradicting the Gaussian primality of $z$. Conversely, let $N\left(z\right)$ be a prime in $ℕ$. Suppose $z$ is not a Gaussian prime. Then it has non-trivial factors $v$ and $w$ and, hence, $\stackrel{̄}{v}$ and $\stackrel{̄}{w}$ are non-trivial factors of $\stackrel{̄}{z}$. Thus, $z\stackrel{̄}{z}$ and $w\stackrel{̄}{w}$ are non-trivial real factors of $N\left(z\right)$, a contradiction. □

Now that we have understood complex primes, we ask: is any Gaussian integer decomposable as product of Gaussian primes? In other words, we seek the analogues of the prime factorization theorem and the fundamental theorem of arithmetic for positive real integers.

Theorem 3 (Prime Factorization Theorem). Any number $n\in ℕ$ such that $n>1$ is either prime or can be decomposed as a product of prime numbers.

The decomposition in to product of primes is unique and is called the fundamental result of arithmetic.

Do we have similar results for Gaussian integers? The answer is in aﬃrmative, as long as, we bear in mind that unique factorisation is uniqueness up to multiplication with units $1,i,{i}^{2},{i}^{3}$. The unique prime factorization is obvious for Gaussian integers on real and imaginary line. For instance, any real non-prime positive integer has the unique factorisation $n={p}_{1}^{{a}_{1}}\dots {p}_{k}^{{a}_{k}}$. If any of the real prime ${p}_{i}$s are not Gaussian prime then they have a Gaussian prime decomposition as discussed above and this factorization is unique up to multiplication by units. For negative integers $-n$ with $n>0$, the factorization is the unit $-1$ multiplied with the factorization of $n$. For $in$ with $n\in ℤ$ it is still a multiple of the unit $i$ or $-i$. The unique factorisation can also be shown for any Gaussian integer. Therefore, we have the general result:

Theorem 4 (Unique Factorization Theorem). Any Gaussian integer $z$ with $N\left(z\right)>1$ can be decomposed as a product of Gaussian primes and the decomposition is unique up to associated Gaussian primes.

The discussion in this article are protoypes of algebraic entites like rings, prime ideals, unique factorization domains, class number etc. Class number $1$ corresponds to unique factorization property (UFP). $ℤ\left[i\right]$ is also related to Pythagorean triples. Similar to $ℤ\left[i\right]$, one may consider other quadratic ring $ℤ\left[\sqrt{m}\right]$, for $m\in ℤ$. Note that $m=0$ corresponds to $ℤ$ and $m=-1$ corresponds to $ℤ\left[i\right]$. The quadratic rings $ℤ\left[\sqrt{m}\right]$ are useful in the study of Pell’s equation

${x}^{2}-m{y}^{2}=1.$

The solution to Pell’s equation are the unit norm elements od $ℤ\left[\sqrt{m}\right]$. For $m>0$, $ℤ\left[\sqrt{m}\right]\subset ℝ$ and, for $m<0$, $ℤ\left[\sqrt{m}\right]\subset ℂ$ We know, for both $m=0$ and $m=-1$ the corresponding ring of integers satisﬁes UFP. Thus, one is tempted to conjecture that $ℤ\left[\sqrt{m}\right]$ satisﬁes the UFP, for all $m\in ℤ$. But the answer is in negation. For instance, $ℤ\left[\sqrt{-5}\right]$ do not satisfy UFP. The number $6\in ℤ\left[\sqrt{-5}\right]$ has two diﬀerent prime decomposition, viz., $6=2×3=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right)$. Check that each of the four factors is a prime in $ℤ\left[\sqrt{-5}\right]$. In fact, it has been shown that there are exactly nine negative integers, viz., $-1,-2,-3,-7,-11,-19,-43,-67,-163$ for which the UFP holds true. These are called Heegner numbers. It is an open problem whether there are ﬁnite number of positive integers for which UFP is true in $ℤ\left[\sqrt{m}\right]$.

Friday, 30 May 2014

Why Complex Numbers?

ComplexNos

Complex numbers are introduced in high school mathematics today. A common question that springs in our mind is:

Why do we need complex numbers? We all know x2 > 0 for all non-zero real numbers. Then why bother to seek a ‘‘number’’ x such that x2 = -1?

First note that it is very clear that there is no real number satisfying x2 = −1. Till some point in the history when people encountered such an equation, they ignored it as being absurd. It was Gerolamo Cardano (1545) who pursued √−1 as an “imaginary” number and Rafael Bombelli (1572) developed it as a number system. This blog is an attempt to recall the motivation behind their interest in a “number” that was not “real”.

The “imaginary” numbers were introduced as a mathematical tool to make life simple in the real world. In contrast to quadratic equations, it is impossible to compute real roots of certain cubic equations without solving for x2 =−1. Thus, it was observed that even to obtain real roots of certain cubic equations one has to go outside the realm of real numbers.

It is known for, at least, 2300 years that the formula to compute roots of the quadratic equation ax2 + bx + c =0, for given a,b,c∈ℝ with a ≠ 0 is

x  =
− b ±
 b2 −4ac
2a
.

A straight forward way of deriving this formula

a x2 + bx + c=0
x2 +
 b a
x
=
−
 c a
x2 +
 b a
x +

 b 2a

 2
=
 c a
+

 b 2a

 2

x +
 b 2a

 2
=
 b2 − 4ac 4a2
x +
 b 2a
=
±
 b2 − 4ac
2a
x=
− b ±
 b2 −4ac
2a
.

The case b2 −4ac < 0 always corresponds to non-existence of roots. Geometrically, in this case, the graph of the quadratic function never intersects x-axis. This situation sits well with our understanding that it is absurd to consider square root of negative numbers.

Let us derive the formula for roots of quadratic equation in an alternate way. This alternate approach will help us in deriving a formula for cubic equation. Note that if b=0 in the quadratic equation, then a x2 + c=0 and

x =
 √
 −c a
.

Let us seek a ξ such that replacing x in ax2 + bx+c with y − ξ changes the equation to A y2 + C. Set x= y −ξ. Then

 a x2 + bx + c = a (y−ξ)2 + b (y −ξ) + c = a y2 − 2aξ y + a ξ2 + by − b ξ +c = a y2 + (b − 2aξ)y + a ξ2 − bξ +c.

We shall choose ξ such that the coefficient of y is zero. Therefore, we choose ξ = b/2a. Thus,

a y2 +
 b2 4a
−
 b2 2a
+ c = a y2 −
 b2 4a
+ c.

The roots of a y2b2/4a + c =0 are

y = ±
 b2 − 4ac
2a

and the roots of ax2 + bx +c =0 are

x = −
 b 2a
±
 b2 − 4ac
2a
.

Let us employ the above approach to find a formula for roots of the cubic equation ax3 + bx2 +cx +d =0. We seek for a ξ such that replacing x in a x3 + b x2 +cx +d with y −ξ changes the equation to Ax3 + Cx +D. Then

 a x3 + bx2 + cx + d = a (y−ξ)3 + b (y −ξ)2 + c (y− ξ) + d = a y3 − 3aξ y2 + 3 a ξ2 y − ξ3 + by2 − 2b ξ y +b ξ2 + cy − c ξ +d = a y3 + (b − 3aξ)y2 + (3 a ξ2 − 2 bξ +c) y +bξ2 − ξ3 − c ξ +d.

Demanding ξ to be such that the coefficients of both y2 and y vanish is too restrictive because in that case we must have b − 3aξ = 3a ξ2 − 2b ξ +c =0. This would imply that ξ = b/(3a) and b2 = 3ac which is too restrictive for a general cubic equation.

Let us eliminate the coefficient of y2, by choosing ξ = b/(3a). Then the cubic equation in y has the form

a y3 +

 3 a c − b2 3a

y +

 b 3a

 3
(3a −1) +
= 0.

Now, set

p :=
 3 a c − b2 3a

and

q :=

 b 3a

 3
(3a −1) +

to make the equation appear as a y3 + py +q =0. To reduce this cubic equation to a quadratic equation in a new variable we use the Vieta’s substitution which says define a new variable z such that

y = z −
 p 3az
.

The Vieta’s substituion can be motivated but we shall not digress in to that domain. Then the equation a y3 + py +q =0 transforms to a quadratic equation

 27 a4 (z3)2 + 27 q a3 z3 − p3=0.

The roots of this equation are

z3 =
− q ±
 √
q2 +
 4p3 27 a2
2a
.

At first glance, it seems like z has six solutions, but three of them will coincide. Thus, finding z leads to finding y and, hence, to x. Thus far, we have only derived a formula for roots of cubic equation. We are yet to address the question of complex numbers.

As a simple example, consider the cubic function x3 − 3x. The roots of this equation can be easily computed by rewriting x3x = x(x2 −3) = x (x +√3)(x−√3) and hence has exactly three roots 0, √3, −√3.

Let us try to compute the roots of x3x using the formula derived above. Note that x3x is already in the form with no x2 term. Thus, a=1, p=−3, q=0 and z3 = ± √−1. The cubic equation has real roots but z is not in the realm of real numbers. √−1 makes no sense, since square of any non-zero real number is positive. This is the motivation for complex numbers! We set i:= √−1 and, hence, i2 = −1. We introduce this notation to avoid using the property of square root, √ab = √ab. Negative numbers will not inherit this property because √−1−1 = −1 ≠ 1 = √(−1)(−1). With this setting, z3 = ± i. Now recall from your course on complex numbers that the cube roots of i are z = −i, √3+i/2, −√3+i/2. Using this in the formula

x = z +
 1 z

we get x = 0, √3, − √3. The cube roots of −i are z = i, √3i/2, −√3i/2 which yield the same roots. Expanding to complex number system helped us in solving a real cubic equation with only real roots! This little bold step helped us understand/expand in many ways. Complex numbers and complex functions has found application in engineering and other sciences, especially, via analytic functions and analytic continuations.