Составители:
Рубрика:
8
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 – простое число, поэтому окончательно
имеем в канонической форме: 10500 = 2
2
3
1
5
3
7
1
.
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
.
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
