Теория чисел. Ч. 1 (110,00 руб.)

Стр.1

Стр.3

Стр.6

Стр.7

Стр.8

Стр.9

Стр.10

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Р.С. Адамова ТЕОРИЯ ЧИСЕЛ Часть 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.  n1 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 = 112 – 1 42 + 1 32. , ka ), так как все числа a1, a2,  , ak делятся на НОД 2 . При k = 3 имеем : 10

Стр.10