ВУЗ:
Составители:
Рубрика:
25
что
b=q
1
c, a=q
2
b, откуда а=q
1
q
2
c=qc и снова по определению
ac / .
Лемма 2. Если m=a+b, d/m и d/a, то d/a.
Доказательство: по определению m=q
1
d и a=q
2
d. Поэтому
из равенства
m=a+b получим b=q
1
d - q
2
d=(q
1
-q
2
)d=qd, откуда
следует
d/b. Отсюда следует, что если m=a
1
+a
2
+…+a
n -1
+a
n
и d
делит числа
m, а
1
,…,а
n -1
, то d/a
n
.
Общим делителем двух или нескольких чисел называется
число, являющееся делителем каждого из этих чисел.
Если а
1
,…,а
n
числа из Z и хотя бы одно из них не равно
нулю, то множество их общих делителей конечно и среди этих
делителей существует наибольшее число.
Наибольшим общий делителем (НОД) чисел а
1
,…,а
n
на-
зывается наибольший из их общих делителей. Он обозначается
(а
1
,…,а
n
).
Число
n>1 называется простым, если оно не имеет других
делителей кроме
1 и n. Например, числа 2, 3, 5, 7 являются про-
стыми, т.к. они делятся только на 1 и на самих себя.
Число n называется составным, если оно имеет делитель
отличный от 1 и
n. Например, числа 4, 6, 8 составные числа.
Если НОД
(а
1
,…,а
n
)=1, то числа а
1
,…,а
n
называют взаимно
простыми
Например: (2,5)=1; (10,21)=1
Лемма 3. Если a, b, c - целые числа, то (a, b)=1 b/ac, то b/c.
Лемма 4. Если целое число b взаимно просто с каждым из
целых чисел
а
1
,…,а
n
, то b взаимно просто с их произведением
а
1
а
2
,…, а
n
Когда
а не делится на b, то принято говорить о делении а
на
b с остатком r.
Теорема о делении с остатком. Если а и b целые числа,
то
b>0, то существуют единственные целые числа q и r такие,
что
a=b*q+r,
b
r
<
≤0
.
Число
q называют неполным частным при делении a на b,
число
r называют остатком от деления а на b.
Очевидно, что если
r=0, то b/a.
Пример.
Пусть b=12… Тогда для чисел а= 110, а= -53, а
26
=156 имеем
а=b
q+r
110=12
9+2 0<r=2<b=12
-53=12+(-5)+7 0<
r=7<b=12
156=12
13 +0 r=0
Любое натуральное составное число
n представляется в
виде
n=ab, 1<a<n, 1<b<n.
Лемма 5. Наименьший отличный от единицы делитель на-
турального числа
n>1 есть простое число.
Доказательство. Число n>1 имеет хотя бы два различных
делителя (
1 и n) и, следовательно, имеет делитель отличный от
единицы. Среди всех делителей отличных от
1 имеется наи-
меньший. Пусть это будет
q. Число q должно быть простым т.к.
в противном случае оно было бы составным и по определению
имело бы делитель q
1
такой, что 1<q
1
<q. Но q
1
/q и q/n, а тогда по
лемме1
q
1
/n. Это противоречит тому, что q наименьший дели-
тель
n, значит q - простое число.
Следствие. Каждое натуральное число n>1 имеет хотя бы
один простой делитель.
Лемма 6. Наименьший простой делитель составного числа
n не превосходит
n
.
Доказательство. Пусть p>1 наименьший делитель числа n
являющийся по лемме 5 простым числом. Так как
n составное
число, то
n=pq, где
qp
≤
. Поэтому
2
pn ≥
,откуда
np ≤
.
Лемма 7. Если p - простое число, то любое целое число а
либо взаимно простое с
р, либо делится на р т.е. р/а.
Доказательство. Наибольшим общим делителем (а, р) чи-
сел
а и р может быть только делитель простого числа р, который
в свою очередь может быть равен
1 или р. тогда в первом случае
(а, р)=1 и числа а и р взаимно простые, а во втором случае когда
(а, р)=р а делится на р т.е. р/а.
Основная теорема арифметики. Любое натуральное чис-
ло
n>1 представляется в виде произведения простых чисел, при-
чем единственным образом.
Доказательство. По лемме 5 число n>1 имеет наимень-
ший простой делитель
р
1
. тогда n=p
1
a
1
. Если а
1
>1, то аналогично
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
