Составители:
разложения чисел на множители, так и методов восстановления двух
простых чисел p и q из их произведения n:
n = p ⋅ q.
Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,
b) или просто (a, b), − это наибольшее число, делящее одновременно
числа a и b. В эквивалентной форме
(a, b) – это натуральное число,
которое делит a и b, и делится на любое число, делящее и a, и b . Если
НОД ( a, b) = 1, то целые a и b - взаимно простые.
Наибольший общий делитель может быть вычислен с помощью
алгоритма Евклида.
Если принять следующие обозначения: q
i
- частное; r
i
- остаток, то
данный алгоритм можно представить в виде цепочки равенств:
a = b ⋅ q
1
+ r
1
, 0 < r
1
< b,
b = r
1
⋅ q
2
+ r
2
, 0 < r
2
< r
1
,
r
1
= r
2
⋅ q
3
+ r
3
, 0 < r
3
< r
2
,
. .
. .
. .
r
k-2
= r
k-1
⋅ q
k
+ r
k
, 0 <r
k
< r
k-1
,
r
k-1
= r
k
⋅ q
k+1
.
Как видно из алгоритма остатки r
i
от делений образуют строго
убывающую последовательность натуральных чисел. Откуда следует,
что r
k
есть общий делитель чисел a и b и, более того, любой общий
делитель чисел a и b делит и r
k
.
Пример Ι [14,17]. Найти НОД (175, 77) согласно алгоритма Евклида
(a, b) = (b, r
1
) = (r
1
, r
2
) = ⋅⋅⋅ = (r
n-1
, r
n
) = r
n
.
175 = 77 ⋅ 2 + 21, 77 = 21 ⋅ 3 + 14, 21 = 14 ⋅ 1 + 7, 14 = 7 ⋅ 2.
Таким образом, последний положительный остаток – r
3
= 7, т.е. НОД
(175, 77) = 7.
П.2. Алгоритмы вычисления обратных величин
В арифметике действительных чисел нетрудно вычислить
мультипликативную обратную величину a
-1
для a ≠ 0:
a
-1
= 1/a или a ⋅ a
-1
=1.
155
Страницы
- « первая
- ‹ предыдущая
- …
- 151
- 152
- 153
- 154
- 155
- …
- следующая ›
- последняя »
