Группы, кольца и поля. - 6 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Рубрика: 

6 ГРУППЫ, КОЛЬЦА И ПОЛЯ
1) Наибольшим общим д елителем (НОД) чисел m и n называется такой положительный об-
щий делитель
4
этих чисел, на который делится любой другой их общий делитель.
2) Числа m и n называются взаимно простым и, если их НОД равен единице.
3) Наименьшим общим кратным (НОК) чисел m и n называется такое их положительное
общее кратное, которое делит любое другое общее кратное этих чисел.
Предложение 3. У любых двух ненулевых целых чисел существуют НОД и НОК.
Нахождение НОД и НОК. Чтобы найти НОД и НОК чисел m и n, нужно:
1) Найти разложение (3) для чисел m и n.
2) Записать числа m и n в виде
m = p
i
1
1
p
i
2
2
. . . p
i
k
k
,
n = p
j
1
1
p
j
2
2
. . . p
j
k
k
.
Если какое-нибудь из чисел p
α
не является делителем m или n, то соответствующий пока-
затель степени равен нулю.
3) Взять числа l
α
= min(i
α
, j
α
). Тогда
НОД = p
l
1
1
p
l
2
2
. . . p
l
k
k
.
4) Взять числа s
α
= max(i
α
, j
α
). Тогда
НОК = p
s
1
1
p
s
2
2
. . . p
s
k
k
.
Пример 28. Пусть m = 72, n = 75. Тогда
72 = 2
3
· 3
2
, 75 = 3 · 5
2
.
Значит,
72 = 2
3
· 3
2
· 5
0
,
75 = 2
0
· 3
1
· 5
2
.
Поэтому l
1
= min(3, 0) = 0, l
2
= min(2, 1) = 1, l
3
= min(0, 2) = 0, а s
1
= max(3, 0) = 3, s
2
=
max(2, 1) = 2, l
3
= max(0, 2) = 2. Значит,
НОД = 2
0
· 3
1
· 5
0
= 3, НОК = 2
3
· 3
2
· 5
2
= 1800.
Алгоритм Евклида. Ещё один способ находить НОД двух чисел основан на следующем ре-
зультате (который вытекает из равенства (2)).
Теорема 3 (алгоритм Евклида). Пусть m
0
и m
1
— натуральные числа, m
0
> m
1
и m
1
не
является делителем числа m
0
. Тогда существуют такие целые числа q
0
, q
1
, . . . , q
k−1
, q
k
и m
2
,
m
3
, . . . , m
k
, что m
0
> m
1
> ··· > m
k
, a
k
> 1 и
m
0
= m
1
q
0
+ m
2
,
m
1
= m
2
q
1
+ m
3
,
. . . .
m
k−2
= m
k−1
q
k−1
+ m
k
,
m
k−1
= m
k
q
k
.
При этом m
k
является наибольшим общим делителем чисел m
0
и m
1
.
4
То есть число, которое является делителем и m, и n.
6                                         ГРУППЫ, КОЛЬЦА И ПОЛЯ

     1) Наибольшим общим делителем (НОД) чисел m и n называется такой положительный об-
        щий делитель4 этих чисел, на который делится любой другой их общий делитель.
     2) Числа m и n называются взаимно простыми, если их НОД равен единице.
     3) Наименьшим общим кратным (НОК) чисел m и n называется такое их положительное
        общее кратное, которое делит любое другое общее кратное этих чисел.
    Предложение 3. У любых двух ненулевых целых чисел существуют НОД и НОК.

Нахождение НОД и НОК. Чтобы найти НОД и НОК чисел m и n, нужно:
     1) Найти разложение (3) для чисел m и n.
     2) Записать числа m и n в виде
                                               m = pi11 pi22 . . . pikk ,
                                               n = pj11 pj22 . . . pjkk .
        Если какое-нибудь из чисел pα не является делителем m или n, то соответствующий пока-
        затель степени равен нулю.
     3) Взять числа lα = min(iα , jα ). Тогда
                                             НОД = pl11 pl22 . . . plkk .
     4) Взять числа sα = max(iα , jα ). Тогда
                                            НОК = ps11 ps22 . . . pskk .
    Пример 28. Пусть m = 72, n = 75. Тогда
                                         72 = 23 · 32 ,         75 = 3 · 52 .
Значит,
                                                72 = 23 · 32 · 50 ,
                                                75 = 20 · 31 · 52 .
Поэтому l1 = min(3, 0) = 0, l2 = min(2, 1) = 1, l3 = min(0, 2) = 0, а s1 = max(3, 0) = 3, s2 =
max(2, 1) = 2, l3 = max(0, 2) = 2. Значит,
                           НОД = 20 · 31 · 50 = 3,           НОК = 23 · 32 · 52 = 1800.


Алгоритм Евклида. Ещё один способ находить НОД двух чисел основан на следующем ре-
зультате (который вытекает из равенства (2)).
  Теорема 3 (алгоритм Евклида). Пусть m0 и m1 — натуральные числа, m0 > m1 и m1 не
является делителем числа m0 . Тогда существуют такие целые числа q0 , q1 , . . . , qk−1 , qk и m2 ,
m3 , . . . , mk , что m0 > m1 > · · · > mk , ak > 1 и
                                         
                                         
                                         
                                             m0 = m1 q 0 + m2 ,
                                          m1 = m2 q 1 + m3 ,
                                         
                                         
                                         
                                              ....
                                         
                                              mk−2 = mk−1 qk−1 + mk ,
                                         
                                         
                                         
                                         
                                         
                                          m
                                                k−1 = mk qk .

При этом mk является наибольшим общим делителем чисел m0 и m1 .

    4То есть число, которое является делителем и m, и n.

Страницы