|
1.2. Prime Numbers
9
Problem 1.1.18.
Find all positive integers
(
x
,
n
)
such that
x
n
+
2
n
+
1 is a divisor
of
x
n
+
1
+
2
n
+
1
+
1.
(1998 Romanian International Mathematical Olympiad Team Selection Test)
Problem 1.1.19.
Find the smallest positive integer
K
such that every
K
-element
subset of
{
1
,
2
, . . . ,
50
}
contains two distinct elements
a
,
b
such that
a
+
b
divides
ab
.
(1996 Chinese Mathematical Olympiad)
1.2
Prime Numbers
The integer
p
>
1 is called a
prime
if its only divisors are 1 and
p
itself. Any
integer
n
>
1 has at least one prime divisor. If
n
is a prime, then that prime
divisor is
n
itself. If
n
is not a prime, then let
a
be its least divisor greater than
1. If
a
were not a prime, then
a
=
a
1
a
2
with 1
<
a
1
≤
a
2
<
a
and
a
1
|
n
,
contradicting the minimality of
a
.
An integer
n
>
1 that is not a prime is called
composite
. If
n
is a composite
integer, then it has a prime divisor
p
not exceeding
√
n
. Indeed, writing again
n
=
ab
, with 1
<
a
≤
b
, we see that
n
≥
a
2
; hence
a
≤
√
n
.
The following result has been known for more than 2000 years:
Theorem 1.2.1.
(Euclid
1
)
There are infinitely many primes.
Proof.
Assume by way of contradiction that there are only a finite number of
primes:
p
1
<
p
1
<
· · ·
<
p
m
. Consider the number
P
=
p
1
p
2
· · ·
p
n
+
1.
If
P
is a prime, then
P
>
p
m
, contradicting the maximality of
p
m
. Hence
P
is composite and, consequently, it has a prime divisor
p
>
1 that is one of the
primes
p
1
,
p
2
, . . . ,
p
m
, say
p
k
. It follows that
p
k
|
p
1
· · ·
p
k
· · ·
p
m
+
1. This,
together with
p
k
|
p
1
· · ·
p
k
· · ·
p
m
, implies
p
k
|
1, a contradiction.
Remark.
The largest known prime at the present time is 2
32582657
−
1. It was
discovered in 2006 and it has 9808358 digits.
The most fundamental result in arithmetic pertains to the factorization of in-
tegers:
Theorem 1.2.2.
(The prime factorization theorem)
Any integer n
>
1
has a
unique representation as a product of primes.
Proof.
The existence of such a representation can be obtained as follows: Let
p
1
be a prime divisor (factor) of
n
. If
p
1
=
n
, then
n
=
p
1
is the prime factorization
of
n
. If
p
1
<
n
, then
n
=
p
1
r
1
, where
r
1
>
1. If
r
1
is a prime, then
n
=
1
Euclid of Alexandria (ca. 325–365 B.C.E.) is one of the most prominent mathematician of antiq-
uity, best known for his treatise on mathematics
The Elements
. The long-lasting nature of
The Elements
must make Euclid the leading mathematics teacher of all time.
10
I Fundamentals, 1. Divisibility
p
1
p
2
, where
p
2
=
r
1
, is the desired factorization of
n
. If
r
1
is composite, then
r
1
=
p
2
r
2
, where
p
2
is a prime,
r
2
>
1 and so
n
=
p
1
p
2
r
2
. If
r
2
is a prime,
then
n
=
p
1
p
2
p
3
, where
r
2
=
p
3
and we are done. If
r
2
is composite, then we
continue this algorithm, obtaining a sequence of integers
r
1
>
r
2
>
· · · ≥
1.
After a finite number of steps (see also FMID Variant 1 in Section 5.3), we reach
r
k
=
1, that is,
n
=
p
1
p
2
· · ·
p
k
.
For the uniqueness, let us assume that there is at least one positive integer
n
with two distinct representations, i.e.,
n
=
p
1
p
2
· · ·
p
k
=
q
1
q
2
· · ·
q
h
,
where
p
1
,
p
2
, . . . ,
p
k
,
q
1
,
q
2
, . . . ,
q
h
are primes. It is clear that
k
≥
2 and
h
≥
2. Let
n
be the minimal such integer. We claim that
p
i
=
q
j
for every
i
=
1
,
2
, . . . ,
k
,
j
=
1
,
2
, . . . ,
h
. If, for example,
p
k
=
q
h
=
p
, then
n
=
n
/
p
=
p
1
· · ·
p
k
−
1
=
q
1
· · ·
q
h
−
1
and 1
<
n
<
n
, contradicting the minimality of
n
.
Assume without loss of generality that
p
1
is the least prime factor of
n
in the
above representations. By applying the division algorithm, it follows that
q
1
=
p
1
c
1
+
r
1
,
q
2
=
p
1
c
2
+
r
2
,
. . .
q
h
=
p
1
c
h
+
r
h
,
where 1
≤
r
i
<
p
1
,
i
=
1
, . . . ,
h
.
We have
n
=
q
1
q
2
· · ·
q
h
=
(
p
1
c
1
+
r
1
)(
p
1
c
2
+
r
2
)
· · ·
(
p
1
c
h
+
r
h
).
Expanding the last product, we obtain
n
=
Ap
1
+
r
1
r
2
· · ·
r
h
. Setting
n
=
r
1
r
2
· · ·
r
h
we have
n
=
p
1
p
2
· · ·
p
k
=
Ap
1
+
n
. It follows that
p
1
|
n
and
n
=
p
1
s
1
s
2
· · ·
s
i
, where
s
1
,
s
2
, . . . ,
s
i
are primes.
On the other hand, using the factorization of
r
1
,
r
2
, . . . ,
r
h
into primes, all
their factors are less than
r
i
<
p
1
. From
n
=
r
1
r
2
· · ·
r
h
, it follows that
n
has
a factorization into primes of the form
n
=
t
1
t
2
· · ·
t
j
, where
t
s
<
p
1
,
s
=
1
,
2
, . . . ,
j
. This factorization is different from
n
=
p
1
s
1
s
2
· · ·
s
i
. But
n
<
n
,
contradicting the minimality of
n
.
From the above theorem it follows that any integer
n
>
1 can be written
uniquely in the form
n
=
p
α
1
1
· · ·
p
α
k
k
,
where
p
1
, . . . ,
p
k
are distinct primes and
α
1
, . . . , α
k
are positive integers and
p
1
<
p
2
<
· · ·
<
p
k
. This representation is called the
canonical factorization
of
n
.
1.2. Prime Numbers
11
An immediate application of the prime factorization theorem is an alternative
way of proving that there are infinitely many primes.
As in the previous proof, assume that there are only finitely many primes:
p
1
<
p
2
<
· · ·
<
p
m
. Let
x
=
m
i
=
1
1
+
1
p
i
+ · · · +
1
p
k
i
+ · · ·
=
m
i
=
1
1
1
−
1
p
i
.
On the other hand, by expanding and by using the canonical factorization of
positive integers, we obtain
x
=
1
+
1
2
+
1
3
+ · · ·
yielding
m
i
=
1
p
i
p
i
−
1
= ∞
, a contradiction. We have used the well-known fact
that the harmonic series
1
+
1
2
+
1
3
+ · · ·
diverges and the expansion formula
1
1
−
x
=
1
+
x
+
x
2
+ · · ·
(
for
|
x
|
<
1
),
which can also be interpreted as the summation formula for the infinite geometric
progression 1
,
x
,
x
2
, . . .
.
From the formula
∞
i
=
1
p
i
p
i
−
1
= ∞
,
using the inequality 1
+
t
≤
e
t
,
t
∈
R
, we can easily derive
∞
i
=
1
1
p
i
= ∞
.
Even though there are no definitive ways to find all primes, the density of
primes (that is, the average appearances of primes among integers) has been
known for about 100 years. This was a remarkable result in the mathematical
field of
analytic number theory
showing that
lim
n
→∞
π(
n
)
n
/
log
n
=
1
,
12
Do'stlaringiz bilan baham: |
