Frequently used Theorems and Conjectures
Fermat’s Little Theorem
Let p be a prime number. Given any positive integer a co-prime with p,
then
ap−1
1 (mod p).
The Prime Number Theorem
As x ∞,
π(x) = (1 + o(1))Li(x),
with
Li(x) =
x
log x
+
x
log2
x
+ 2!
x
log3
x
+ . . . + (r 1)!
x
logr
x
+ O
x
logr+1
x
,
where r is any given fixed integer.
The Chinese Remainder Theorem
Let m1, m2, . . . , mr be co-prime integers, and let a1, a2, . . . , ar be arbi-
trary integers. Then the system of congruences









n a1 (mod m1)
n a2 (mod m2)
.
.
.
n ar (mod mr)
has a solution given by
n0 =
r
i=1
m
mi
biai,
where m = m1m2 . . . mr and where each bi is the solution of the congru-
ence (m/mi)bi 1 (mod mi).
xvii
Previous Page Next Page