4 1001 PROBLEM S I N CLASSICA L NUMBE R THEOR Y
THEOREM
5 (ArithmeticGeometri c Mean s Inequality) . Let a\,a
2
, . ..,an be
positive real numbers. Then
(
win s a
1
+a2\ + a
n
(aio2 .. . any/n ,
n
with equality if and only if a\ = a
2
= .. . = a n.
[Divisibility]
DEFINITION 1 (Binomia l Coefficients) . Let n be a positive integer and k an
integer satisfying 0 k n. We define the binomial coefficient Q ) by
n\
K
kJ kl(nk)V
where 0 ! = 1 and n\ = n(n  1) • • • 3 • 2 • 1.
THEOREM
6 (Binomia l Theorem) . Let a, b £ R and n £ N . Then
£0."
fc=0
In particular , i t follow s fro m Theore m 6 tha t
D1)*(fc)
=
(1 1 )B
= °
an d
E ft) = a +
DB
= 2.
fc=o x y fe=o v 7
DEFINITION
2 . Le t a , 6 € Z wit h a ^ 0 . W e say tha t a divides b if there exists
an integer c such that b — ac, in which case we write a\b and say that a is a divisor
ofb. If a does not divide b, we write aj(b. In the case where a\b and 1 a b, we
shall say that a is a proper divisor ofb. We write p
a\\n
to mean that p
a\n
while
pa+1
does not divide n.
THEOREM
7 (Euclidea n Division) . Let a, b £ Z , a 0 . Then, there exist
integers q and r such that b = aq + r, where 0 r a. Moreover, if a does not
divide b, then 0 r a.
DEFINITION 3 (Greates t Commo n Divisor) . Let a, b £ Z \ {0} . The greatest
common divisor (or GCD) of a and b, denoted by (o , 6), is the unique positive
integer d satisfying the following two conditions:
(i) d\a and d\b, (ii) if c\a and c\b, then c d.
Similarly, if a\,a 2, • .., a
r
£ Z \ {0}
?
the GCD of ai,a2,... , ar, denoted by
(ai,a2,... ,a
r
), i s th e unique positive integer d satisfying the following two con
ditions:
(i) d\ai, d\a 2, •.. , d\a r, (ii) if c\a\, c\a 2, ... , ca r, then c d.
THEOREM
8 . Let ai , a2 ,..., ar e Z\{0} . The n there exist integersx±, x 2,..., x
r
such tha t (ai , a2, • • •, «r) = Q\X\ + a2# 2 + • • • + a rxr.
THEOREM
9 . Let a,b £ Z b e suc h tha t a 6 ^ 0 . Le t d be a positive integer.
Then
d\a and d\b,
(G, j ^ ^ 
c

a a i 3
j
c
 ^ _ ^
c
 ^