Definition
Suppose I take a number x, and a natural number n.
Now raise it to the nth power, by multiplying n x's together, in a
process called exponentiation. If the answer
comes out as 1, then x is an nth root of unity. A formal mathematical definition
might look something like:
The nth roots of unity are the solutions to the equation
xn = 1. Mathematicians may like nothing more than
being formal, but there have been no surprises so far, and this may
not look like a very interesting concept. Let's see how far it can go. Indeed, there seems to be little of interest going on if we look
at real numbers. There's only one positive nth root of 1, and
that's 1 itself, for every n. If we allow negative numbers, then -1
is an nth root as well if and only if n is even. That's it. When we start to look at complex numbers, things begin to get a
little more interesting. And there's a whole world of other
algebraic number systems out there, such as modular arithmetic.
Complex numbers
There are n nth complex roots of unity, of the form exp(k*2πi/n), as k ranges from 0 to n-1. They are n equally spaced
points on the unit circle. We can quickly prove that's all of them,
since 1 is itself on the unit circle, powers of points inside the unit
circle are still inside the unit circle, and powers of points outside,
stay outside. The modulus of any complex solutions must be 1. What
about the argument - the angle of the number on an Argand diagram?
Since exponentiation multiplies this angle, it follows the angle must
be a whole number of rotations, divided by n, for a number to be an
n'th root. It's no accident that there are exactly n roots in the
complex plane. It's a consequence of the fundamental theorem of
algebra, but there are algebraic structures in which it is not
always true, which we'll visit later.
However, we can still say more. Consider the case n=4. The 4th
roots of unity are {1, i, -1, -i} in the complex number system.
However, 1 is unity itself, and -1 is a square root. Only i and -i
satisfy x4 = 1 and are not solutions to
xn = 1 for any smaller value of n. These roots are
known as primitive roots. For a given n, there are exactly φ(n) primitive
roots, where φ is the Euler phi function, the number of
integers less than n, but with no common factor with n (other than 1).
By convention, one of these primitive roots can be denoted by ω. It turns out that the set of values {ω0 =
1, ω1, ω2 ... ωn-1} are all
distinct and are precisely the nth roots of unity again. A lot of the jargon
for these properties reflects this circular behavior. For example "ω is
a generator of the cyclic group of nth roots", or "the
primitive roots satisfy the nth cyclotomic polynomial". Many of these facts still hold true in other systems.
Modular arithmetic
We can similarly consider the notion of nth roots of unity in
modular arithmetic where all operations are performed modulo some
number m - in other words, we only consider ourselves with the remainders
on division by m after any arithmetic. The easiest case turns out to be when m is a prime number. Let's use m=17 for an example, and pick g=3. We can write a table of
the powers of g:
g0 = 1
g1 = 3
g2 = 9
g3 = 27 = 10 mod 17
g4 = g * g3 = 3 * 10 = 30 = 13 mod 17
g5 = g * g4 = 3 * 13 = 39 = 5 mod 17
...
By continuing the table, it turns out that 3
16 = 1 mod
17, but 3
n is not 1 for any smaller value of n. 3 is a
primitive 16th root, modulo 17. What's more, the 16 powers of 3 form a
covering of all the
nonzero values, modulo 17. Every nonzero
value modulo 17 appears exactly once in this list of powers. We could reverse the table above, and get a new table of
discrete logarithms:
x | log3x mod 17
=======================
1 | 0 (30 = 1)
2 | 14 (314 = 2 mod 17)
3 | 1 (31 = 3)
4 | 12 (312 = 4 mod 17)
5 | 5 (35 = 5 mod 17)
...
Just like regular
logarithms, we could multiply numbers modulo 17
by adding their discrete logarithms, which sounds like there could be
an easy way to multiply and divide in general. However, the problem of
finding a discrete logarithm is hard. Apart from drawing up the whole
table (which, even for a small number like 17, appears to be quite some
work) there appears to be no efficient way of solving the discrete
logarithm problem. Many
cryptography systems depend on this, for it
appears that exponentiation is a
one-way function. It's quite easy
to exponentiate, but so far seems very difficult to perform the
inverse process
of finding a discrete logarithm. Furthermore, many other problems can
be shown to be
equivalent to the discrete logarithm problem. Should
anyone find an efficient method, it will have quite some consequences.
The behavior of multiplication modulo 17 (that the 16 non-zero
values are all 16th roots of unity, and there exists a primitive 16th
roots) is typical for prime moduli, and has many applications in
number theory. The picture is quite different, however, for
composite moduli.
Composite moduli
What about
arithmetic modulo some composite number, such as 15? It
turns out that things behave significantly differently from in the
prime case. For example, here's a list of values x and their
squares:
x | x2 mod 15
===================
1 | 1 = 1 mod 15
4 | 16 = 1 mod 15
11 | 121 = 1 mod 15
14 | 196 = 1 mod 15
Already, there is something different going on. 1 appears to have
four square roots modulo 15. Aren't there only supposed to be
two? If you investigate further, you'll find there are eight fourth
roots, no unique generator, and the values modulo 15 that have common
factors with 15 are never roots of unity at all. Evidently the
behavior is different because 15 is composite, but can we explain it?
If we reduce the values in the table modulo the prime factors of
15, that's 3 and 5, the problem does disappear. There's two square
roots of unity for each prime factor. There are four possible
combinations of these roots from the factors, which produce the four
values in the table after applying the Chinese remainder theorem.
Furthermore, we can look at the square roots modulo 15 as solutions to
the equation x2-1 = 0 mod 15. The left hand side factors as a
difference of two squares, so (x-1)(x+1) = 0 mod 15.
Substituting one of the "rogue" values like x=4 and we get 3*5 = 0 mod
15, in other words, we have managed to find the factors. The
fundamental theorem of algebra did not apply, because it's no longer
true that if the product is zero, one of the original terms in the
equation has to be zero, too. (In technical terms, modulo 15
arithmetic occurs in a ring, not a field).
Applications
It's already been implied that the behavior of the nth roots of
unity has applications in number theory, particularly
primality testing. If p is a prime, then all the non-zero elements modulo p
are (p-1)'th roots of unity. This is equivalent to Fermat's little theorem (not with be confused with his "last"). The
contrapositive statement requires a little care to formulate and we have to be
particularly careful with the grammar. If there exists an element
a modulo n such that an-1 is not 1 modulo n, then n is
surely composite. Such an a is called a witness to the composite
nature of n. The converse of the little theorem is not true - there
do exist pseudoprimes which satisfy the condition of the little
theorem for a particular value of a, but are composite. There are even
composite numbers called Carmichael numbers that satisfy the Fermat
condition for all values of a that have no common factor with
n. However, with a little work, even these can be resolved. For a
prime modulus n, there are not only (n-1)th roots, but also (n-1)th
primitive roots, and finding one of those proves primality. For large
values of n, the difficult part then becomes factoring n-1. However, it is a basis for many primality tests with low time complexity.
Roots of unity also surface in numerical applications such as the
fast Fourier transform. While it can be formulated in terms of complex roots, it is also possible to construct an
integer FFT by performing all arithmetic modulo some number with
known roots. As noted above, the discrete logarithm problem is
difficult, so finding the roots to some arbitrary modulus is not the
way to proceed. Instead, a construction is used to produce a
convenient modulus and roots which are easy to manipulate
in computation. However, some care is required, since all arithmetic
must be done to that modulus. Results that exceed that modulus will overflow
and wrap around.
Sources
Hardy, G. H. and Wright, E. M. An Introduction to the
Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.
Grandlund, T. FFT Multiplication, from the GNU MP
documentation.
http://www.gnu.org/software/gmp/manual/html_node/FFT-Multiplication.html
, viewed on July 16, 2005.