358 nth root of unity

n

2π

–

n

time to find solutions). This question is usually written:

P = NP?

See also

POLYNOMIAL TIME

.

nth root of unity Any

COMPLEX NUMBER

zsuch that

zn= 1 is called an nth root of unity. When nis 2 or 3,

the relevant roots are usually called square roots and

cube roots, respectively. There are two square roots of

unity, namely, z= 1 and z= –1, and there are three cube

roots of unity: z= 1, , and . In

general, as the

FUNDAMENTAL THEOREM OF ALGEBRA

shows, there are n nth roots of unity. The number z= 1

is an nth root of unity for all values of n.

E

ULER

’

S THEOREM

shows that the nth roots of

unity are given by the formula:

for k= 0,1,…,n(since zn= = ei2πk= cos(2πk)

+ isin (2πk) = 1 + 0 = 1). This shows that the n nth

roots of unity all lie on a circle of radius one and are

equidistant along that circle at angles that are multiples

of . That is, when plotted on the complex plane, the

n nth roots of unity lie at the vertices of a regular ngon

with the point z= 1 on the real axis as one vertex of

the polygon.

An nth root of unity zis called a primitive if zn= 1,

but zk≠1 for any positive integer smaller than n. For

example, although z= –1 is a fourth root of unity, it is

not a primitive root, since we also have (–1)2= 1. The

numbers z= iand z= –iare both primitive fourth roots

of unity.

An nth root of unity zsatisfies the equation zn– 1

= 0. Factoring yields:

(z– 1)(1 + z+ z2+ z3+…+ zn–1) = 0

If zis different from 1, then it must be the case that the

second term of the left side of this expression is zero.

This proves:

Each nth root of unity different from 1 satisfies

1 + z+ z2+ z3+…+ zn–1= 0.

Taking n= 5, for example, and

EQUATING REAL AND

IMAGINARY PARTS

, this shows, for instance, that:

and

n-tuple (list) A set of nobjects taken in a particular

order is called an n-tuple. An n-tuple of numbers a1, a2,

…, an, in that order, is usually denoted (a1,a2,…,an) or

〈a1,a2,…,an〉. Two n-tuples (a1,a2,…,an) and (b1,b2,…,bn)

are equal if, and only if, corresponding entries match:

a1= b1, a2= b2,…, an= bn. Thus, for instance, (2,1.3)

and (1,2,3) are distinct 3-tuples.

A 3-tuple is called a “triple,” and a 4-tuple a

“quadruple.” When n= 2, an n-tuple is called an

ordered pair.

An n-tuple of numbers can represent a point in n-

dimensional space, a finite

SEQUENCE

, or, if angled

brackets are used, an n-dimensional

VECTOR

. An

ordered

PARTITION

of a number Nis an n-tuple of

numbers whose entries sum to N.

See also

ORDERED SET

.

number The development of different types of num-

bers can be seen as motivated by the need for solving

different types of equations. For example, the counting

numbers (that is, the

NATURAL NUMBERS

N) suffice for

solving any equation of the type x+ 2 = 5, for instance,

but not an equation of the type x+ 5 = 2. (There is no

solution to this equation within the set of counting

numbers.) This motivates the introduction of

NEGATIVE

NUMBERS

and the construction of the

INTEGERS

Z. But

this set is not always sufficient for solving equations of

the type 5x= 3, for instance. Desiring solutions to

equations of this type leads to the construction of

FRACTION

s and the set of all

RATIONAL NUMBERS

Q.

Unfortunately, again, not all equations can be solved

within this system. For example, the equation x2–2 = 0

has no rational solution. Extending the set of rational

numbers to include solutions to equations of this type

introduces

IRRATIONAL NUMBERS

and the construction

of the

REAL NUMBER

system R. Yet this new system also

does not suffice for solving all equations. With the

introduction of a single additional number, denoted i,