МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
Р.С. Адамова
ТЕОРИЯ ЧИСЕЛ
Часть 1
Учебно-методическое пособие
Воронеж
Издательский дом ВГУ
2017
Стр.1
§1 . Делимость в множестве натуральных чисел.
§ 1. Делимость в множестве натуральных чисел
Пусть a, b N.
Определение 1. Говорят, что a д е л и т с я на b, если существует q N
такое, что
a = b q
При этом пишут a b . Число q называют частным от деления a на b,
число a называют к р а т н ы м числа b (обозначают a b ), а
b –
д е л и т е л е м числа a. Если a не делится на b, пишут a b .
Теорема 1. Если a > b и a b , то существуют, и притом единственным
образом, числа q, r N такие, что
a = b q + r,
r < b.
(1)
При этом q называют н е п о л н ы м ч а с т н ы м , а r – о с т а т к о м от
деления a на b.
Такое представление числа a называется д е л е н и е м с о с т а т к о м .
Определение 2. Н а и б о л ь ш и м о б щ и м д е л и т е л е м системы
натуральных чисел a1, a2, , ak называется наибольший среди их общих
делителей.
Он обозначается НОД (a1, a2, . . . , ak) или, короче, (a1, a2, . . . , ak).
Определение 3. Н а и м е н ь ш и м о б щ и м к р а т н ы м системы
натуральных чисел a1, a2, . . . , ak называется наименьшее среди их общих
кратных.
Оно обозначается НОК (a1, a2, . . . , ak) или [a1, a2, . . . , ak].
Теорема 2. Наибольший общий делитель и наименьшее общее кратное
обладают следующими свойствами:
1. Любое общее кратное чисел a1, a2, . . . , ak делится на их наименьшее
общее кратное.
2. Наибольший общий делитель чисел a1, a2, . . . , ak делится на любой
общий делитель этих чисел.
3. Если [a1, a2, . . . , ak] = m , то [a1, a2, . . . , ak, ak+1] = [m, ak+1].
4. Если (a1, a2, . . . , ak) = d, то (a1, a2, . . . , ak, ak+1) = (d, ak+1).
5. При одновременном делении чисел a1, a2, . . . , ak на любой их общий
делитель c то же самое происходит и с их НОД и НОК, то есть
3
Стр.3
§ 2. Алгоритм Евклида
§ 2. Алгоритм Евклида
Для нахождения НОД и НОК любого конечного семейства чисел
достаточно, в силу теорем 2 и 3, уметь находить НОД двух чисел. Пусть
даны два натуральных числа a и b, a b. Если a b, то НОД (a, b) = b.
Рассмотрим другую ситуацию: a > b,
последовательного деления.
a = b q1 + r1
b = r1 q2 + r2
r1= r2 q3 + r3
……………………….
a b . Выполним процесс
(5)
rn-2 = rn-1 qn + rn
rn-1 = rn qn+1
Такой процесс действительно конечен, так как остатки r1, r2, r3, ... –
a b )
натуральные числа, убывающие с возрастанием номера. Он называется
а л г о р и т м о м Е в к л и д а п о с л е д о в а т е л ь н о г о д е л е н и я a
н а b .
Теорема 4. Наибольшим общим делителем чисел a и b (a > b,
является последний остаток в процессе алгоритма Евклида
последовательного деления a на b.
Доказательство. Пусть d = (a, b). Тогда a, b d. Из алгоритма (5)
1
последовательно получаем r d r d,
,b r a r .
,
r
Итак, rn – общий делитель чисел a и b и поэтому d rn
делимостью r dn это дает, что rn = d.
n1 r r
n n 2 n
,
rn ,
q1
q2 q3
1
1
q n 1
1
qn
Это выражение называется цепной дробью, построенной по числам
(6)
,
рассматривая этот алгоритм с конца, получим последовательно
n
2
. Вместе с
Из алгоритма (5) выпишем все последовательные неполные частные:
q1, q2, . . . , qn и по ним запишем выражение
1
, r dn
. В тоже время,
6
Стр.6
§ 2. Алгоритм Евклида
q1, q2, . . . , qn. Ее значение обозначается | q1, q2, . . . , qn |, число n называется
д л и н о й этой цепной дроби.
Теорема 5. Если a > b и a b , то наибольший общий делитель чисел
a и b может быть выражен через них с помощью определителя:
НОД(
a )b, = (-1)n+1
a b
P Q
,
где P и Q - числитель и знаменатель несократимой дроби
(7)
P
Q , равной
значению цепной дроби (6), n - длина этой цепной дроби.
Доказательство. Если n = 1, то в алгоритме Евклида только одно
неполное частное, и легко видеть, что утверждение теоремы справедливо.
Покажем, как из справедливости утверждения для значения n = k−1
вытекает справедливость для следующего. Запишем алгоритм Евклида при
значении n = k :
a = b q1 + r1
b = r1 q2 + r2
r1 = r2 q2 + r3
(8)
. . . . . . . . . . . .
rk−2 = rk−1 qk + rk
rk−1 = rk qk+1.
Будем рассматривать алгоритм, начиная со второй строки. По
существу, мы видим алгоритм нахождения наибольшего общего делителя
для чисел b и r1 . Согласно предположению индукции будем иметь
НОД(b r1)
где P1 и Q1
q q2 , 3
Q
P
1
1
, , qk
, = (-1)
k
P Q
b r
1
1
1
- числитель и знаменатель несократимой дроби
. Как видно из алгоритма (8), НОД (a, b) = НОД (b, r1).
Согласно (9) имеем
НОД(a, b) =
k
(-1) QP
b r =
1
1
1
(-1)
k
P Pq Q
b bq r
1
1
1 1
1
=
1
(-1)
k+1
Pq Q P
b
1 1 + 1
a
1
несократимой дроби, равной | q1, q2, . . . , qn |. Дробь q P Q
P
1 1
1
7
1
.
Осталось показать, что q1 P1 + Q1 и P1 - числитель и знаменатель
несократима,
,
(9)
Стр.7
§ 2. Алгоритм Евклида
так как в противном случае оказалась бы сократимой дробь
того, она представима в виде
P
q Q
1
1
1
1
1
1
1
Q
q P
q
q1
1
2
то есть равна | q1, q2, ..., qk | .
Пример 2. Положим a = 272, b = 50. Выполним алгоритм Евклида
272 = 50
50 = 22
22 = 6
6 = 4
4 = 2
5 + 22
2 + 6
3 + 4
1 + 2
2
+
НОД (272, 50) = 2,
5, 2,3,1 5
2
1
1
3 1
1
P = 49, Q = 9, n = 4.
2 ( 1) 272 50
4 1
49 9
272 9 50 49
49
9
1
q k 1
1
qk
,
P
Q
1
1
и, кроме
8
Стр.8
§ 2. Алгоритм Евклида
Схема вычисления цепной дроби.
Пусть нужно вычислить
q q ,2 ,qn q
1,
q1
2
цепную дробь, в обратном порядке:
qn qn–1 … q2 q1
1 qn
Заполним нижнюю строку по правилу:
(10)
каждое следующее число получается, если к произведению чисел,
стоящих над ним и перед ним, прибавить предпоследнее из
имеющихся чисел в нижней строке.
При таком заполнении таблицы справедлива следующая теорема.
Теорема 6. Последними числами в нижней строке таблицы (10) будут
последовательно числа Q и P – знаменатель и числитель несократимой
дроби, равной | q1,q2, ,qn | .
Доказательство. Утверждение верно, когда n = 2. Предположим, что оно
справедливо при n = k–1. Рассмотрим схему при n = k:
qk qk–1 q2 q1
1 q k ...
Q
Q1
= q2, q3,. ..,qk. Поэтому дробь
Q
P
q q2 , ... , qk q1
1,
1
q q3 ,... , qk
2 ,
1
1
Q
q Q
1q Q Q1
Q
1
.
Q1 Q P
Поскольку утверждение верно при n = k–1,то дробь Q
Q1
– несократимая и
1
qn
Составим таблицу, записав в верхней строке числа, определяющие
1
9
Стр.9
§ 2. Алгоритм Евклида
Полученная дробь несократима, так как в противном случае
делителем
наибольший общий делитель P и Q, отличный от единицы, оказался бы
общим
для Q и Q1, что невозможно.
Пример 3. Мы видели в примере (2) , что 5, 2, 3, 1 = 49
9 . Проведем
вычисление этого числа по схеме (10) :
1 3 2 5
1
1 4 9 49
9 = Q, 49 = P, P
Q 49
9
5 2 3 1 .
, , ,
Теорема 7. НОД чисел a1, a2 , ... , ak является наименьшим
натуральным числом в множестве всех линейных комбинаций этих чисел с
целыми коэффициентами.
Доказательство. НОД (a1, a2, , ak) представляется в виде их линейной
комбинации. В самом деле, при k = 2 это следует из теоремы 5 и из того, что
НОД (a1, a2) = a2, если a a1
при некоторых m1, n1, n2, n3 Z. Аналогично поступаем при любом k > 3.
Пусть теперь d = n1 a1 + n2 a2 + + nk ak, где n1, n2, , nk Z, и d –
НОД ( a1, a2, a3 ) = (a1(a2, a3)) = n1a1 + m1(a2, a3) = n1a1 + n2a2 + n3a3
наименьшее натуральное число среди комбинаций такого вида. Тогда
d
(a1, , ak), и поэтому d НОД (a1, , ak). С другой стороны , d НОД
(a1, , ak)построению. Следовательно , d = НОД (a1, , ak).
Пример 4. НОД (12, 42, 32) = 2 и
НОД (a1,
2 = 112 – 1 42 + 1 32.
, ka ), так как все числа a1, a2, , ak делятся на НОД
2 . При k = 3 имеем :
10
Стр.10