$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \setcounter{chapter}{-1}$

## Section4.4Multiplicative Group of Complex Numbers

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

###### Example4.17

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

###### Example4.20

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.

###### Example4.22

If $z = 3 \cis( \pi / 3 )$ and $w = 2 \cis(\pi / 6 )\text{,}$ then $zw = 6 \cis( \pi / 2 ) = 6i\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*}
###### Example4.24

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*}

### Subsection4.4.1The Circle Group and the Roots of Unity

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.

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.

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.

###### Example4.27

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*}

### Subsection4.4.2The Method of Repeated Squares

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.

###### Example4.29

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