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