212 Appendix C

Appendix C: Fundamental Facts
Throughout the text, we will be using the notational devices for multiplica-
x The Sum Notation
In general, if we have numbers am , am+1 , В· В· В· , an (m в‰¤ n), we may write
their sum as
n
ai = am + am+1 + В· В· В· an .
i=m

The letter i is the index of summation (and any letter may be used here), n is
the upper limit of summation, m is the lower limit of summation, and ai is a
summand.
The close cousin of the summation notation is the following symbol.
x The Product Symbol
The multiplicative analogue for the summation notation is the product sym-
bol denoted О , upper case Greek pi. Given am , am+1 , . . . , an в€€ R (m в‰¤ n),
their product is denoted:
n
ai = am am+1 В· В· В· an .
i=m

The letter i is the product index, m is the lower product limit, n is the upper
product limit, and ai is a multiplicand.
The notation m n for integers m, n means that m divides n, namely, there
exists an integer such that n = m. Behind the basic notion of divisibility is
a special kind of divisor that we will use throughout.

Deп¬Ѓnition C.1 (The Greatest Common Divisor)
If a, b в€€ Z are not both zero, then the greatest common divisor or gcd of a
and b is the natural number g such that g a, g b, and g is divisible by any
common divisor of a and b, denoted by g = gcd(a, b).

We have a special term for the case where the gcd is 1.

Deп¬Ѓnition C.2 (Relative Primality)
If a, b в€€ Z, and gcd(a, b) = 1, then a and b are said to be relatively prime or
coprime. Sometimes the phrase a is prime to b is also used. If {a1 , a2 , . . . , an }
has the property that gcd(ai , aj ) = 1, for each i = j, we say that the elements
are pairwise relatively prime.

Of particular importance for divisibility is the following algorithm.

В© 2003 by CRC Press LLC
Fundamental Facts 213

Theorem C.3 (The Division Algorithm)
If a в€€ N and b в€€ Z, then there exist unique integers q, r в€€ Z with 0 в‰¤ r < a,
and b = aq + r.

вњ·
Proof. See [163, Theorem 1.3.1, p. 33].
EuclidвЂ™s celebrated algorithm tells us how to п¬Ѓnd the gcd based upon the
division algorithm.

Theorem C.4 (The Euclidean Algorithm)
Let a, b в€€ Z (a в‰Ґ b > 0), and set a = rв€’1 , b = r0 . By repeatedly applying
the Division Algorithm, we get rjв€’1 = rj qj+1 + rj+1 with 0 < rj+1 < rj for
all 0 в‰¤ j < n, where n is the least nonnegative number such that rn+1 = 0, in
which case gcd(a, b) = rn .

вњ·
Proof. See [163, Theorem 1.3.3, p. 37].
We will have occasion to use the following generalization of Theorem C.4
throughout the text.

Theorem C.5 (The Extended Euclidean Algorithm)
Let a, b в€€ N, and let qi for i = 1, 2, . . . , n + 1 be the quotients obtained from
the application of the Euclidean Algorithm to п¬Ѓnd g = gcd(a, b), where n is the
least nonnegative integer such that rn+1 = 0. If sв€’1 = 1, s0 = 0, and

si = siв€’2 в€’ qnв€’i+2 siв€’1 ,

for i = 1, 2, . . . , n + 1, then

g = sn+1 a + sn b.

вњ·
Proof. See [163, Theorem 1.3.4, p. 38].
The elementary fundamental fact behind factorization algorithms studied in
Chapter 5 is the following.

Theorem C.6 (The Fundamental Theorem of Arithmetic)
r s
Let n в€€ N, n > 1. If n = i=1 pi = i=1 qi , where the pi and qi are primes,
then r = s, and the factors are the same if their order is ignored.

вњ·
Proof. See [163, Theorem 1.4.2, pp. 44вЂ“45].
Also in Chapter 5, we will need the following basic concept related to the
gcd.

Deп¬Ѓnition C.7 (The Least Common Multiple)
If a, b в€€ Z, then the smallest natural number which is a multiple of both a
and b is the least common multiple of a and b, denoted by lcm(a, b).

В© 2003 by CRC Press LLC
214 Appendix C

Throughout the text, we will be working within the following structure.

Deп¬Ѓnition C.8 (The Ring Z/nZ)
For n в€€ N, the set

Z/nZ = {0, 1, 2, . . . , n в€’ 1}

is called the Ring of Integers Modulo n, where m denotes the congruence class
of m modulo n.C.1

A special kind of division is given a special notation as follows. If n в€€ N
and a, b в€€ Z, we say that a is congruent to b modulo n if n (a в€’ b) and we
denote this by a в‰Ў b (mod n). If n (a в€’ b), then we write a в‰Ў b (mod n). With
the basic notion of congruential arithmetic comes the following notion that is
essential in many cryptographic algorithms such as RSA.

Deп¬Ѓnition C.9 (Modular Multiplicative Inverses)
Suppose that a в€€ Z, and n в€€ N. A multiplicative inverse of the integer a
modulo n is an integer x such that ax в‰Ў 1 (mod n). If x is the least positive
such inverse, then we call it the least multiplicative inverse of the integer a
modulo n, denoted x = aв€’1 .

Since cryptosystems related to RSA are essentially predicated upon the fol-
lowing celebrated result, we include it here for convenience.

Theorem C.10 (FermatвЂ™s Little Theorem)
If a в€€ Z, and p is a prime such that gcd(a, p) = 1, then apв€’1 в‰Ў 1 (mod p).

вњ·
Proof. See [163, Theorem 2.1.4, p. 80].
Knowing when the integers modulo n form a п¬Ѓeld is essential as is the struc-
ture of the units modulo n in what follows.

Theorem C.11 (The Field Z/pZ)
If n в€€ N, then Z/nZ is a п¬Ѓeld if and only if n is prime.

вњ·
Proof. See [165, Theorem 2.13, p. 62].
We employ the notation F в€— to denote the multiplicative group of nonzero
elements of a given п¬Ѓeld F . In particular, when we have a п¬Ѓnite п¬Ѓeld Z/pZ = Fp
of p elements for a given prime p, then (Z/pZ)в€— denotes the multiplicative group
of nonzero elements of Fp . This is tantamount to saying that (Z/pZ)в€— is the
group of units in Fp , and (Z/pZ)в€— is cyclic. Thus, this notation and notion may
C.1 When the context is clear and no confusion can arise when talking about elements of
Z/nZ, we will eliminate the overline bars.

В© 2003 by CRC Press LLC
Fundamental Facts 215

be generalized as follows. Let n в€€ N and let the group of units of Z/nZ be
denoted by (Z/nZ)в€— . Then
в€—
(Z/nZ) = {a в€€ Z/nZ : 0 в‰¤ a < n and gcd(a, n) = 1}. (C.12)

Numerous times we will need to solve systems of congruences for which the
following result from antiquity is most useful.

Theorem C.13 (Chinese Remainder Theorem)
Let ni в€€ N for natural numbers i в‰¤ k в€€ N be pairwise relatively prime, set
k
n = j=1 nj and let ri в€€ Z for i в‰¤ k. Then the system of k simultaneous linear
congruences given by:
x в‰Ў r1 (mod n1 ),
x в‰Ў r2 (mod n2 ),
.
.
.
x в‰Ў rk (mod nk ),
has a unique solution modulo n.

вњ·
Proof. See [165, Theorem 2.29, p. 69].
The natural generalization of FermatвЂ™s idea is the following, which provides
the modulus for the RSA enciphering and deciphering exponents, for instance.

Deп¬Ѓnition C.14 (EulerвЂ™s П†-Function)
For any n в€€ N the Euler П†-function, also known as EulerвЂ™s Totient П†(n) is
deп¬Ѓned to be the number of m в€€ N such that m < n and gcd(m, n) = 1.

Theorem C.15 (The Arithmetic of the Totient)
a
k
If n = j=1 pj j where the pj are distinct primes, then

k k k
a в€’1 a в€’1
a a
в€’ (pj в€’ 1)pj j
П†(pj j ) (pj j pj j )
П†(n) = = = .
j=1 j=1 j=1

вњ·
Proof. See [165, Theorem 2.22, p. 65].

Theorem C.16 (EulerвЂ™s Generalization of FermatвЂ™s Little Theorem)
If n в€€ N and m в€€ Z such that gcd(m, n) = 1, then mП†(n) в‰Ў 1 (mod n).

вњ·
Proof. See [163, Theorem 2.3.1, p. 90].

Example C.17 Let n в€€ N. Then the cardinality of (Z/nZ)в€— is П†(n). Hence, if
G is a subgroup of (Z/nZ)в€— , |G| П†(n).

В© 2003 by CRC Press LLC
216 Appendix C

The caclulus of integer orders and related primitive roots is an underlying
fundamental feature of cryptographic problems such as the discrete log problem.

Deп¬Ѓnition C.18 (Modular Order of an Integer)
Let m в€€ Z, n в€€ N and gcd(m, n) = 1. The order of m modulo n is the
smallest e в€€ N such that me в‰Ў 1 (mod n), denoted by e = ordn (m), and we say
that m belongs to the exponent e modulo n.

Note that the modular order of an integer given in Deп¬Ѓnition C.18 is the
same as the element order in the group (Z/nZ)в€— .

Proposition C.19 (Divisibility by the Order of an Integer)
If m в€€ Z, d, n в€€ N such that gcd(m, n) = 1, then md в‰Ў 1 (mod n) if and
only if ordn (m) d. In particular, ordn (m) П†(n).

вњ·
Proof. See [165, Proposition 4.3, p. 161].

Deп¬Ѓnition C.20 (Primitive Roots)
If m в€€ Z, n в€€ N and
ordn (m) = П†(n),
then m is called a primitive root modulo n. In other words, m is a primitive
root if it belongs to the exponent П†(n) modulo n.

Theorem C.21 (Primitive Root Theorem)
An integer n > 1 has a primitive root if and only if n is of the form 2a pb
where p is an odd prime, 0 в‰¤ a в‰¤ 1, and b в‰Ґ 0 or n = 4. Also, if m has a
primitive root, then it has П†(П†(n)) of them.

вњ·
Proof. See [165, Theorem 4.10, p. 165].
The following will be most useful in Chapter 4. The result can be easily
proved using Deп¬Ѓnition C.20 and Theorem C.10.

Proposition C.22 (Primitive Roots and Primality)

(1) If m is a primitive root modulo an odd prime p, then for any prime q
dividing (p в€’ 1), m(pв€’1)/q в‰Ў 1 (mod p).
(2) If m в€€ N, p is an odd prime, and m(pв€’1)/q в‰Ў 1 (mod p) for all primes
q (p в€’ 1), then m is a primitive root modulo p.

The following generalization of the Legendre symbol will be required for
understanding, for example, the primality test on page 84.

В© 2003 by CRC Press LLC
Fundamental Facts 217

Deп¬Ѓnition C.23 (The Jacobi Symbol)
e
Let n > 1 be an odd natural number with n = j=1 pj j where ej в€€ N and the
k

pj are distinct primes. Then the Jacobi Symbol of a with respect to n is given
by
k e
aj
a
= ,
n pj
j=1

for any a в€€ Z, where the symbols on the right are Legendre Symbols.

Theorem C.24 (Properties of the Jacobi Symbol)
Let m, n в€€ N, both odd, and a, b в€€ Z. Then
ab a b
(1) = .
n n n
a b
if a в‰Ў b (mod n).
(2) =
n n
a a a
(3) = .
mn m n
в€’1
= (в€’1)(nв€’1)/2 .
(4)
n
2 в€’1)/8
2
= (в€’1)(n
(5) .
n
(6) If gcd(a, n) = 1 where a в€€ N is odd, then
a n aв€’1 nв€’1
= (в€’1) 2 В· 2 ,
n a
which is the Quadratic Reciprocity Law for the Jacobi Symbol.

вњ·
Proof. See [165, Theorem 4.40, p. 175].

Theorem C.25 (EulerвЂ™s Criterion for Power Residue Congruences)
Let e, c в€€ N with e в‰Ґ 2, b в€€ Z, p > 2 is prime with p b, and g =
gcd(e, П†(pc )) b. Then the congruence

xe в‰Ў b (mod pc ) (C.26)

is solvable if and only if c
в‰Ў 1 (mod pc ).
)/g
bП†(p

вњ·
Proof. See [165, Theorem 4.17, p. 168].
When b = 1 and we are concenrned with quadratic residues this becomes
the following.

В© 2003 by CRC Press LLC
218 Appendix C

Corollary C.27 (EulerвЂ™s Criterion for Quadratic Residues)
Let p be an odd prime. Then

c
c(pв€’1)/2 в‰Ў (mod p).
p

Theorem C.28 (Solutions of Power Residue Congruences)
m
r
Let n be an odd natural number with n = j=1 pj j for distinct primes pj
(1 в‰¤ j в‰¤ r). Then
xt в‰Ў 1 (mod n)
m
r
gcd(t, П†(pj j )) solutions. Also, if
has exactly g = j=1

xt в‰Ў в€’1 (mod n)

has a solution, then it has g solutions.

вњ·
Proof. See [163, Theorem 3.3.2, p. 155].
Of course, the gem of number theory will come into play in our cryptographic
journey, so we state it here for п¬Ѓnger-tip reference.

Theorem C.29 (Prime Number Theorem)
Let the number of primes less than x be denoted by ПЂ(x). Then

ПЂ(x)
lim = 1,
xв†’в€ћ x/ log(x)

denoted by ПЂ(x) в€ј x/ log(x).C.2

вњ·
Proof. See .
We now provide a brief reminder of vector space basics and elementary
matrix theory that we will need to describe other concepts to be used in the
text.

x Vector Spaces
A vector space consists of an additive abelian group V and a п¬Ѓeld F together
with an operation called scalar multiplication of each element of V by each
element of F on the left, such that for each r, s в€€ F and each О±, ОІ в€€ V the
following conditions are satisп¬Ѓed:

C.30. rО± в€€ V .
C.31. r(sО±) = (rs)О±.
general, if f and g are functions of a real variable x, then f (x) в€ј g(x) means
C.2 In

limxв†’в€ћ f (x)/g(x) = 1. Such functions are said to be asymptotic.

В© 2003 by CRC Press LLC
Fundamental Facts 219

C.32. (r + s)О± = (rО±) + (sО±).

C.33. r(О± + ОІ) = (rО±) + (rОІ).
C.34. 1F О± = О±.

The set of elements of V are called vectors and the elements of F are called
scalars. The generally accepted abuse of language is to say that V is a vector
space over F . If V1 is a subset of a vector space V that is a vector space in its
own right, then V1 is called a subspace of V .

Deп¬Ѓnition C.35 (Bases, Dependence, and Finite Generation)
If S is a subset of a vector space V , then the intersection of all subspaces of
V containing S is called the subspace generated by S, or spanned by S. If there
is a п¬Ѓnite set S, and S generates V , then V is said to be п¬Ѓnitely generated. If
S = в€…, then S generates the zero vector space. If S = {m}, a singleton set, then
the subspace generated by S is said to be the cyclic subspace generated by m.
A subset S of a vector space V is said to be linearly independent provided
that for distinct s1 , s2 , . . . , sn в€€ S, and rj в€€ F for j = 1, 2, . . . , n,
n
rj sj = 0 implies that rj = 0 for j = 1, 2, . . . , n.
j=1

If S is not linearly independent, then it is called linearly dependent. A linearly
independent subset of a vector space that spans V is called a basis for V . The
number of elements in a basis is called the dimension of V . A hyperplane H is
an (n в€’ 1)-dimensional subspace of an n-dimensional vector space V .

Example C.36 For a given prime p, m, n в€€ N, the п¬Ѓnite п¬Ѓeld Fpn is an n-
dimensional vector space over Fpm with pmn elements.

x Basic Matrix Theory
If m, n в€€ N, then an m Г— n matrix (read вЂњm by n matrixвЂќ) is a rectangular
array of entries with m rows and n columns. For simplicity, we will assume that
the entries come from a п¬Ѓeld F . (For instance, in Section 8.1, we will be using
Fp to describe a secret sharing scheme base on vectors and matrices.) If A is
such a matrix, and ai,j denotes the entry in the ith row and j th column, then
пЈ« пЈ¶
a1,1 a1,2 В· В· В· a1,n
пЈ¬ a2,1 a2,2 В· В· В· a2,n пЈ·
пЈ¬ пЈ·
A = (ai,j ) = пЈ¬ . пЈ·.
. .
пЈ­. пЈё
. . .
. .
am,1 am,2 В· В· В· am,n

В© 2003 by CRC Press LLC
220 Appendix C

Two m Г— n matrices A = (ai,j ), and B = (bi,j ) are equal if and only if
ai,j = bi,j for all i and j. The matrix (aj,i ) is called the transpose of A, denoted
by
At = (aj,i ).

Addition of two m Г— n matrices A and B is done in the natural way.

A + B = (ai,j ) + (bi,j ) = (ai,j + bi,j ),
and if r в€€ F , then rA = r(ai,j ) = (rai,j ), called scalar multiplication.
Matrix products are deп¬Ѓned by the following.
If A = (ai,j ) is an m Г— n matrix and B = (bj,k ) is an n Г— r matrix, then the
product of A and B is deп¬Ѓned as the m Г— r matrix:
AB = (ai,j )(bj,k ) = (ci,k ),
where
n
ci,k = ai, b ,k .
=1
Multiplication, if deп¬Ѓned, is associative, and distributive over addition. If m =
n, then the identity n Г— n matrix:
пЈ« пЈ¶
1F 0 В· В· В· 0
пЈ¬ 0 1F В· В· В· 0 пЈ·
пЈ¬ пЈ·
In = пЈ¬ . . пЈ·,
. .
пЈ­. .пЈё
. .
. . . .
В· В· В· 1F
0 0
is called the n Г— n identity matrix, where 1F is the identity of F .
Another important aspect of matrices that we will need throughout the text
is motivated by the following. Consider the 2 Г— 2 matrix with entries from F :
ab
A= ,
cd
then ad в€’ bc is called the determinant of A, denoted by det(A). More generally,
we may deп¬Ѓne the determinant of any n Г— n matrix with entries from F for any
n в€€ N. The determinant of any r в€€ F is just det(r) = r. Thus, we have the
deп¬Ѓnitions for n = 1, 2, and we may now give the general deп¬Ѓnition inductively.
The deп¬Ѓnition of the determinant of a 3 Г— 3 matrix
пЈ« пЈ¶
a1,1 a1,2 a1,3
A = пЈ­ a2,1 a2,2 a2,3 пЈё
a3,1 a3,2 a3,3
is deп¬Ѓned in terms of the above deп¬Ѓnition of the determinant of a 2 Г— 2 matrix,
namely, det(A) is given by
a2,2 a2,3 a2,1 a2,3 a2,1 a2,2
в€’ a1,2 det
a1,1 det + a1,3 det .
a3,2 a3,3 a3,1 a3,3 a3,1 a3,2

В© 2003 by CRC Press LLC
Fundamental Facts 221

Therefore, we may inductively deп¬Ѓne the determinant of any n Г— n matrix in
this fashion. Assume that we have deп¬Ѓned the determinant of an n Г— n matrix.
Then we deп¬Ѓne the determinant of an (n + 1) Г— (n + 1) matrix A = (ai,j ) as
follows. First, we let Ai,j denote the n Г— n matrix obtained from A by deleting
the ith row and j th column. Then we deп¬Ѓne the minor of Ai,j at position (i, j)
to be det(Ai,j ). The cofactor of Ai,j is deп¬Ѓned to be

cof(Ai,j ) = (в€’1)i+j det(Ai,j ).

We may now deп¬Ѓne the determinant of A by

det(A) = ai,1 cof(Ai,1 ) + ai,2 cof(Ai,2 ) + В· В· В· + ai,n+1 cof(Ai,n+1 ). (C.37)

This is called the expansion of a determinant by cofactors along the ith row of
A. Similarly, we may expand along a column of A.

det(A) = a1,j cof(A1,j ) + a2,j cof(A2,j ) + В· В· В· + an+1,j cof(An+1,j ),

called the cofactor expansion along the j th column of A. Both expansions can
be shown to be identical. Hence, a determinant may be viewed as a function
that assigns a real number to an n Г— n matrix, and the above gives a method
for п¬Ѓnding that number.
If A is an n Г— n matrix with entries from F , then A is said to be invertible,
or nonsingular if there is a unique matrix denoted by Aв€’1 such that

AAв€’1 = In = Aв€’1 A.

Another important fact, that we will need for instance in Chapter 8, is a
result which follows from cofactor expansions.

Theorem C.38 (CramerвЂ™s Rule)
Let A = (ai,j ) be the coeп¬ѓcient matrix of the following system of n linear
equations in n unknowns:

a1,1 x1 + a1,2 x2 + В· В· В· + a1,n xn = b1

a2,1 x1 + a2,2 x2 + В· В· В· + a2,n xn = b2
. . . . .
. . . . .
. . . . .
an,1 x1 + an,2 x2 + В· В· В· + an,n xn = bn ,
over a п¬Ѓeld F . If det(A) = 0, then the system has a solution given by:
n
1
(1 в‰¤ j в‰¤ n).
(в€’1)i+j bi det(Ai,j ) ,
xj =
det(A) i=1

В© 2003 by CRC Press LLC
222 Appendix C

Of particular importance is a special matrix called the Vandermonde matrix,
of order t > 1, which is given as follows.

пЈ« пЈ¶
В· В· В· xtв€’1
1 x1 1
пЈ¬ пЈ·
В· В· В· xtв€’1
1 x2
пЈ¬ пЈ·
2
A=пЈ¬ пЈ·,
.. . .
пЈ­ пЈё
.. . .
.. . .
В· В· В· xt
tв€’1
1 xt
where
(xk в€’ xi )
det(A) =
1в‰¤i<kв‰¤t

(see Exercise 8.17 on page 159).
A notion that uses vector spaces and matrix theory is the following, which
we will use in Chapters 5 and 8, for instance.

x Gaussian Elimination
The term Gaussian elimination refers to an eп¬ѓcient algorithm for п¬Ѓnding
linear dependency relations among vectors in a vector space over a suitable п¬Ѓeld.
Suppose that we have vectors vj = (v1,j , v2,j , . . . , vn,j ) for j = 1, 2, . . . , m over
a п¬Ѓeld F . What we seek п¬Ѓeld elements c1 , c2 , . . . , cm в€€ F such that
m
в€’
в†’
cj vj = 0 , (C.39)
i=j
в€’
в†’
where cj vj = (cj v1,j , cj v2,j , . . . , cj vn,j ), and 0 = (0, 0, . . . , 0) is the zero vector
m
of length n. Since i=j cj vj , the relation given in (C.39) where not all coeп¬ѓ-
cients are 0, is a linear dependency relation (see Deп¬Ѓnition C.35 on page 219).
Gaussian elimination uses the basic notions of linear algebra to deп¬Ѓne matrices
with the vectors vj as columns, then performs elementary row operations to
put them into a form to determine the dependency relations therefrom, if there
are any. The basic point from elementary linear algebra is that if the number
of vectors is greater than the dimension of the vector space over the п¬Ѓeld, then
there must be a dependency relation. For instance, if m > n in (C.39), then at
least one of the cj = 0. This idea will be used in the text, especially for factoring
techniques in Chapter 5.
The following will be needed in our discussions on secret sharing in Section
8.1, for instance.

Theorem C.40 (The Lagrange Interpolation Formula) Let F be a п¬Ѓeld,
and let aj for j = 0, 1, 2, . . . , n be distinct elements of F . If cj for j =
0, 1, 2, . . . , n are any elements of F , then
n
(x в€’ a0 ) В· В· В· (x в€’ ajв€’1 )(x в€’ aj+1 ) В· В· В· (x в€’ an )
f (x) = cj
(aj в€’ a0 ) В· В· В· (aj в€’ ajв€’1 )(aj в€’ aj+1 ) В· В· В· (aj в€’ an )
j=0

В© 2003 by CRC Press LLC
Fundamental Facts 223

is the unique polynomial in F [x] such that f (aj ) = cj for all j = 0, 1, . . . , n.

We will need to address the notion of convergents of continued fractions, for
example in Section 6.2, so we present some basics here.

x Continued Fractions

Deп¬Ѓnition C.41 (Continued Fractions)
If q j в€€ R where j в€€ Z is nonnegative and q j в€€ R+ for j > 0, then an
expression of the form
1
О± = q0 +
1
q1 +
q 2+
..
.
1
+
1
qk +
q k+1
..
.
is called a continued fraction. If q k в€€ Z for all k в‰Ґ 0, then it is called a
simple continued fraction,C.3 denoted by q 0 ; q 1 , . . . , q k , q k+1 , . . . . If there exists
a nonnegative integer n such that qk = 0 for all k в‰Ґ n, then the continued
fraction is called п¬Ѓnite. If no such n exists, then it is called inп¬Ѓnite.

Deп¬Ѓnition C.42 (Convergents) Let n в€€ N and let О± have continued fraction
expansion q 0 ; q 1 , . . . , q n , . . . for q j в€€ R+ when j > 0. Then

Ck = q 0 ; q 1 , . . . , q k

is the k th convergent of О± for any nonnegative integer k.

Theorem C.43 (Finite Simple Continued Fractions Are Rational)
Let О± в€€ R. Then О± в€€ Q if and only if О± can be written as a п¬Ѓnite simple
continued fraction.

C.3 Note that the classical deп¬Ѓnition of a simple continued fraction is a continued fraction that
arises from the reciprocals as in the Euclidean Algorithm, so the вЂњnumeratorsвЂќ are all 1 and
the denominators all integers. This is to distinguish from more general continued fractions in
which the numerators and denominators can be functions of a complex variable, for instance.
Simple continued fractions are also called regular continued fractions in the literature.

В© 2003 by CRC Press LLC