[Notations j

Let N , Z , Q , R an d C stan d respectivel y fo r th e se t o f positiv e integer s (als o

called natura l numbers) , th e se t o f integers, th e se t o f rational numbers , th e se t o f

real number s an d th e se t o f complex numbers .

Unless indicate d otherwise ,

• th e letter s a , 6, c, d, z, j, k^l^m^n^r an d s stan d fo r integers ,

• th e letter s p an d q stand fo r prim e numbers ,

• th e letters p\, p

2

P3, PA ? Ps, P6»P7 • • • represent th e sequence of prime num-

bers 2,3,5,7,11,13,17,.. . ,

• b y twin primes, we mean a pair of prime numbers {p, q] such that q = p- f 2.

Given a n intege r n 2 , we often writ e

for it s canonical representation a s a product o f distinct prim e powers : her e the q^s

are th e prime s dividin g n writte n i n increasin g orde r an d th e exponent s a^' s ar e

positive integer s (se e Theorem 11).

[Some Classical Forms of Argument)

THEOREM

1 (Inductio n Principle) . Let S be a set of natural numbers having

the following two properties:

(i) 1 € 5 ,

(ii) ifk e S, then k + leS.

Then S = N.

THEOREM

2 (Pigeonhol e Principle) . If more than n objects are distributed

amongst n boxes, then one of the boxes must contain at least two objects.

THEOREM

3 (Inclusion-Exclusio n Principle) . Let A be a set containing N ele-

ments and let Pi , P2,..., P

r

be distinct properties that each element of A must

satisfy. Ifn(Pi

x

, Pi

2

,..., Pi

k

) stands for the number of elements of A having all the

properties P^ , Pi

2

,..., Pi

k

, then the number of elements of A having none of the r

properties is equal to

iV- (n(Px)+n(P

2

) + • • •+ n(Pr )) + (n(P

l 5

P2 )+n(P

l 5

P 3) + • • •+ n(P

r

_

l 5

Pr;

-(n(P

1

,P

2

,P

3

) + n(P 1,P

2

,P

4

) + -- - + n(P

r

_

2

,P

r

_ 1,P

r

))+-- -

+ ( - l ) r n ( P i , P

2

, . . . , P

r

) .

Inequalities

THEOREM

4 (Cauchy-Schwar z Inequality) . Let a±, a2 ,..., an, 61,62, ... , b

n

be

real numbers. Then

i=l ' i=l i=l

3