Учебник + задачник АП Ильиных

Министерство образования Российской Федерации

Уральский государственный педагогический университет

А.П. Ильиных

ТЕОРИЯ ЧИСЕЛ

Учебное пособие

Екатеринбург 2003

УДК 511 И 45

РЕЦЕНЗЕНТ: член - корреспондент РАН, доктор физико-математи- ческих наук, профессор А.А.Махнев

И 45 Ильиных А.П. Теория чисел: Учебное пособие / Урал. гос. пед. ун-т.– Екатеринбург, 2003. – 148 с.

Пособие является курсом лекций по теории чисел и предназначено для студентов дневного и заочного отделений математических факультетов педагогических вузов.

Некоторые утверждения требуют самостоятельного доказательства. На такие утверждения указывает следующий знак на поле страницы. "

В заключительной части пособия содержатся индивидуальные домашние задания по теории чисел.

c Ильиных А.П., 2003

Содержание

Лекция 1. Делимость целых чисел. Частное и остаток . . . . . . . . . . . . . . 4 Лекция 2. Наибольший общий делитель. Алгоритм Евклида . . . . . . . . 7 Лекция 3. Линейная форма НОД. НОК и его свойства . . . . . . . . . . . . 13 Лекция 4. Простые числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 Лекция 5. Каноническое разложение натурального числа . . . . . . . . . 20 Лекция 6. Теоретико-числовые функции . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Лекция 7. Теория сравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Лекция 8. Полная и приведенная системы вычетов . . . . . . . . . . . . . . . . 32 Лекция 9. Кольцо и поле классов вычетов . . . . . . . . . . . . . . . . . . . . . . . . 41 Лекция 10. Сравнения первой степени с одной неизвестной . . . . . . . 45 Лекция 11. Непрерывные дроби . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Лекция 12. Системы сравнений первой степени . . . . . . . . . . . . . . . . . . . 58 Лекция 13. Показатель числа. Свойства показателя . . . . . . . . . . . . . . .65 Лекция 14. Первообразные корни . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Лекция 15. Индексы. Свойства индексов . . . . . . . . . . . . . . . . . . . . . . . . . 73 Лекция 16. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Лекция 17. Запись рациональных чисел в виде десятичной дроби . . 82 Индивидуальные домашние задания по теории чисел. . . . . . . . . . . . . . 89 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

3

Лекция 1. Делимость целых чисел. Частное и остаток.

В теории чисел рассматриваются в основном целые числа. Поэтому слово «число» подразумевает обычно целое число, а буквы a, b, c . . . обозначают целые числа. Мы без какого-либо упоминания применяем такие известные свойства чисел, как коммутативность a + b = b + a, дистрибутивные законы (a + b)c = ac + bc и a(b + c) = ac + ac и т. п. В курсе «Числовые системы» [8] эти законы будут подробно рассмотрены, а пока мы используем их как очевидные свойства чисел.

Делимость чисел. Пусть a и b – произвольные целые числа. В некоторых случаях существует целое число q, для которого a = bq.

ОПРЕДЕЛЕНИЕ 1.1 . Пусть a, b Z. Число a делится на b, если существует целое число q с условием a = bq.

		.
То, что a делится .на b, записываем в виде		.
		a . b. Если a не делится на b,
.
то записываем a 6. b.
Используя логическую символику, получаем
.
.	q Z	a = bq.
a . b

Кроме того, если число a делится на b, то говорят, что b – делитель числа a и используют запись b | a.

Свойства делимости. Из определения делимости нетрудно получить следующие свойства.

СВОЙСТВО 1. Каждое число a делится на 1 и делится на самого себя.

Доказательство. Имеем a = 1·q, где q = a Z и a = a·q, где q = 1 Z. Поэтому a ... 1 и a ... a.

СВОЙСТВО 2. Отношение делимости транзитивно, т. е. a ... b b ... c a ... c.

Доказательство. Так как a ... b, то a = bq1, где q1 Z. Аналогично, b ... c, т.е. b = cq2, где q2 Z. Тогда a = cq для q = q2q1 Z. Поэтому a ... c.

4

СВОЙСТВО 3. Если числа a и b делятся на c, то a + b, a − b и ka,

где k Z, делятся на число c, т.е.
.	.	.	.	.
.	.	.	.	.
a . c	b .	c a + b .	c, a − b .	c, ka . c.

Доказательство. Так как a и b делятся на c, то a = cq1 и b = cq2 для

q1, q2 . Z. Тогда a + b = cq1 + cq2 =. c(q1 +		.q2), где q1 + q2 Z. Поэтому
.	.	.
a + b . c. Так же получаем, что a − b . c и ka		. c.

Сформулировать и доказать аналогичные утверждения для нескольких " чисел.

СВОЙСТВО 4. Пусть дано равенство a1 + a2 + · · · + am = b1 + b2 + + · · · + bn, в котором все члены, кроме одного, делятся на c. Тогда и этот, оставшийся член, также делится на c.

Доказательство. Пусть все члены, кроме a1, делятся на c Имеем a1 = (−a2) + · · · + (−am) + b1 + b2 + · · · + bn. В правой части все слагаемые делится на c. Поэтому их сумма, т.е. число a1, делится на c.

СВОЙСТВО 5. Пусть a и b – натуральные числа. Если a делится на b , то a > b. Если a и b делятся друг на друга, то a = b.

Доказательство. Пусть a ... b. Тогда a = bq, где q Z и q > 0. Поэтому q > 1. Умножив неравенство q > 1 на b, получим bq > b, т.е. a > b.

Если a и b делятся друг на друга, то a > b и b > a. Тогда a = b.

Частное и остаток. Частное и остаток от деления a на b рассматриваются в школьном курсе математики. Хорошо известен «способ деления уголком» для нахождения частного и остатка. Например, при делении 1243 на 10 получаем частное 124 и остаток 3, т.е. 1243 = 10 · 124 + 3. Рассмотрим точные определения.

ОПРЕДЕЛЕНИЕ 1.2. Пусть a, b Z и b > 0. Если для некоторых

q, r Z выполнено равенство
a = bq + r,
где
0 6 r < b,	(1.1)

то число q называется неполным частным, а число r – остатком от деления a на b.

Неравенство (1.1) – это признак остатка. Вместо слов «неполное частное» будем обычно говорить «частное».

5

ТЕОРЕМА 1.1. Пусть a и b – произвольные целые числа и b > 0. Частное и остаток от деления a на b существуют и определены однозначно.

Доказательство. Установим вначале существование частного и остатка. В бесконечно возрастающей последовательности чисел

. . . , −2b, −b, 0, b, 2b, 3b, . . .

выберем наибольшее число bq, не превосходящее числа a. Получим

bq 6 a и b(q + 1) > a.

(1.2)

Рассмотрим число r = a − bq. Тогда

a = bq + r.

(1.3)

Из первого неравенства в (1.2) имеем 0 6 a − bq, т.е. 0 6 r. Из второго неравенства получаем a − bq < b, т.е. r < b. Итак, мы имеем равенство (1.3), и выполнен признак остатка 0 6 r < b. Поэтому число q можно назвать частным, а число r – остатком от деления a на b.

Установим единственность частного и остатка. Пусть наряду с частным q и остатком r, существует еще одно частное q1 и остаток r1. Имеем два условия

a = bq + r,	где 0 6 r < b,	(1.4)
a = bq1 + r1,	где 0 6 r1 < b.	(1.5)

Нужно проверить, что q = q1 и r = r1. Методом от противного докажем, что r = r1. Пусть r 6= r1. Можно считать, что r1 > r, т.е. r1 − r N. Вычтем из равенства (1.4) равенство (1.5). Получим

0 = b(q − q1) + (r − r1),

(1.6)

откуда r1−r = b(q−q1). Итак, натуральное число r1−r делится на число b. По свойству делимости 5 получаем, что r1 − r > b. Однако из (1.5) имеем r1 − r < b, противоречие. Поэтому r = r1.

Учитывая r − r1 = 0, из (1.6) получаем 0 = b(q − q1). Так как b 6= 0, то q − q1 = 0. Тогда q = q1, что и нужно. Теорема доказана.

6

Лекция 2. Наибольший общий делитель. Алгоритм Евклида.

Пусть d – делитель числа a. Тогда −d также является делителем числа a. Поэтому, делителю d > 0 числа a всегда сопутствует отрицательный делитель −d. Мы будем рассматривать только положительные делители чисел, и слова «делитель числа» всегда означают положительный делитель.

ОПРЕДЕЛЕНИЕ 2.1 . Пусть a, b, c – произвольные целые числа. Число c называется общим делителем чисел a и b, если c является делителем как числа a, так и числа b.

ОПРЕДЕЛЕНИЕ 2.2. Наибольшим общим делителем ( НОД ) чисел a и b называется наибольший из общих делителей чисел a и b.

Наибольший общий делитель чисел a и b обозначается через (a, b).

ПРИМЕР. (12, 8) = 4, (12, −8) = 4, (3, 7) = 1, (0, 5) = 5.

Ровно в одном случае наибольший общий делитель (a, b) не существует. Пусть a = 0 и b = 0. Поскольку ноль делится на любое число, то любое число – общий делитель чисел a = 0 и b = 0. Поэтому среди общих делителей чисел a и b нельзя выбрать наибольшее число и (a, b) не существует.

Рассмотрим способ для нахождения наибольшего общего делителя.

ЛЕММА 2.1. Пусть число a делится на b > 0. Тогда справедливы два утверждения.

1)Множество общих делителей чисел a и b совпадает с множеством делителей одного числа b.

2)(a, b) = b.

Доказательство. 1) Обозначим через Da,b множество общих делителей чисел a и b, а через Db – множество делителей одного числа b. Проверим, что Da,b = Db, т.е.

a) Da,b Db и b) Db Da,b.

7

Установим a). Если d Da,b, то d – общий делитель чисел a и b. Тогда d – делитель одного числа b, т.е. d Db. Получили Da,b Da.

Проверим b). Если d Db, то b ... d. По условию a ... b. Из a ... b и b ... d следует a ... d, т.е. d Da,b. Получили Db Da,b.

Итак, Da,b = Db, и первое утверждение леммы доказано.

2) Для нахождения НОД чисел a и b, т.е. числа (a, b), нужно из множества Da,b выбрать наибольшее число d. Так как Da,b = Db, то нужно выбрать наибольшее число d из Db – множества делителей числа b. Для любого делителя d числа b по свойству 5 имеем d 6 b. Поэтому наибольшее число из множества делителей числа b есть само число b. Получили d = b. Лемма доказана.

ЛЕММА 2.2 . Пусть для чисел a, b, r справедливо равенство

a= bq + r. Тогда

1)Множество общих делителей чисел a и b совпадает с множеством общих делителей чисел b и r.

2)(a, b) = (b, r).

Доказательство. 1) Обозначим через Da,b множество общих делителей чисел a и b, а через через Db,r – множество делителей чисел b и r.

Используя рассуждения из предыдущей леммы, доказать, что "

Da,b = Db,r.

2) Так как множества Da,b и Db,r совпадают, то и совпадают наибольшие числа (a, b) и (b, r) из этих множеств. Получили (a, b) = (b, r). Лемма доказана.

Ясно, что (a, b) = (−a, b). Поэтому для случая a 6= 0 и b 6= 0 при нахождении НОД можно считать, что a > 0 и b > 0 . Если a = 0 и b = 0, то НОД не существует, если a = 0 и b > 0, то (a, b) = b.

Алгоритм Евклида. Для нахождения НОД двух чисел a > 0 и b > 0 применяется способ, рассмотренный в знаменитых книгах Евклида «Начала», III век до н. э.

Разделим число a на b. Получим a = bq1+r1, где q1 – частное, r1 – остаток от деления a на b. Затем разделим число b на r1, получим b = r1q2 + r2. Далее продолжаем этот процесс, т.е. то, «на что делили на предыдущем шаге» делим на «полученный на предыдущем шаге остаток». Получим систему равенств и условий для полученных остатков r1, r2, . . . , rn.

8

a = bq1 + r1,	0 6 r1 < b,
b = r1q2 + r2,	0 6 r2 < r1,
r1 = r2q3 + r3,	0 6 r3 < r2,	(2.1)
. . .	. . .
rn−3 = rn−2qn−1 + rn−1, 0 6 rn−1 < rn−2,
rn−2 = rn−1qn + rn,	0 6 rn < rn−1,
rn−1 = rnqn+1.

Заметим, что на некотором этапе получается остаток rn+1, равный нулю, и поэтому процесс деления обрывается. В противном случае имели бы бесконечно убывающую последовательность натуральных чисел

b > r1 > r2 > r3 > . . . ,

что невозможно.

Итак, имеем rn+1 = 0, и rn – последний, не равный нулю, остаток.

ТЕОРЕМА 2.1 . Последний, не равный нулю, остаток rn в алгоритме Евклида является наибольшим общим делителем чисел a и b.

Доказательство. Нужно проверить, что (a, b) = rn. Применим пункт 2) леммы 2.2. Получим равенства

(a, b) = (b, r1) = (r1, r2) = (r2, r3) = · · · = (rn−2, rn−1) = (rn−1, rn) = rn.

В последнем равенстве учтено, что rn−1 ... rn и (rn−1, rn) = rn по пункту 2) леммы 2.1. Теорема доказана.

ЗАМЕЧАНИЕ 2.1. Число c является общим делителем двух чисел a и b тогда и только тогда, когда c является делителем НОД этих чисел.

Доказательство. Достаточно проверить, что множество общих делителей двух чисел a и b совпадает с множеством делителей одного числа (a, b). Применим пункт 1) лемм 2.2 и 2.1. Получим

Da,b = Db,r1 = Dr1,r2 = · · · = Drn−1,rn = Drn, где rn = (a, b).

НОД нескольких чисел. Наибольшим общим делителем чисел a1, a2, . . . , an называется наибольший из общих делителей этих чисел. НОД чисел a1, a2, . . . , an обозначается через (a1, a2, . . . , an).

Для нахождения числа d = (a1, a2, . . . , an) нужно вначале найти d1 = (a1, a2), затем d2 = (d1, a3), . . . , dn−2 = (dn−3, an−1), и, наконец, d = (dn−2, an).

Это правило получается из следующей теоремы.

9

ТЕОРЕМА 2.2. Справедлива следующая формула для НОД нескольких чисел

		(2.2)
(a1, a2, . . . , an) =	(a1, a2), a3 , . . . , an .

Доказательство. Проверим вначале, что

(a1, a2, a3) = (a1, a2), a3 .

Рассмотрим D – множество общих делителей трех чисел (a1, a2, a3) и D0 – множество общих делителей двух чисел: а именно, числа d1 = (a1, a2) и числа a3. По замечанию 2.1 слова «с – общий делитель чисел a1 и a2» можно заменить на «с – делитель числа d1 = (a1, a2)».

Поэтому слова «с – общий делитель чисел a1, a2, a3» можно заменить на «с – общий делитель двух чисел d1 и a3». Отсюда D = D0. Так как множества D и D0 равны, то равны и наибольшие элементы из этих множеств,

т.е. (a1, a2, a3) = (a1, a2), a3 .

Доказательство для случая n > 3 провести самостоятельно. Теорема " доказана.

Свойства НОД и взаимно простых чисел. Рассмотрим свойства наибольшего общего делителя.

СВОЙСТВО 1. Для любых чисел a, b, m, где m > 0, справедливо равенство

(am, bm) = (a, b)m.

(2.3)

Тем самым, общий множитель m можно выносить за знак НОД. Доказательство. Найдем НОД чисел a и b с помощью алгорит-

ма Евклида (2.1). Для последнего, не равного нулю остатка rn, имеем rn = (a, b). Умножив на m, получаем из (2.1)

am bm r1m

. . .

rn−3m rn−2m rn−1m

= (bm)q1 + r1m,	0 6 r1m < bm,
= (r1m)q2 + r2m,	0 6 r2m < r1m,
= (r2m)q3 + r3m,	0 6 r3m < r2m,

	. . .	(2.4)
= (rn−2m)qn−1 + rn−1m, 0 6 rn−1m < rn−2m,
= (rn−1m)qn + rnm,	0 6 rnm < rn−1m,
= (rnm)qn+1.

Неравенства, приведенные выше, – это признаки остатка. В частности,

10