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).
Previous Page Next Page