Математика. Часть 1. Алгебра и аналитическая геометрия. Красильщик И.С - 94 стр.

UptoLike

ВУЗ: 

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

Составители: 

Рубрика: 

§19. Кольцо целых чисел 93
Алгоритм Евклида. Ещё один способ находить НОД двух чисел основан
на следующем результате (который вытекает из равенства (2)).
Теорема 4 (алгоритм Евклида). Пусть 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
,
q
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
.
Пример 30 . Для чисел из примера 29 имее м
(
75 = 72 · 1 + 3,
72 = 3 · 24.
Ещё один пример: пусть m
0
= 165, m
1
= 35. Тогда
165 = 35 · 4 + 25,
35 = 25 · 1 + 10,
25 = 10 · 2 + 5,
10 = 5 · 2.
Позиционные системы счисления. Зафиксируем натуральное число n 6=
6= 1 и рассмотрим произвольное целое число m. Тогда, в с илу равенства (2), m
можно представить в виде m = q
1
n + r
0
. Если q
1
> n, то q
1
= q
2
n + r
1
и,
следовательно, m = q
2
n
2
+ r
1
n + r
0
. Продолжая э т о т процесс, мы придём к
представлению
m = q
k
n
k
+ q
k−1
n
k−1
+ . . . + q
1
n + q
0
, (4)
где все числа q
i
удовлетворяют неравенствам 0 6 q
i
< n. Предс тавление (4)
называется записью числа m в n-ичной системе счисления, а числа q
i
n-
ичными цифрами. В этом случае пишут
m = (q
k
q
k−1
. . . q
1
q
0
)
n
.
Например, в двоичной системе имеются всего две цифры — 0 и 1 — и всякое
число з аписывается в этой с истеме в виде
m = q
k
· 2
k
+ q
k−1
· 2
k−1
+ . . . + q
1
· 2 + q
0
, q
0
, q
1
, . . . , q
k
= 0, 1,
или m = (q
k
q
k−1
. . . q
1
q
0
)
2
.
§19. Кольцо целых чисел                                                                       93

Алгоритм Евклида. Ещё один способ находить НОД двух чисел основан
на следующем результате (который вытекает из равенства (2)).
   Теорема 4 (алгоритм Евклида). Пусть m0 и m1 — натуральные чис-
ла, m0 > m1 и m1 не является делителем числа m0 . Тогда существуют такие
целые числа q0 , q1, . . . , qk−1, qk и m2 , m3 , . . . , mk , что m0 > m1 > · · · > mk ,
qk > 1 и                      
                              
                              
                                  m0 = m1 q0 + m2 ,
                              
                               m1 = m2 q1 + m3 ,
                              
                              
                                   .. . .. . .. . .
                              
                              
                              
                              
                                  mk−2 = mk−1qk−1 + mk ,
                              
                               m
                                     k−1 = mk qk .
При этом mk является наибольшим общим делителем чисел m0 и m1 .
   Пример 30. Для чисел из примера 29 имеем
                                   (
                                       75 = 72 · 1 + 3,
                                       72 = 3 · 24.
Ещё один пример: пусть m0 = 165, m1 = 35. Тогда
                         
                         
                            165 = 35 · 4 + 25,
                         
                          35 = 25 · 1 + 10,
                         
                            25 = 10 · 2 + 5,
                         
                         
                             10 = 5 · 2.

Позиционные системы счисления. Зафиксируем натуральное число n 6=
6= 1 и рассмотрим произвольное целое число m. Тогда, в силу равенства (2), m
 можно представить в виде m = q1 n + r0. Если q1 > n, то q1 = q2n + r1 и,
следовательно, m = q2n2 + r1n + r0. Продолжая этот процесс, мы придём к
 представлению
                     m = qk nk + qk−1nk−1 + . . . + q1 n + q0,            (4)
 где все числа qi удовлетворяют неравенствам 0 6 qi < n. Представление (4)
 называется записью числа m в n-ичной системе счисления, а числа qi n-
 ичными цифрами. В этом случае пишут
                                  m = (qk qk−1 . . . q1 q0)n .
Например, в двоичной системе имеются всего две цифры — 0 и 1 — и всякое
число записывается в этой системе в виде
       m = qk · 2k + qk−1 · 2k−1 + . . . + q1 · 2 + q0 ,         q0, q1, . . . , qk = 0, 1,
или m = (qk qk−1 . . . q1 q0)2.

Страницы