Cryptography Reference
In-Depth Information
Figure 3.6
PROPOSITION 14
Suppose
a
1
,
a
2
, . . . ,
a
n
are positive integers, and
p
is a prime which
divides
a
1
a
2
...
a
n
. Then there is an integer
i
such that 1
≤
i
≤
n
and
p
|
a
i
.
Proof.
If
n
= 1, the result is trivially true. Now suppose the theorem is true for
n
=
k
, and
consider a product of
k
+ 1 integers
a
1
a
2
...
a
k
1
divisible by
p
. Since
p
|
a
1
a
2
...
a
k
1
= (
a
1
a
2
...
a
k
)
a
k
1
, proposition 13 says either
p
|
a
1
a
2
...
a
k
, or
p
|
a
k
1
. If
p
|
a
k
1
, we are finished. If,
on the other hand
p
|
a
1
a
2
...
a
k
, our supposition says
an integer
i
between 1 and
n
(inclu-
sive) such that
p
|
a
i
. In this case, induction establishes the desired result.
PROPOSITION 15
(The Fundamental Theorem of Arithmetic.) Every positive integer
n
greater than 1 can be written in the form
n
=
p
1
p
2
...
p
r
where each
p
r
is prime,
i
= 1,
2, . . . ,
n
. Furthermore, this representation is unique.
Proof.
Assume some positive integer greater than 1 cannot be written as a product of
primes, and let
n
n
be the smallest such integer. If
is prime, it is trivially a product of primes.
n
ab
a
n
b
n
n
So
=
is composite, where 1 <
<
, 1 <
<
. Since
is the smallest number greater
a
b
than 1 which cannot be written as a product of primes,
and
must both be products of
n
ab
n
primes. But since
is also a product of primes, contrary to our assumption. Given
that this prime factorization of
=
,
n
n
exists, we must now show it is unique. Suppose
has two
different factorizations
n
=
p
1
p
2
...
p
m
=
q
1
q
2
...
q
k
Search WWH ::
Custom Search