|
1.3. The Greatest Common Divisor and Least Common Multiple
19
Proposition 1.3.2.
(Euclid’s lemma).
Let p be a prime and a
,
b
∈
Z
. If p
|
ab,
then p
|
a or p
|
b.
Proof.
Suppose that
p
a
. Since gcd
(
p
,
a
)
|
p
, we have gcd
(
p
,
a
)
=
1 or
gcd
(
p
,
a
)
=
p
; but the latter implies
p
|
a
, contradicting our assumption, thus
gcd
(
p
,
a
)
=
1. Let
r
,
s
∈
Z
be such that
r p
+
sa
=
1. Then
r pb
+
sab
=
b
and
so
p
|
b
.
More generally, if a prime
p
divides a product of integers
a
1
· · ·
a
n
then
p
|
a
j
for some
j
. This can be proved by induction on the number
n
.
We can define the greatest common divisor of several positive integers
m
1
,
m
2
,
. . .
,
m
s
by considering
d
1
=
gcd
(
m
1
,
m
2
),
d
2
=
gcd
(
d
1
,
m
3
), . . . ,
d
s
−
1
=
gcd
(
d
s
−
2
,
m
s
).
The integer
d
=
d
s
−
1
is called the greatest common divisor of
m
1
, . . . ,
m
s
and denoted by gcd
(
m
1
, . . . ,
m
s
)
. The following properties can be easily verified:
(i) gcd
(
gcd
(
m
,
n
),
p
)
=
gcd
(
m
,
gcd
(
n
,
p
))
, proving that gcd
(
m
,
n
,
p
)
is well
defined.
(ii) If
d
|
m
i
,
i
=
1
, . . . ,
s
, then
d
|
gcd
(
m
1
, . . . ,
m
s
)
.
(iii) If
m
i
=
p
α
1
i
1
· · ·
p
α
ki
k
,
i
=
1
, . . . ,
s
, then
gcd
(
m
1
, . . . ,
m
s
)
=
p
min
(α
11
,...,α
1
k
)
1
· · ·
p
min
(α
1
s
,...,α
ks
)
k
.
For a positive integer
k
we denote by
M
k
the set of all multiples of
k
. Unlike
the set
D
k
defined earlier in this section,
M
k
is an infinite set.
For positive integers
s
and
t
, the minimal element of the set
M
s
∩
M
t
is called
the
least common multiple
of
s
and
t
and is denoted by lcm
(
s
,
t
)
.
The following properties are easily obtained from the definition above:
(1
) If
m
=
lcm
(
s
,
t
)
,
m
=
ss
=
tt
, then gcd
(
s
,
t
)
=
1.
(2
) If
m
is a common multiple of
s
and
t
and
m
=
ss
=
tt
, gcd
(
s
,
t
)
=
1,
then
m
=
m
.
(3
) If
m
is a common multiple of
s
and
t
, then
m
|
m
.
(4
) If
s
=
p
α
1
1
· · ·
p
α
k
k
and
t
=
p
β
1
1
· · ·
p
β
k
k
,
α
i
,
b
i
≥
0,
i
=
1
, . . . ,
k
, then
lcm
(
s
,
t
)
=
p
max
(α
1
,β
1
)
1
· · ·
p
max
(α
k
,β
k
)
k
.
The following property establishes an important connection between greatest
common divisor and least common multiple:
20
I Fundamentals, 1. Divisibility
Proposition 1.3.3.
For any positive integers m
,
n the following relation holds:
mn
=
gcd
(
m
,
n
)
·
lcm
(
m
,
n
).
Proof.
Let
m
=
p
α
1
1
· · ·
p
α
k
k
,
n
=
p
β
1
1
· · ·
p
β
k
k
,
α
i
, β
i
≥
0,
i
=
1
, . . . ,
k
. From
properties (4) and (4
) we have
gcd
(
m
,
n
)
·
lcm
(
m
,
n
)
=
p
min
(α
1
,β
1
)
+
max
(α
1
,β
1
)
1
· · ·
p
min
(α
k
,β
k
)
+
max
(α
k
,β
k
)
k
e
=
p
α
1
+
β
1
1
· · ·
p
α
k
+
β
k
k
=
mn
.
It is also not difficult to see that if
m
|
s
and
n
|
s
, then lcm
(
m
,
n
)
|
s
.
Another useful property is the following.
Proposition 1.3.4.
Let n, a, b be positive integers. Then
gcd
(
n
a
−
1
,
n
b
−
1
)
=
n
gcd
(
a
,
b
)
−
1
.
Proof.
Without loss of generality, we assume that
a
≥
b
. Then
gcd
(
n
a
−
1
,
n
b
−
1
)
=
gcd
(
n
a
−
1
−
n
a
−
b
(
n
b
−
1
),
n
b
−
1
)
=
gcd
(
n
a
−
b
−
1
,
n
b
−
1
).
Recall the process of finding gcd
(
a
,
b
)
=
gcd
(
a
−
b
,
b
)
given by the Euclidean
algorithm. We see that the process of computing gcd
(
n
a
−
1
,
n
b
−
1
)
is the same as
the process of computing gcd
(
a
,
b
)
as the exponents, from which the conclusion
follows.
Problem 1.3.1.
Prove that for odd n and odd integers a
1
, a
2
, . . . ,
a
n
, the greatest
common divisor of numbers a
1
,
a
2
, . . . ,
a
n
is equal to the greatest common divisor
of
a
1
+
a
2
2
,
a
2
+
a
3
2
, . . . ,
a
n
+
a
1
2
.
Solution.
Let
a
=
gcd
(
a
1
,
a
2
, . . . ,
a
n
)
and
b
=
gcd
a
1
+
a
2
2
,
a
2
+
a
3
2
, . . . ,
a
n
+
a
1
2
.
Then
a
k
=
b
k
a
, for some integers
b
k
,
k
=
1
,
2
, . . . ,
n
. It follows that
a
k
+
a
k
+
1
2
=
b
k
+
b
k
+
1
2
a
,
(
1
)
where
a
n
+
1
=
a
1
and
b
n
+
1
=
b
1
. Since
a
k
are odd numbers,
b
k
are also odd, so
b
k
+
b
k
+
1
2
are integers.
From relation (1) it follows that
a
divides
a
k
+
a
k
+
1
2
for all
k
∈ {
1
,
2
, . . . ,
n
}
so
a
divides
b
.
On the other hand,
a
k
+
a
k
+
1
2
=
β
k
b
, for some integers
β
k
. Then
2
b
|
a
k
+
a
k
+
1
(
2
)
1.3. The Greatest Common Divisor and Least Common Multiple
21
for all
k
∈ {
1
,
2
, . . . ,
n
}
. Summing up from
k
=
1 to
k
=
n
yields
2
b
|
2
(
a
1
+
a
2
+ · · · +
a
n
),
hence
b
|
a
1
+
a
2
+ · · · +
a
n
.
(
3
)
Summing up for
k
=
1
,
3
, . . . ,
n
−
2 implies
2
b
|
a
1
+
a
2
+ · · · +
a
n
−
1
and furthermore
b
|
a
1
+
a
2
+ · · · +
a
n
−
1
.
(
4
)
From (3) and (4) we get that
b
divides
a
n
; then using relation (2) we obtain
b
|
a
k
for all
k
. Hence
b
|
a
and the proof is complete.
Problem 1.3.2.
Prove that for all nonnegative integers a
,
b
,
c
,
d such that a and
b are relatively prime, the system
ax
−
yz
−
c
=
0
,
bx
−
yt
+
d
=
0
,
has infinitely many solutions in nonnegative integers.
Solution.
We start with a useful lemma that is a corollary to Proposition 1.3.1.
Lemma.
If a and b are relatively prime positive integers, then there are positive
integers u and
v
such that
au
−
b
v
=
1
.
Proof.
Here we give a different argument as in the proof of Proposition 1.3.1.
Consider the numbers
1
·
a
,
2
·
a
, . . . , (
b
−
1
)
·
a
.
(
1
)
When divided by
b
, the remainders of these numbers are distinct. Indeed,
otherwise we would have
k
1
=
k
2
∈ {
1
,
2
, . . . ,
b
−
1
}
such that
k
1
a
=
p
1
b
+
r
,
k
2
a
=
p
2
b
+
r
,
for some integers
p
1
,
p
2
. Hence
(
k
1
−
k
2
)
a
=
(
p
1
−
p
2
)
b
.
Since
a
and
b
are relatively prime, it follows that
b
divides
k
1
−
k
2
, which is
false because 1
≤ |
k
1
−
k
2
|
<
b
.
22
Do'stlaringiz bilan baham: |
