|
5
Basic Principles in Number Theory
5.1
Two Simple Principles
5.1.1
Extremal Arguments
In many problems it is useful to consider the least or the greatest element with
a certain property. Very often such a choice leads to the construction of other
elements or to a contradiction.
Problem 5.1.1.
Show that there exist infinitely many positive integers n such that
the largest prime divisor of n
4
+
1
is greater than
2
n.
(2001 St. Petersburg City Mathematical Olympiad)
Solution.
First we prove the following result.
Lemma.
There are infinitely many numbers that are prime divisors of m
4
+
1
for
some m.
Proof.
Suppose that there are only finite number of such primes. Let
p
1
,
p
2
,
. . .
,
p
k
be all of them. Let
p
be any prime divisor of
(
p
1
p
2
· · ·
p
k
)
4
+
1. This num-
ber cannot equal any
p
i
, a contradiction to our assumption, which proves the
lemma.
Let
P
be the set of all numbers that are prime divisors of
m
4
+
1 for some
m
. Pick any
p
from
P
and
m
from
Z
, such that
p
divides
m
4
+
1. Let
r
be the
residue of
m
modulo
p
. We have
r
<
p
,
p
|
r
4
+
1, and
p
|
(
p
−
r
)
4
+
1. Let
n
be the minimum of
r
and
p
−
r
. It follows that
n
<
p
/
2 and
p
>
2
n
and of
course
p
|
n
4
+
1. Thus we have found for each
p
∈
P
a good number
n
p
. Since
n
p
≥
4
√
p
−
1, and
P
is infinite, the set
{
n
p
:
p
∈
P
}
is also infinite.
Remark.
Essentially the same proof shows that for any polynomial
P
(
x
)
with
integer coefficients, there are infinitely many primes that divide
P
(
n
)
for some
integer
n
.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
89
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/
_5,
b11 56
8
90
I Fundamentals, 5. Basic Principles in Number Theory
Problem 5.1.2.
Let a
1
,
a
2
, . . .
be a strictly increasing sequence of positive inte-
gers such that
gcd
(
a
m
,
a
n
)
=
a
gcd
(
m
,
n
)
for all positive integers m and n. There
exists a least positive integer k for which there exist positive integers r
<
k and
s
>
k such that a
2
k
=
a
r
a
s
. Prove that r divides k and that k divides s.
(2001 Indian Mathematical Olympiad)
Solution.
We begin by proving a lemma.
Lemma.
If positive integers a
,
b
,
c satisfy b
2
=
ac, then
gcd
(
a
,
b
)
2
=
gcd
(
a
,
c
)
·
a
.
Proof.
Consider any prime
p
. Let
e
be the highest exponent such that
p
e
divides
b
,
and let
e
1
and
e
2
be the corresponding highest exponents for
a
and
c
, respectively.
Because
b
2
=
ac
, we have 2
e
=
e
1
+
e
2
. If
e
1
≥
e
, then the highest powers of
p
that divide gcd
(
a
,
b
)
, gcd
(
a
,
c
)
, and
a
are
e
,
e
2
, and
e
1
, respectively. Otherwise,
these highest powers are all
e
1
. Therefore, in both cases, the exponent of
p
on the
left side of the desired equation is the same as the exponent of
p
on the right side.
The desired result follows.
Applying the lemma to the given equation
a
2
k
=
a
r
a
s
, we have
gcd
(
a
r
,
a
k
)
2
=
gcd
(
a
r
,
a
s
)
a
r
.
It now follows from the given equation that
a
2
gcd
(
r
,
k
)
=
a
gcd
(
r
,
s
)
a
r
.
Assume, for sake of contradiction, that gcd
(
r
,
k
) <
r
, so that
a
gcd
(
r
,
k
)
<
a
r
. Then from the above equation, it follows that
a
gcd
(
r
,
k
)
>
a
gcd
(
r
,
s
)
,
so that gcd
(
r
,
k
) >
gcd
(
r
,
s
)
. But then we have that
(
k
0
,
r
0
,
s
0
)
=
gcd
(
r
,
k
)
,
gcd
(
r
,
s
),
r
satisfies
a
2
k
0
=
a
r
0
a
s
0
with
r
0
<
k
0
<
s
0
and
k
0
<
r
<
k
, contradict-
ing the minimality of
k
.
Thus, we must have gcd
(
r
,
k
)
=
r
, implying that
r
|
k
. Then
gcd
(
a
r
,
a
k
)
=
a
gcd
(
r
,
k
)
=
a
r
,
so
a
r
|
a
k
. Thus
a
s
=
a
k
a
k
a
r
is an integer multiple of
a
k
, and
a
gcd
(
k
,
s
)
=
gcd
(
a
k
,
a
s
)
=
a
k
.
Because
a
1
,
a
2
, . . .
is increasing, it follows that gcd
(
k
,
s
)
=
k
. Therefore,
k
|
s
, completing the proof.
5.1. Two Simple Principles
91
Problem 5.1.3.
Determine all pairs
(
n
,
p
)
of positive integers such that p is a
prime, n
≤
2
p and
(
p
−
1
)
n
+
1
is divisible by n
p
−
1
.
(40th International Mathematical Olympiad)
Solution.
All pairs
(
1
,
p
)
, where
p
is a prime number, satisfy the conditions.
When
p
=
2, it follows that
n
=
2, and thus the pair
(
2
,
2
)
is also a solution of
the problem. Thus, we may suppose
p
≥
3 and let
n
be such that
n
≤
2
p
and
n
p
−
1
divides
(
p
−
1
)
n
+
1. Since
(
p
−
1
)
n
+
1 is odd number, it follows that
n
<
2
p
. We shall prove that
n
=
p
.
Let
q
be a minimal prime divisor of
n
. Since
q
|
n
and
n
p
−
1
|
(
p
−
1
)
n
+
1,
it follows that
(
p
−
1
)
n
≡ −
1
(
mod
q
)
. Since
n
and
q
−
1 are relatively prime
numbers, we may write
an
+
b
(
q
−
1
)
=
1 for some integers
a
and
b
.
We have
p
−
1
≡
(
p
−
1
)
an
+
b
(
q
−
1
)
≡
(
p
−
1
)
na
(
p
−
1
)
(
q
−
1
)
b
≡
(
−
1
)
a
1
b
≡ −
1
(
mod
q
),
because
a
must be odd. This shows that
q
|
p
, and therefore
q
=
p
. Since
n
<
2
p
,
by the consideration of
q
, we have
n
=
p
.
Let consider in these conditions the original divisibility
p
p
−
1
|
(
p
−
1
)
p
+
1
=
p
p
−
p
1
p
p
−
1
+
p
2
p
p
−
2
− · · · +
p
p
−
1
p
−
1
+
1
=
p
2
1
p
p
−
2
−
p
1
p
p
−
3
+
p
2
p
p
−
4
− · · · +
1
2
.
Therefore
p
−
1
=
2,
p
=
3, and we then obtain the pair (3
,
3).
The conclusion is that the required solutions are
(
1
,
p
)
,
(
2
,
2
)
, and
(
3
,
3
)
,
where
p
is an arbitrary prime.
Remark.
With a little bit more work, we can even erase the condition
n
≤
2
p
.
5.1.2
The Pigeonhole Principle
Let
S
be a nonempty set and let
S
1
,
S
2
, . . . ,
S
n
be a partition of
S
(that is,
S
1
∪
S
2
∪ · · · ∪
S
n
=
S
and
S
i
∩
S
j
= ∅
for
i
=
j
). If
a
1
,
a
2
, . . . ,
a
n
+
1
are distinct
elements in
S
, then there is a
k
∈ {
1
,
2
, . . . ,
n
}
such that at least two of these
elements belong to
S
k
.
This simple observation is called the
pigeonhole principle
(or
Dirichlet’s prin-
ciple
).
Examples.
(1) Let
m
1
,
m
2
, . . . ,
m
n
+
1
be distinct integers. Then
m
i
≡
m
j
(
mod
n
)
for some
i
,
j
∈ {
1
,
2
, . . . ,
n
+
1
}
,
i
=
j
.
Indeed, let
S
t
= {
x
∈
Z
:
x
≡
t
(
mod
n
)
}
,
t
=
1
,
2
, . . . ,
n
. There is a
k
∈ {
1
,
2
, . . . ,
n
}
such that
S
k
contains at least two of the given integers, say
m
i
and
m
j
. Then
m
i
≡
m
j
(
mod
n
)
.
92
Do'stlaringiz bilan baham: |
