Дискретная математика. Ерош И.Л - 117 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

117
ди делителей имеется наибольшее число, которое называется наиболь
шим общим делителем – НОД (a
1
, a
2
, a
3
, …, a
n
) или (a
1
, a
2
, a
3
, …, a
n
).
6.1.5. Простые числа. Разложение на простые сомножители.
Каноническая форма числа
Число, которое не имеет никаких делителей, кроме 1 и самого себя,
называется простым числом. Примеры простых чисел: 2, 3, 5, 7, 11,
13, 17, 19, 23, 29, 31, …
Любое число N может быть представлено в виде произведения сте
пеней простых чисел (каноническое представление числа). Такое пред
ставление единственно (с точностью до перестановки сомножителей).
Так, число 600 = 2
3
3
1
5
2
.
Для представления числа N в канонической форме можно исполь
зовать следующий алгоритм. Число N делим на наименьшее простое
число 2 до тех пор, пока оно делится нацело, затем на 3, на 5 и т. д.
Например, N = 10500. 10500: 2 = 5250; 5250: 2 = 2625. Это число
больше не делится на 2 нацело. Делим его на 3. 2625: 3 = 875. Это
число на 3 нацело не делится. Делим его на 5. 875: 5 = 175. Еще раз
делим на 5. 175: 5 = 35. Еще раз делим на 5. 35: 5 = 7. Число 7 –
простое число, поэтому окончательно имеем в канонической форме:
10 500 = 2
2
3
1
5
3
7
1
.
6.1.6. Определение НОК И НОД чисел
Для произвольного целого числа a и произвольного целого положи
тельного числа b существуют такие числа t и r, что a = bt + r, где 0 £ r < b.
Причем такое представление единственное.
Можно показать, что если b|a (b делит a нацело), то (a, b) = b, и если
a = bt + r, то (a, b) = (b, r).
Для нахождения наибольшего общего делителя двух чисел a и b из
вестен алгоритм Евклида: пусть a ³ b. Рассмотрим следующую после
довательность равенств:
a = bt
1
+ r
2
, 0 < r
2
< b;
b = r
2
t
2
+ r
3
, 0 < r
3
< r
2
;
r
2
= r
3
t
3
+ r
4
, 0 < r
4
< r
3
…
r
n–1
= r
n
t
n
+ r
n+1
, 0 = r
n+1
.
Поскольку a ³ b > r
2
> r
3
> … ³ 0, то алгоритм имеет конечное число
шагов. Согласно вышеприведенным свойствам, (a, b) = (b, r
2
) = (r
2
, r
3
) =
= … = r
n
. Таким образом, наибольший общий делитель чисел a и b ра
вен последнему ненулевому остатку в последовательности равенств, т. е.
r
n
. А наименьшее общее кратное a и b равно [a, b] = ab/(a, b).

Страницы