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

Допустим, что c — общее кратное чисел a и b. Тогда c = aq и c = bt. С учетом

.

.

(6) имеем c = a1dq и c = a1dt. Тогда a1dq = a1dt и a1q = b1t. Отсюда a1q . b1.

.

.

C учетом (a1, b1) = 1 получаем q . b1, т.е. q = b1s. Тогда c = a1dq = a1db1s =

a1db1d

ab

s =

s.

d

d

ab

Итак, любое общее кратное c чисел a и b равно

s.

ab

d

Обратно, любое число c =

s, где s

Z является общим кратным чисел a

d

и b. Получили следующую формулу для общих кратных c чисел a и b

ab

где s Z.

(7)

c =

s,

(a, b)

Наименьшее общее кратное получим при s = 1. Поэтому [a, b] = (a,abb).

ЗАМЕЧАНИЕ 1 Число c общее кратное чисел a и b тогда и только тогда, когда c кратно их НОК [a, b].

	Действительно, в формуле (7) для общих кратных c чисел a и b заменим	ab
		(a, b)

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

на [a, b]. Получим

c = (a,abb)s = [a, b]s.

Аналогично определению НОК двух чисел можно дать определение НОК нескольких чисел.

ОПРЕДЕЛЕНИЕ 2 Наименьшим общим кратным [a1, a2, . . . an] чисел a1, a2, . . . an называется наименьшее из положительных общих кратных этих чисел.

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

a1, a2, . . . an = [[a1, a2], a3], . . . , an .

(8)

Доказательство. Проверим вначале, что [a1, a2, a3] = [[a1, a2], a3]. Пусть M — множество общих кратных трех чисел a1, a2, a3, M0 — множество общих кратных двух чисел [a1, a2] и a3.

По замечанию 1 слова «c кратно чисел a1 и a2» можно заменить на слова «c кратно числу [a1, a2]». Поэтому M = M0. Тогда совпадают наименьшие положительные числа из этих множеств, т.е. [a1, a2, a3] = [[a1, a2], a3].

Случай n > 3 аналогичен. Теорема доказана.

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

Лекция 4. Простые числа.

Среди натуральных чисел 1, 2, 3, . . . только число a = 1 имеет один делитель.

Все числа a > 1 имеют по крайней мере два делителя, а именно, 1 и a. У неко-

торых чисел нет других делителей, отличных от 1 и a.

ОПРЕДЕЛЕНИЕ 1 Натуральное число a > 1 называется простым чис-

лом, если у него нет делителей, отличных от 1 и самого числа a.

ОПРЕДЕЛЕНИЕ 2 Натуральное число a > 1 называется составным,

если оно имеет делитель, отличный от 1 и a.

ПРИМЕР. Числа 2, 7, 31 — простые, а числа 4, 12, 28 − 1 —составные.

Заметим, что понятие простого и составного числа вводится на множестве

чисел > 1. Поэтому 1 не принадлежит ни к простым числам, ни к составным.

Понятия простого и составного числа являются отрицанием друг друга. Ес-

ли известно, что число a > 1 не простое, то делается вывод, что оно составное.

Число a > 1, не являющееся составным, — простое число.

Свойства простых чисел.

СВОЙСТВО 1. Пусть p — наименьший делитель среди неединичных дели-

телей числа a > 1. Тогда p — простое число.

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

Доказательство. Предположим противное. Тогда p — составное число. По-
					.
					.
этому p имеет делитель p1, отличный от 1 и p. Имеем 1 < p1 < p. Так как a . p
.	.
.	.
и p . p1, то a . p1. Получили неединичный делитель p1 числа a, меньший чем p.
Противоречие, т.к. p — наименьший делитель среди неединичных делителей
числа a. Значит p — простое число.
СВОЙСТВО 2. Пусть p — наименьший делитель среди неединичных дели-
телей составного числа a. Тогда p 6 √a.
Доказательство. По свойству 1 p — простое число. Так как p — делитель
числа a, то a = pt. При этом t 6= 1, иначе a = p и a — простое, что не так.
Так как t	6= 1 и a = pt, то t — неединичный делитель числа a. Поскольку
p — наименьший делитель среди неединичных делителей числа a, то p 6 t.
Домножив обе части этого неравенства на p, получим p2 6 pt. Так как pt = a,
то p2 6 a и p 6 √a.
СВОЙСТВО 3. Пусть p — простое число, a — произвольное целое число.
.
.
Тогда a . p или (a, p) = 1.
Доказательство. Рассмотрим d = (a, p). Тогда d — делитель простого числа
					.
					.
p. Поэтому d = 1 или d = p. Если d = 1, то (a, p) = 1, если d = p, то a . p.
	.			.	.
	.			.	.
СВОЙСТВО 4. Если ab . p и p — простое число, то a . p или b					. p. Доказа-
			.	.
тельство. Предположим противное a			.	.
			. p и b	. p. По свойству 3 (a, p) = 1 и
	След Пред Стр Начало	Оглавление Обратно Меню Экран Выход
			6	6

	.
	.
(b, p) = 1. Тогда (ab, p) = 1. Однако ab . p, и поэтому (ab, p) = p, противоречие.
Аналогичное утверждение справедливо для нескольких сомножителей.
		.
		.
СВОЙСТВО 5. Пусть p и q простые числа. Если p . q, то p = q.
Доказательство самостоятельно.
Одним из основных фактов о простых числах является следующая
ТЕОРЕМА 1 (Евклид, III в. до н. э.) Простых чисел бесконечно много.
Доказательство. Предположим противное, т.е. простых чисел конечное число.
Пусть
	p1, p2, . . . , pn		(1)
полный список всех простых чисел.
Составим натуральное число a = p1 ·p2 ·. . .·pn + 1. Тогда a > 1. Рассмотрим
наименьший делитель p среди неединичных делителей числа a. По свойству 1
p — простое число. Тогда p = pi для некоторого i, так как в списке (1) учтены
все простые числа.	.	.
	.	.
Из p = pi следует p1 · p2 · . . . · pn . p. Кроме того, a . p, т.к. мы рассматриваем
p — делитель числа a.	.	.	.
.
.	.	.	.
Имеем a . p и p1 · p2	· . . . · pn . p. Тогда a − p1	· p2 · . . . · pn . p, т.е. 1	. p.
Число 1 имеет только одиничный делитель. Поэтому p = 1. Противоречие, т.к.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

p — неединичный делитель. Итак, простых чисел бесконечно много. Теорема доказана.

Решето Эратосфена. Для нахождения множества всех простых чисел из промежутка 1, 2, . . . , a применяется метод, называемый «решетом Эратосфена». Рассмотрим этот метод.

Выпишем список чисел 2, 3, . . . , a и выберем из них простые числа. Для это-

го

1.Обводим первое число списка (т.е. число 2 ) кружком и вычеркиваем все последующие числа, кратные двум. Находим первое невычеркнутое число

— это 3. Обводим его кружком и вычеркиваем все последующие числа, кратные 3. Следующее число первое невычеркнутое число 5. Повторяем действия для 5 и так далее.

2.Если вычеркнутые числа, кратные p и при этом p2 > a, то процесс завершаем.

Тем самым, мы каждый раз вычеркивали числа 6= p и кратные p, и это осуществлялось для всех p, для которых p2 > a.

Тогда искомый список найден в силу следующего утверждения.

ТЕОРЕМА 2 Числа, оставшиеся в списке невычеркнутыми составляют множество простых чисел в промежутке от 1 до a.

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

Доказательство. Ясно, что вычеркиваются только составные числа.
Пусть b —невычеркнутое число. Предположим, что b составное число. Возь-
мем его наименьший делитель p среди неединичных делителей. По свойству 2
число p простое и p 6										√a, т.е. p2 6 a. Тогда на каком-то этапе вычеркива-
ния, мы должны были вычеркнуть b, как кратное p, а оно у нас не вычеркнуто.
Значит b — простое число.
Теорема доказана.
ПРИМЕР. Составить список простых чисел от 1 до 50.
Решение. Выписываем числа от 2 до 50 и применяем решето Эратосфена.
После вычеркивания чисел, кратных 11 имеем 112 = 121 > 50 и процесс за-
вершен.				.......	.......	.		.......	.	.......	.
			.		. .			.		.
			. . . .					. .		. .
			. . . .					. .		. .
			. . . .					. .		. .
	.......	.	.......2......... .......3......... 4					.......5.........		6 .......7......... 8 9
	.
. .
. .				12 13 14				15		16 17 18 19
. .
10 ......11..........
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50
Ответ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
							След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 5. Каноническое разложение натурального числа.

ТЕОРЕМА 1 Произвольное натуральное число a > 1 можно представить в виде произведения простых чисел. Это представление однозначно с точностью до порядка сомножителей.

Доказательство. Докажем вначале существование разложения. Рассмотрим наименьший неединичный делитель p1 числа a. Тогда p1 — простое число по свойству 1 из свойств простых чисел.

Имеем a = p1a1. Если a1 = 1, то a = p1 — искомое разложение с одним сомножителем. Пусть a1 6= 1. Рассмотрим наименьший неединичный делитель p2 числа a1.

Тогда a1 = p2a2 и a = p1p2a2. При a2 = 1 получим a = p1 · p2 разложение на два сомножителя. Продолжим этот процесс. Тогда либо получим

a = p1 · p2 · p3 · . . . · pm

(1)

искомое разложение, либо процесс будет бесконечен. Второй случай невозможен. Действительно, тогда имеем бесконечную последовательность натуральных чисел, меньших a

a > a1 > a2 > . . . .

(2)

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

Однако возможно лишь конечное число натуральных чисел, меньших a, противоречие.

Докажем единственность разложения. Пусть наряду с разложением (1) имеем другое разложение

a = q1 · q2 · q3 · . . .

· qn.

(3)

Проверим, что m = n и после перестановки сомножителей в одном из разложений справедливы равенства p1 = q1, . . . , pm = qm.

Правая часть из (1) очевидно делится на p1. Поэтому q1 · q2 · . . . · qn ... p1. По свойству простых чисел 4 по крайней мере один из сомножителей q1, q2, . . . , qn делится на p1. Переставляя эти сомножители считаем, что q1 ... p1. По свойству 5 q1 = p1. Приравняем правые части из (1) и (3) и сократим на p1. Получим p2p3 . . . pm = q2q3 . . . pn. Повторяя рассуждения, имеем p1 = q1, p2 = q2, . . . .

Если m 6= n, то можно считать n > m. Тогда после m сокращений приходим к равенству qm+1 . . . qn = 1. Получили противоречие, так как qm+1 . . . qn > 1.

Поэтому m = n и переставляяя q1, . . . , qm имеем p1 = q1, p2 = q2, . . . — единственность разложения.

Теорема доказана.

Обычно в разложении (1) перемножают одинаковые сомножители. Тогда

a = p1α1 p2α2 . . . pkαk ,	(4)
След Пред Стр Начало Оглавление Обратно Меню Экран Выход

где p1, . . . , pk — попарно различные простые числа и α1, α2, . . . , αk > 0. Запись натурального числа в виде (4) называется каноническим разложением числа a

С помощью канонического разложения можно найти все делители числа a.

ТЕОРЕМА 2 Пусть дано каноническое разложение (4) натурального числа a. Тогда все делители b числа a имеют вид

b = p1β1 p2β2 . . . pkβk ,

(5)

где 0 6 β1 6 α1, 0 6 β2 6 α2, , . . . , 0 6 βk 6 αk.

Доказательство самостоятельно.

Каноническое разложение можно использовать также для нахождения НОД и НОК целых чисел. Запишем числа a и b в виде

a = p1α1 p2α2 . . . pmαm,	(6)
b = p1β1 p2β2 . . . pmβm,	(7)

где αi > 0, βi > 0. Возможно, что простое число pi входит в одно из разложений, а в другое не входит. Тогда впишем pi в нулевой степени в то разложение, где его нет.

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