|
I Fundamentals, 1. Divisibility
Prove that X contains two distinct elements x
,
y such that x
=
1
and x di-
vides y.
(1996 Balkan Mathematical Olympiad)
Solution.
Take
m
such that
m
2
<
p
< (
m
+
1
)
2
and write
p
=
k
+
m
2
, with
1
≤
k
≤
2
m
. Since
p
−
(
m
−
k
)
2
=
k
(
2
m
−
k
+
1
)
, we have
p
−
m
2
|
p
−
(
m
−
k
)
2
.
Thus we are done by taking
x
=
p
−
m
2
=
k
and
y
=
p
− |
m
−
k
|
2
unless either
k
=
p
−
m
2
=
1 (which gives
x
=
1),
k
=
m
(which gives
|
m
−
k
| =
0), or
k
=
2
m
(which gives
x
=
y
). The latter two cases give
p
=
m
(
m
+
1
)
and
p
=
m
(
m
+
2
)
, respectively, which cannot occur, since
p
is prime. In the remaining
case,
p
=
m
2
+
1, which forces
m
be even. Hence
x
=
p
−
(
m
−
1
)
2
=
2
m
divides
y
=
p
−
1
=
m
2
is the required example.
Additional Problems
Problem 1.2.10.
For each integer
n
such that
n
=
p
1
p
2
p
3
p
4
, where
p
1
,
p
2
,
p
3
,
p
4
are distinct primes, let
d
1
=
1
<
d
2
<
d
3
<
· · ·
<
d
16
=
n
be the sixteen positive integers that divide
n
. Prove that if
n
<
1995, then
d
9
−
d
8
=
22.
(1995 Irish Mathematical Olympiad)
Problem 1.2.11.
Prove that there are infinitely many positive integers
a
such that
the sequence
(
z
n
)
n
≥
1
,
z
n
=
n
4
+
a
, does not contain any prime number.
(11th International Mathematical Olympiad)
Problem 1.2.12.
Let
p
,
q
,
r
be distinct prime numbers and let
A
be the set
A
= {
p
a
q
b
r
c
:
0
≤
a
,
b
,
c
≤
5
}
.
Find the smallest integer
n
such that every
n
-element subset of
A
contains two
distinct elements
x
,
y
such that
x
divides
y
.
(1997 Romanian Mathematical Olympiad)
Problem 1.2.13.
Prove Bonse’s inequality:
p
1
p
2
· · ·
p
n
>
p
2
n
+
1
for
n
≥
4, where
p
1
=
2,
p
2
=
3
, . . .
is the increasing sequence of prime
numbers.
1.3. The Greatest Common Divisor and Least Common Multiple
17
Problem 1.2.14.
Show that there exists a set
A
of positive integers with the fol-
lowing property: for any infinite set
S
of primes, there exist two positive integers
m
∈
A
and
n
∈
A
each of which is a product of
k
distinct elements of
S
for some
k
≥
2.
(35th International Mathematical Olympiad)
Problem 1.2.15.
Let
n
be an integer,
n
≥
2. Show that if
k
2
+
k
+
n
is a prime
number for every integer
k
, 0
≤
k
≤
√
n
/
3, then
k
2
+
k
+
n
is a prime number
for every
k
, 0
≤
k
≤
n
−
2.
(28th International Mathematical Olympiad)
Problem 1.2.16.
A sequence
q
1
,
q
2
, . . .
of primes satisfies the following condi-
tion: for
n
≥
3,
q
n
is the greatest prime divisor of
q
n
−
1
+
q
n
−
2
+
2000. Prove that
the sequence is bounded.
(2000 Polish Mathematical Olympiad)
Problem 1.2.17.
Let
a
>
b
>
c
>
d
be positive integers and suppose
ac
+
bd
=
(
b
+
d
+
a
−
c
)(
b
+
d
−
a
+
c
).
Prove that
ab
+
cd
is not prime.
(42nd International Mathematical Olympiad)
Problem 1.2.18.
Find the least odd positive integer
n
such that for each prime
p
,
n
2
−
1
4
+
np
4
+
p
8
is divisible by at least four primes.
(Mathematical Reflections)
1.3
The Greatest Common Divisor and
the Least Common Multiple
For a positive integer
k
we denote by
D
k
the set of all its positive divisors. It is
clear that
D
k
is a finite set. For positive integers
m
,
n
the maximal element in the
set
D
m
∩
D
n
is called the
greatest common divisor
of
m
and
n
and is denoted by
gcd
(
m
,
n
)
.
Another characterization of gcd
(
m
,
n
)
is given by the property
d
|
gcd
(
m
,
n
)
if and only if
d
|
m
and
d
|
n
. Note that gcd
(
0
,
n
)
=
n
.
If
D
m
∩
D
n
= {
1
}
, we have gcd
(
m
,
n
)
=
1 and we say that
m
and
n
are
relatively prime
.
The following properties can be directly derived from the definition above.
(1) If
d
=
gcd
(
m
,
n
)
,
m
=
dm
,
n
=
dn
, then gcd
(
m
,
n
)
=
1.
18
I Fundamentals, 1. Divisibility
(2) If
m
=
dm
,
n
=
dn
, and gcd
(
m
,
n
)
=
1, then
d
=
gcd
(
m
,
n
)
.
(3) If
d
is a common divisor of
m
and
n
, then
d
divides gcd
(
m
,
n
)
.
This property says, in particular, that gcd
(
m
,
n
)
is the largest common di-
visor of
m
and
n
, as the name implies.
(4) If
m
=
p
α
1
1
· · ·
p
α
k
k
and
n
=
p
β
1
1
· · ·
p
β
k
k
,
α
i
, β
i
≥
0,
i
=
1
, . . . ,
k
, then
gcd
(
m
,
n
)
=
p
min
(α
1
,β
1
)
1
· · ·
p
min
(α
k
,β
k
)
k
.
(5) If
m
=
nq
+
r
, then gcd
(
m
,
n
)
=
gcd
(
n
,
r
)
.
Let us prove the last property. Set
d
=
gcd
(
m
,
n
)
and
d
=
gcd
(
n
,
r
)
. Because
d
|
m
and
d
|
n
it follows that
d
|
r
. Hence
d
|
d
. Conversely, from
d
|
n
and
d
|
r
it follows that
d
|
m
, so
d
|
d
. Thus
d
=
d
.
A useful algorithm for finding the greatest common divisor of two positive
integers is the
Euclidean algorithm
. It consists in repeated application of the divi-
sion algorithm:
m
=
nq
1
+
r
1
,
1
≤
r
1
<
n
,
n
=
r
1
q
2
+
r
2
,
1
≤
r
2
<
r
1
,
. . .
r
k
−
2
=
r
k
−
1
q
k
+
r
k
,
1
≤
r
k
<
r
k
−
1
,
r
k
−
1
=
r
k
q
k
+
1
+
r
k
+
1
,
r
k
+
1
=
0
.
This chain of equalities is finite because the descending sequence
n
>
r
1
>
r
2
>
· · ·
>
r
k
≥
0 of integers cannot go on indefinitely.
The last nonzero remainder,
r
k
, is the greatest common divisor of
m
and
n
.
Indeed, by applying successively property (5) above, we obtain
gcd
(
m
,
n
)
=
gcd
(
n
,
r
1
)
=
gcd
(
r
1
,
r
2
)
= · · · =
gcd
(
r
k
−
1
,
r
k
)
=
r
k
.
Proposition 1.3.1.
For positive integers m and n, there exist integers a and b such
that am
+
bn
=
gcd
(
m
,
n
)
.
Proof.
From the Euclidean algorithm it follows that
r
1
=
m
−
nq
1
,
r
2
= −
mq
2
+
n
(
1
+
q
1
q
2
), . . . .
In general,
r
i
=
m
α
i
+
n
β
i
,
i
=
1
, . . . ,
k
. Because
r
i
+
1
=
r
i
−
1
−
r
i
q
i
+
1
, it
follows that
α
i
+
1
=
α
i
−
1
−
q
i
+
1
α
i
,
β
i
+
1
=
β
i
−
1
−
q
i
+
1
β
i
,
i
=
2
, . . . ,
k
−
1. Finally, we obtain gcd
(
m
,
n
)
=
r
k
=
α
k
m
+
β
k
n
.
Do'stlaringiz bilan baham: |
