The complex numbers are defined as
\begin{equation*} {\mathbb C} = \{ a + bi : a, b \in {\mathbb R} \}, \end{equation*}where \(i^2 = -1\text{.}\) If \(z = a + bi\text{,}\) then \(a\) is the real part of \(z\) and \(b\) is the imaginary part of \(z\text{.}\)
To add two complex numbers \(z=a+bi\) and \(w= c+di\text{,}\) we just add the corresponding real and imaginary parts:
\begin{equation*} z + w=(a + bi ) + (c + di) = (a + c) + (b + d)i. \end{equation*}Remembering that \(i^2 = -1\text{,}\) we multiply complex numbers just like polynomials. The product of \(z\) and \(w\) is
\begin{equation*} (a + bi )(c + di) = ac + bdi^2 + adi + bci = (ac -bd) +(ad + bc)i. \end{equation*}Every nonzero complex number \(z = a +bi\) has a multiplicative inverse; that is, there exists a \(z^{-1} \in {\mathbb C}^\ast\) such that \(z z^{-1} = z^{-1} z = 1\text{.}\) If \(z = a + bi\text{,}\) then
\begin{equation*} z^{-1} = \frac{a-bi}{ a^2 + b^2 }. \end{equation*}The complex conjugate of a complex number \(z = a + bi\) is defined to be \(\overline{z} = a- bi\text{.}\) The absolute value or modulus of \(z = a + bi\) is \(|z| = \sqrt{a^2 + b^2}\text{.}\)
Let \(z = 2 + 3i\) and \(w = 1-2i\text{.}\) Then
\begin{equation*} z + w = (2 + 3i) + (1 - 2i) = 3 + i \end{equation*}and
\begin{equation*} z w = (2 + 3i)(1 - 2i ) = 8 - i. \end{equation*}Also,
\begin{align*} z^{-1} & = \frac{2}{13} - \frac{3}{13}i\\ |z| & = \sqrt{13}\\ \overline{z} & = 2-3i. \end{align*}There are several ways of graphically representing complex numbers. We can represent a complex number \(z = a +bi\) as an ordered pair on the \(xy\) plane where \(a\) is the \(x\) (or real) coordinate and \(b\) is the \(y\) (or imaginary) coordinate. This is called the rectangular or Cartesian representation. The rectangular representations of \(z_1 = 2 + 3i\text{,}\) \(z_2 = 1 - 2i\text{,}\) and \(z_3 = - 3 + 2i\) are depicted in Figure 4.18.
Nonzero complex numbers can also be represented using polar coordinates. To specify any nonzero point on the plane, it suffices to give an angle \(\theta\) from the positive \(x\) axis in the counterclockwise direction and a distance \(r\) from the origin, as in Figure 4.19. We can see that
\begin{equation*} z = a + bi = r( \cos \theta + i \sin \theta). \end{equation*}Hence,
\begin{equation*} r = |z| = \sqrt{a^2 + b^2} \end{equation*}and
\begin{align*} a & = r \cos \theta\\ b & = r \sin \theta. \end{align*}We sometimes abbreviate \(r( \cos \theta + i \sin \theta)\) as \(r \cis \theta\text{.}\) To assure that the representation of \(z\) is well-defined, we also require that \(0^{\circ} \leq \theta \lt 360^{\circ}\text{.}\) If the measurement is in radians, then \(0 \leq \theta \lt2 \pi\text{.}\)
Suppose that \(z = 2 \cis 60^{\circ}\text{.}\) Then
\begin{equation*} a = 2 \cos 60^{\circ} = 1 \end{equation*}and
\begin{equation*} b = 2 \sin 60^{\circ} = \sqrt{3}. \end{equation*}Hence, the rectangular representation is \(z = 1+\sqrt{3}\, i\text{.}\)
Conversely, if we are given a rectangular representation of a complex number, it is often useful to know the number's polar representation. If \(z = 3 \sqrt{2} - 3 \sqrt{2}\, i\text{,}\) then
\begin{equation*} r = \sqrt{a^2 + b^2} = \sqrt{36 } = 6 \end{equation*}and
\begin{equation*} \theta = \arctan \left( \frac{b}{a} \right) = \arctan( - 1) = 315^{\circ}, \end{equation*}so \(3 \sqrt{2} - 3 \sqrt{2}\, i=6 \cis 315^{\circ}\text{.}\)
The polar representation of a complex number makes it easy to find products and powers of complex numbers. The proof of the following proposition is straightforward and is left as an exercise.
Let \(z = r \cis \theta\) and \(w = s \cis \phi\) be two nonzero complex numbers. Then
\begin{equation*} zw = r s \cis( \theta + \phi). \end{equation*}If \(z = 3 \cis( \pi / 3 )\) and \(w = 2 \cis(\pi / 6 )\text{,}\) then \(zw = 6 \cis( \pi / 2 ) = 6i\text{.}\)
Let \(z = r \cis \theta\) be a nonzero complex number. Then
\begin{equation*} [r \cis \theta ]^n = r^n \cis( n \theta) \end{equation*}for \(n = 1, 2, \ldots\text{.}\)
We will use induction on \(n\text{.}\) For \(n = 1\) the theorem is trivial. Assume that the theorem is true for all \(k\) such that \(1 \leq k \leq n\text{.}\) Then
\begin{align*} z^{n+1} & = z^n z\\ & = r^n( \cos n \theta + i \sin n \theta ) r( \cos \theta + i\sin \theta )\\ & = r^{n+1} [( \cos n \theta \cos \theta - \sin n \theta \sin \theta ) + i ( \sin n \theta \cos \theta + \cos n \theta \sin \theta)]\\ & = r^{n+1} [ \cos( n \theta + \theta) + i \sin( n \theta + \theta) ]\\ & = r^{n+1} [ \cos( n +1) \theta + i \sin( n+1) \theta ]. \end{align*}Suppose that \(z= 1+i\) and we wish to compute \(z^{10}\text{.}\) Rather than computing \((1 + i)^{10}\) directly, it is much easier to switch to polar coordinates and calculate \(z^{10}\) using DeMoivre's Theorem:
\begin{align*} z^{10} & = (1+i)^{10}\\ & = \left( \sqrt{2} \cis \left( \frac{\pi }{4} \right) \right)^{10}\\ & = ( \sqrt{2}\, )^{10} \cis \left( \frac{5\pi }{2} \right)\\ & = 32 \cis \left( \frac{\pi }{2} \right)\\ & = 32i. \end{align*}The multiplicative group of the complex numbers, \({\mathbb C}^*\text{,}\) possesses some interesting subgroups. Whereas \({\mathbb Q}^*\) and \({\mathbb R}^*\) have no interesting subgroups of finite order, \({\mathbb C}^*\) has many. We first consider the circle group,
\begin{equation*} {\mathbb T} = \{ z \in {\mathbb C} : |z| = 1 \}. \end{equation*}The following proposition is a direct result of Proposition 4.21.
The circle group is a subgroup of \({\mathbb C}^*\text{.}\)
Although the circle group has infinite order, it has many interesting finite subgroups. Suppose that \(H = \{ 1, -1, i, -i \}\text{.}\) Then \(H\) is a subgroup of the circle group. Also, \(1\text{,}\) \(-1\text{,}\) \(i\text{,}\) and \(-i\) are exactly those complex numbers that satisfy the equation \(z^4 = 1\text{.}\) The complex numbers satisfying the equation \(z^n=1\) are called the \(n\)th roots of unity.
If \(z^n = 1\text{,}\) then the \(n\)th roots of unity are
\begin{equation*} z = \cis\left( \frac{2 k \pi}{n } \right), \end{equation*}where \(k = 0, 1, \ldots, n-1\text{.}\) Furthermore, the \(n\)th roots of unity form a cyclic subgroup of \({\mathbb T}\) of order \(n\)
By DeMoivre's Theorem,
\begin{equation*} z^n = \cis \left( n \frac{2 k \pi}{n } \right) = \cis( 2 k \pi ) = 1. \end{equation*}The \(z\)'s are distinct since the numbers \(2 k \pi /n\) are all distinct and are greater than or equal to 0 but less than \(2 \pi\text{.}\) The fact that these are all of the roots of the equation \(z^n=1\) follows from from Corollary 17.9, which states that a polynomial of degree \(n\) can have at most \(n\) roots. We will leave the proof that the \(n\)th roots of unity form a cyclic subgroup of \({\mathbb T}\) as an exercise.
A generator for the group of the \(n\)th roots of unity is called a primitive \(n\)th root of unity.
The 8th roots of unity can be represented as eight equally spaced points on the unit circle (Figure 4.28). The primitive 8th roots of unity are
\begin{align*} \omega & = \frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2} i\\ \omega^3 & = -\frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2} i\\ \omega^5 & = -\frac{\sqrt{2}}{2} - \frac{\sqrt{2}}{2} i\\ \omega^7 & = \frac{\sqrt{2}}{2} - \frac{\sqrt{2}}{2}i. \end{align*}Computing large powers can be very time-consuming. Just as anyone can compute \(2^2\) or \(2^8\text{,}\) everyone knows how to compute
\begin{equation*} 2^{2^{1{,}000{,}000} }. \end{equation*}However, such numbers are so large that we do not want to attempt the calculations; moreover, past a certain point the computations would not be feasible even if we had every computer in the world at our disposal. Even writing down the decimal representation of a very large number may not be reasonable. It could be thousands or even millions of digits long. However, if we could compute something like
\begin{equation*} 2^{37{,}398{,}332 } \pmod{ 46{,}389}, \end{equation*}we could very easily write the result down since it would be a number between \(0\) and \(46{,}388\text{.}\) If we want to compute powers modulo \(n\) quickly and efficiently, we will have to be clever. 1 The results in this section are needed only in cryptography.
The first thing to notice is that any number \(a\) can be written as the sum of distinct powers of \(2\text{;}\) that is, we can write
\begin{equation*} a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}, \end{equation*}where \(k_1 \lt k_2 \lt \cdots \lt k_n\text{.}\) This is just the binary representation of \(a\text{.}\) For example, the binary representation of 57 is 111001, since we can write \(57 = 2^0 + 2^3 + 2^4 + 2^5\text{.}\)
The laws of exponents still work in \({\mathbb Z}_n\text{;}\) that is, if \(b \equiv a^x \pmod{ n}\) and \(c \equiv a^y \pmod{ n}\text{,}\) then \(bc \equiv a^{x+y} \pmod{ n}\text{.}\) We can compute \(a^{2^k} \pmod{ n}\) in \(k\) multiplications by computing
\begin{gather*} a^{2^0} \pmod{ n}\\ a^{2^1} \pmod{ n }\\ \vdots\\ a^{2^k} \pmod{ n}. \end{gather*}Each step involves squaring the answer obtained in the previous step, dividing by \(n\text{,}\) and taking the remainder.
We will compute \(271^{321} \pmod{ 481}\text{.}\) Notice that
\begin{equation*} 321 = 2^0 +2^6 + 2^8; \end{equation*}hence, computing \(271^{ 321} \pmod{ 481}\) is the same as computing
\begin{equation*} 271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}. \end{equation*}So it will suffice to compute \(271^{ 2^i } \pmod{ 481}\) where \(i = 0, 6, 8\text{.}\) It is very easy to see that
\begin{equation*} 271^{ 2^1} = \text{73,441} \equiv 329 \pmod{ 481}. \end{equation*}We can square this result to obtain a value for \(271^{ 2^2} \pmod{481}\text{:}\)
\begin{align*} 271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}\\ & \equiv (329)^2 \pmod{481}\\ & \equiv 108{,}241 \pmod{481}\\ & \equiv 16 \pmod{481}. \end{align*}We are using the fact that \((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) Continuing, we can calculate
\begin{equation*} 271^{ 2^6 } \equiv 419 \pmod{481} \end{equation*}and
\begin{equation*} 271^{ 2^8 } \equiv 16 \pmod{481}. \end{equation*}Therefore,
\begin{align*} 271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{481}\\ & \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{481}\\ & \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}\\ & \equiv 1{,}816{,}784 \pmod{ 481}\\ & \equiv 47 \pmod{ 481}. \end{align*}The method of repeated squares will prove to be a very useful tool to explore RSA cryptography. To encode and decode messages in a reasonable manner under this scheme, it is necessary to be able to quickly compute large powers of integers mod \(n\text{.}\)
