Homework SourseGiven n 1 natural numbers say a1 a2 an1 all less than o
Given n + 1 natural numbers, say a1, a2, . . . , an+1, all less than or equal to 2n, then there exists a pair, say ai and aj with i 6= j, such that ai|aj
Solution
Ans-
his set of notes on number theory was originally written in 1995 for students
at the IMO level. It covers the basic background material that an IMO
student should be familiar with. This text is meant to be a reference, and
not
a replacement but rather a supplement to a number theory textbook;
several are given at the back. Proofs are given when appropriate, or when
they illustrate some insight or important idea. The problems are culled from
various sources, many from actual contests and olympiads, and in general
are very difficult. The author welcomes any corrections or suggestions.
1 Divisibility
For integers
a
and
b
, we say that
a
divides
b
, or that
a
is a
divisor
(or
factor
) of
b
, or that
b
is a
multiple
of
a
, if there exists an integer
c
such
that
b
=
ca
, and we denote this by
a
|
b
. Otherwise,
a
does not divide
b
, and
we denote this by
a
-
b
. A positive integer
p
is a
prime
if the only divisors of
p
are 1 and
p
. If
p
k
|
a
and
p
k
+1
-
a
where
p
is a prime, i.e.
p
k
is the highest
power of
p
dividing
a
, then we denote this by
p
k
k
a
.
Useful Facts
•
If
a
,
b >
0, and
a
|
b
, then
a
b
.
•
If
a
|
b
1
,
a
|
b
2
, . . . ,
a
|
b
n
, then for any integers
c
1
,
c
2
, . . . ,
c
n
,
