In this part of the text, we will narrow our attention to sets of numbers. These sets will be one of the main objects of our interest in BIE-ZMA
We denote the set of natural numbers 22 by $\N$,
Natural numbers abstract the notion of the „count“ of objects. Figure 3.2 shows three sets of different geometrical shapes. Examples (a), (b) and (c) have the property of always having three shapes. We express this observation by stating that there are three shapes there and we denote it by Arabic numeral $3$.
Note that the set of natural numbers is closed under multiplication and addition. More precisely, by multiplying and adding two natural numbers, we get a natural number again:
To appreciate positional notation of numbers using Arabic23 numerals try to consider the problem of performing algebraic operations (addition, multiplication, subtraction) using the Roman numeral system. It's not easy, is it? Arabic numerals in Europe were promoted by Leonardo from Pisa (known as Fibonacci) in the beginning of the thirteenth century. In 1202 he published the Liber abbaci („The Counting Book“), which greatly aided the development of business and science. A courious reader can find out more interesting facts about the „first computational revolution“ in this engaging book (Devlin, 2011).
The set $\N$ is, however, not closed under subtraction of two natural numbers. We can also formulate this fact with the use of addition by saying that the equation
for some natural numbers $a,b\in\N$ may not have a solution $x$ in natural numbers. Consider e.g. $a=4$ and $b=5$. In other words, we cannot express the concept of „debt“ and „empty count“ using only natural numbers.
To eliminate these shortcomings, we need to add zero and negative numbers to natural numbers. Thus we get the set of integers,
In this set we can multiply, add and subtract, but the result of division is outside of this set. I.e. there need not be an integer solution to the equation
for some integers $a$ and $b$. This operation can be motivated by the need to divide an object into several parts. For example, when dividing one pizza ($a = 1$) into eight pieces ($b = 8$) we get eighths of pizza ($x=\frac{1}{8}$). We have to move to rational24 numbers.
The set of rational numbers consists of solutions to the equation (3.6) with non-zero $b$, which we write as fractions
We define addition and multiplication of fractions using operations in $\Z$ as follows25
We can simplify the right-hand sides of these terms by dividing by common factors so we always get an element of the set (3.7). Integers are naturally included in the set of rational numbers, i.e. $\mathbb{Z} \subset \mathbb{Q}$, as fractions $\frac{p}{1}$, where $p \in \mathbb{Z}$, while algebraic operations are preserved.
Rational numbers $\Q$ together with addition $+$ and multiplication $\cdot$ satisfy important relationships
valid for all rational numbers $a,b,c$. We call equalities (3.8) the associative laws for addition, resp. multiplication. Only thanks to these laws we can omit parentheses when writing chains of additions or multiplications since the final result actually does not depend on parentheses26. We call the equality in (3.9) the distributive law. The reader is certainly intimately familiar with it, because it can be used to perform the „factoring out“ operation. To be able to omit parentheses on the right-hand side of (3.9) we introduce the convention of precedence of multiplication over addition. An important element of the set of rational numbers is the number $0$ which satisfies
for any rational number $a$. For every rational $a$ there is a rational number denoted by $-a$ with the property that
The relationship between $0$ and addition is analogous to the relationship between the number $1$ and multiplication. For every rational number $a$ we have that
Finally, for any non-zero rational number $a$ there exists a rational number denoted by $a^{-1}$ having the property that
The previous paragraph can be summed up by saying that the set of rational numbers $\Q$ together with addition $+$ and multiplication $\cdot$ forms a field. The area of mathematics which studies27 number fields is called general algebra. Finite28 fields are widely used in modern encryption algorithms and generally, in computer security.
In the set of rational numbers, we can therefore perform the so-called algebraic operations of addition, subtraction, multiplication and division (by non-zero numbers). This „numerical environment“ is fully sufficient to perform simple accounting and business operations that motivated the development of algebra in the Middle Ages. Unfortunately (or maybe fortunately) this numerical set is not sufficient to describe a number of practical problems. On the other hand, even such an old concept as rational numbers cannot be fully modelled on modern computers (as we do not have infinite memory).
At the beginning of this chapter we showed that natural numbers and integers are „not enough“. It was always necessary to add more numbers to meet our requirements. Similar situation also occurs in the case of rational numbers. This set is already closed under binary algebraic operations of addition and multiplication, but this time we encounter difficulties in analyzing the following geometric problem. Consider a square with side of length $1$ (a rational number), see Figure 3.3.
We want to know the length of its diagonal. It can be constructed using a ruler and compasses. In Figure 3.3 it is denoted by $x$. According to the Pythagoras' theorem,
So $x^2 = 2$. We call this positive number $x$ the square root of two and denote it by $\sqrt{2}$. We can easily show that this number is not rational as we have already shown in Theorem 2.1. So we face a serious problem. The length of the red line in Figure 3.3 cannot be expressed as a rational number! Does it mean that we cannot use the concept of a diagonal in this case? No, it just demonstrates the imperfection of rational numbers which will be solved by introducing the real numbers.
Other important irrational numbers are Ludolf's29 number (traditionally marked by Greek letter $\pi$) or Euler's30 constant (traditionally marked by Latin letter $\ee$). In a sense, there are considerably more31 irrational numbers than rational numbers, one can say that a „typical“ real number is irrational. We will learn more about the relationship of these two sets in BIE-ZMA. The reader certainly knows that numbers can be imagined as points lying on a straight line, called the number line. A significant point corresponding to zero is selected on the line and a number $a$ is plotted on the line at the distance of $|a|$ from $0$. Positive numbers are placed on the right and negative numbers on the left of $0$.
If we plotted only rational numbers on the line the resulting line would be „punctured“. For instance, there would be holes at the distance of $\sqrt{2}$ (to the right as well as left) from $0$. To fill in the number line we must consider also irrational numbers. The requirement for the non-puncteredness of the real line is more accurately expressed by the „axiom of completeness“. We will deal with this issue in more detail in one of the first BIE-ZMA lectures.
Interestingly enough, it may not be easy to decide on rationality or irrationality of a number. There are numbers about which we do not know to which set they belong. An example is the Euler-Mascheroni constant defined by the formula32
More information on this particular issue can be found in (Weisstein, b.r.).
It might seem that after adding irrational numbers to the rational ones no additional numbers are needed. Note that the geometrical consideration of the past paragraph can be simply reduced to the requirement (see the equation (3.10)) that the equation
have a solution in a given number set (here $\pm\sqrt{2}\in\R$). But a simple variation of this equation
does not have a real solution33 either. This equation can be solved by introducing an imaginary unit (we denote it by $\ii$), which satisfies $\ii^2 = -1$ and hence is also a solution of the equation (3.11). We call $\ii$ the complex unit. This new number can be multiplied by and added to any real number. In this way we get the complex numbers,
If $z = a + b \ii$ is a complex number then the real number $a$ is called the real part of $z$ and the real number $b$ the imaginary part of $z$. Two complex numbers are equal when their real parts and their imaginary parts are equal. We denote the real part of a complex number $z$ by $\Re z$ and the imaginary part by $\Im z$. Real numbers are naturally included in the set of complex numbers as we can identify a real number $a$ with a complex number $a + 0 \ii$.
Algebraic operations on $\CC$ are defined as follows:
Note that if $d=b=0$ then $a+c$ and $a\cdot c$ has the same meaning as in real numbers. The set $\CC$ together with these operations forms a field.
We can imagine complex numbers as points in the complex plane. We call the horizontal axis the real axis and the vertical axis the imaginary axis. A complex number $a+\ii b$ is then represented by a point with coordinates $(a,b)$, see Figure 3.5.
We define the absolute value of a complex number as
In the complex plane, we can imagine the absolute value of a complex number $a+ b\ii$ as the length of the segment joining $0$ and $a+b\ii$. We call $a - b\ii$ the complex conjugate of $a + b\ii$, $a,b\in\R$. The complex conjugate is thus obtained by reflection about the real axis.
Addition of complex numbers can be imagined as the addition of vectors (we add their „corresponding components“). Multiplication of complex numbers can be represented as rotation and scaling in the complex plane. This is not at all obvious but it can be derived from the definition of multiplication (3.12), see Figure 3.6. In particular, multiplication by the imaginary unit $\ii$ can be seen, in the complex plane, as rotation by the angle $\frac{\pi}{2}$ relative to the origin of the coordinate system which corresponds to $0$, counterclockwise.
The reason to introduce complex numbers may seem artificial. Now, the question is whether or not, when we examine solutions of polynomial equations other than (3.11), we will need another complex unit. This question was answered by Gauss34 in his famous Fundamental theorem of algebra: every polynomial of degree $n$ with complex number coefficients has $n$ roots in the complex numbers35. So complex numbers are sufficient to solve polynomial equations.
A number of mathematical methods applied in practice inherently use complex numbers. For instance the Fourier transform (resp. Fast Fourier Transform, FFT), used to analyze signal, could be only awkwardly described without the complex number apparatus. Without complex numbers it would be very difficult to formulate quantum physics, the theory behind a number of modern technologies that may completely change the issue of IT security in the near future.
At the end of this chapter, we would like to remark that complex numbers can be further extended to the (non-commutative) field of quaternions. This field has three complex units ($\ii$, $\mathrm{j}$ and $\mathrm{k}$). In total there are four units (one real $1$ and three „complex“ ones), thus the name. Relationships between these units are defined by formulas
From these relationships you can derive other products of different combinations of units.
From the definition in (3.13) derive the products
From $\mathrm{i}\mathrm{j}\mathrm{k} = -1$ by multiplying with $\mathrm{k}$ from the right we have $-\mathrm{i}\mathrm{j} = -k$ and so $\mathrm{i}\mathrm{j} = k$. Similarly, from $\mathrm{i}\mathrm{j}\mathrm{k} = -1$ by multiplying with $\mathrm{i}$ from the left and then with $\mathrm{j}$ from the left we get $-\mathrm{k} = \mathrm{j}\mathrm{i}$.
The set
together with operations defined analogously to complex numbers was introduced by Hamilton36. Why do we mention quaternions? Quaternions can be used to calculate, for example, the rotation of vectors in three-dimensional space. They are used by a number of algorithms implemented in graphics cards. If you are interested see here (Confuted, b.r.).
Plot the following complex numbers in the complex plane.
a) $\Re z = 10$, $\Im z = -5$, b) $\Re z = 3$, $\Im z = -4$, c) $\Re z = -1$, $\Im z = 1$, d) $\Re z = \frac{2}{5}$, $\Im z = - \frac{1}{5}$.