Учебник по теории чисел Ильиных АП

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

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

А.П. Ильиных

ТЕОРИЯ ЧИСЕЛ

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

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

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Содержание

Лекция 1. Делимость целых чисел. Частное и остаток . . . . . . . . . . . . . . . . . . . 3 Лекция 2. Наибольший общий делитель. Алгоритм Евклида . . . . . . . . . . . . . 8 Лекция 3. Линейная форма НОД. НОК и его свойства . . . . . . . . . . . . . . . . . 18 Лекция 4. Простые числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 Лекция 5. Каноническое разложение натурального числа . . . . . . . . . . . . . . 28 Лекция 6. Теоретико-числовые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Лекция 7. Теория сравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Лекция 8. Полная система и приведенная системы вычетов . . . . . . . . . . . . .48 Лекция 9. Кольцо классов вычетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Лекция 10. Сравнения первой степени с одной переменной . . . . . . . . . . . . . 66 Лекция 11. Непрерывные дроби . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Лекция 12. Системы сравнений первой степени . . . . . . . . . . . . . . . . . . . . . . . . 86 Лекция 13. Показатель числа. Свойства показателя . . . . . . . . . . . . . . . . . . . .94 Лекция 14. Первообразные корни . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Лекция 15. Индексы. Свойства индексов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Лекция 16. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112 Лекция 17. Запись рациональных чисел в виде десятичной дроби . . . . . . 119 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

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

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

Делимость чисел. Свойства свойства делимости.

Пусть a и b — произвольные целые числа. В некоторых случаях частное от деления на b является целым числом. Обозначив это частное буквой q, получим a = bq.

ОПРЕДЕЛЕНИЕ 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 ... c b ... c a + b, a − b, ka ... c.

	.
Если	.
	a . b, то говорят, что b — делитель числа a и записывают b a.

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

1.Каждое число a делится на 1 и самого себя.

Доказательство. Имеем a = 1 · a, где q = a Z и a = a · 1, где 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 = q1q1 Z. Поэтому a ... c.

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

Доказательство. Имеем a и b делятся на c, т.е. a = cq1 и b = cq2 для q1, q2 Z. Тогда a + b = cq1 + cq2 = c(q1 + q2), где q1 + q2 Z. Поэтому a+b ... 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 = bq1 и b = aq2 для q1, q2 N. Тогда a = aq1q2 и q1q2 = 1 для q1, q2 N . Поэтому q1 = q2 = 1. Из a = bq1 и q1 = 1 следует a = b.

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

Пусть a, b Z и b > 0. Если для некоторых q, r Z выполнено равенство

a = bq + r,

где

0 6 r < b,

(1)

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

то число q называется неполным частным, а число r – остатком от деления a на b. Неравенства (1) — это признак остатка. Вместо слов «неполное частное» будем говорить обычно «частное».

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

Доказательство. Установим вначале существование частного и остатка. Рас-

смотрим ряд чисел . . . , b(−1), b · 1,	b · 2, b · 3, . . .	и подберем такое q, что
bq 6 a и	b(q + 1) > a.	(2)
Рассмотрим число r = a − bq. Тогда
a = bq + r.		(3)

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

Установим единственность частного и остатка. Пусть наряду с остатком r и

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

частным q, существует еще одно частное q1 и остаток r1. Имеем два равенства

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

Нужно проверить, что q = q1 и r = r1. Методом от противного докажем, что

r= r1. Пусть r 6= r1. Можно считать, что r1 > r. Вычтем из равенства (4) равенство (5). Получим

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

(6)

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

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

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

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

Если c — общий делитель чисел a и b, то, очевидно, −c также общий делитель a и b. Общему делителю c > 0, всегда сопутствует отрицательный делитель −c. Мы будем учитывать только положительные делители, и слово «делитель» всегда означает положительный делитель.

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

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

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

Рассмотрим (0, 0). Поскольку ноль делится на любое число, то любое число

— общий делитель чисел 0 и 0. Поэтому среди общих делителей нельзя выбрать наибольшее число и НОД чисел 0 и 0 не существует.

Рассмотрим способ для нахождения НОД.

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

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

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

2)НОД чисел a и b равен b, т.е. (a, b) = b.

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

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

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

ЛЕММА 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. Выбирая в множествах Da,b = Db,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, получим a = bq2 + r2. Далее продолжаем этот процесс, т.е. то, «что делили на предыдущем шаге» делим на «полученный на предыдущем шаге остаток». Получим систему равенств и

След Пред Стр Начало Оглавление Обратно Меню Экран Выход