xiv Notations

• The factorization of a number usually appears in the form

n = q1

α1

· q2

α2

· . . . · qr

αr

,

where q1 q2 . . . qr are the r distinct prime numbers dividing n and

where α1, α2, . . . , αr are positive integers. For instance, we write

11 560 =

23

· 5 ·

172.

It may happen that the factorization of a large number takes on a particular

form, such as

1227

+ 1 = 257 · P136;

in this case, the expression P136 stands for a (known) 136 digit prime number

which there is no need to write at length, since it can be obtained explicitly by

simply dividing

1227

+ 1 by 257. Another possible situation could occur, as for

instance:

1228

+ 1 = 8253953 · 295278642689 · C258;

in this case, the expression C258 stands for a composite 258 digit number for

which no non trivial factorization is known.

• In order to compare the size of certain expressions in the neighborhood of infin-

ity, we use various notations, some of which have been introduced by Landau,

namely O(. . .) and o(. . .). Hence, given two functions f and g defined on [a, ∞)

(where a ≥ 0), we write:

(i) f(x) = O(g(x)) if there exist two constants M 0 and x0 for which

|f(x)| Mg(x) for all x ≥ x0; in particular, f(x) = O(1) if f(x) is

a bounded function; moreover, instead of writing f(x) = O(g(x)), we

sometimes write f(x) g(x); thus we have

x =

O(x2),

sin x = O(1), log x =

O(x1/10), 2x2

+

x

3

x2;

(ii) f(x) = o(g(x)) if, for each ε 0, there exists a constant x0 = x0(ε) such

that |f(x)| εg(x) for all x ≥ x0; thus we have

1

x

= o(1), sin x = o(x), log x = o(x),

x4

=

o(ex);

(iii) f(x) = Ω(g(x)) if there exist two constants M 0 and x0 such that

|f(x)| M|g(x)| for all x ≥ x0; instead of writing f(x) = Ω(g(x)), we

sometimes write f(x) g(x); thus we have

x = Ω(

√

x),

√

x = Ω(log x),

ex

=

Ω(x4), xex ex;

(iv) f(x) ∼ g(x) to mean that lim

x→∞

f(x)

g(x)

= 1; thus, as x → ∞, we have

1

x

∼ 0,

sin 1/x

1/x

∼ 1,

x2

+ x ∼

x2.

(v) f(x) ≈ g(x) to mean that we have both f(x) g(x) and g(x) f(x).