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

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

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

Пусть в разложении (5.1) сомножитель p1 входит α1 раз, p2 входит α2 раз и т.д. Тогда

a = p1α1 p2α2 . . . pkαk ,

(5.3)

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

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

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

b = p1β1 p2β2 . . . pkβk ,	(5.4)
где 0 6 β1 6 α1, 0 6 β2 6 α2, , . . . , 0 6 βk 6 αk.
Доказательство самостоятельно.	"

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

a = p1α1 p2α2 . . . pmαm,	(5.5)
b = p1β1 p2β2 . . . pmβm,	(5.6)

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

ТЕОРЕМА 5.3. Справедливы формулы для НОД и НОК двух чисел

(a, b) = p1min(α1,β1)p2min(α2,β2) . . . pmmin(αm,βm),	(5.7)
[a, b] = p1max(α1,β1)p2max(α2,β2) . . . pmmax(αm,βm).	(5.8)
Доказательство самостоятельно.	"

21

+ . . .

Лекция 6. Теоретико-числовые функции.

Рассмотрим функции, которые изучаются в теории чисел. Пусть x – произвольное действительное число.

ОПРЕДЕЛЕНИЕ 6.1. Целой частью числа x называется наибольшее целое число, не превосходящее x.

Целая часть числа x обозначается через [x]. ПРИМЕР. [2, 4] = 2, [5 ] = 5, [−3, 7] = −4.

Если представить изображение числа x на числовой оси, то целой частью числа x будет целое число [x] наиболее близко подходящее к x слева. Поэтому [−3, 7] = −4, а не число −3, которое уже больше числа x = −3, 7.

ОПРЕДЕЛЕНИЕ 6.2 . Дробной частью числа x называется разность x − [x].

Дробная часть числа x обозначается через {x}.

ПРИМЕР. {2, 4} = 0, 4; {5} = 0; {−3, 7} = −3, 7 − (−4) = 0, 3.

Укажем применение функции [x] для нахождения канонического разложения числа n!. По определению n! = 1 · 2 · 3 · . . . · n. При большом n вычисление числа n! непосредственно по определению затруднительно. Укажем более быстрый способ для вычисления n!. Предположим, что

n! = p1α1 p2α2 . . . pkαk

(6.1)

каноническое разложение числа n!. Достаточно указать формулу для αi – показателя степени, с которым число pi входит в каноническое разложение числа n!.

ТЕОРЕМА 6.1. Пусть α – показатель, с которым простое число p входит в каноническое разложение числа n!. Тогда

α =	p		+	p2			+	p3			(6.2)
		n			n				n

Заметим, что в правой части этого равенства число слагаемых конеч-

	но. Действительно, при некотором i имеем						n	< 1. Тогда слагаемые
							pi
			,			, . . . равны нулю и отбрасываются.
		n			n
		pi			pi+1

22

Доказательство теоремы. При вычислении числа n! перемножаются сомножители 1, 2, 3, . . . , n. Какие из этих чисел вносят в произведение сомножитель p? Это те числа, которые делятся на p. Выделим их в списке

1, 2, 3, . . . , n. Получим

1, . . . , p, . . . , 2p, . . . , 3p, . . . , tp, . . . , n.

(6.3)

При этом tp – последнее число в (6.3), делящееся на p. Тогда tp 6 n и

(t + 1)p > n. Отсюда

n

n

t 6

и

t + 1 >

.

(6.4)

p

p

Неравенства (6.4) означают, что t – наибольшее целое число, не превос-

ходящее

n

, т. е. t =

n

.

p

p

Перемножим всеhчислаi

из (6.3). Каждое из выделенных чисел внесет

в показатель степени для p единицу. Получим pt

= p[ np ]. Однако некото-

рые сомножители в (6.3) делятся не только на p, но и делятся на p2. Они

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

еще раз по единице для каждого такого сомножителя в показатель степе-

сомножителей равно

n .

ни. Показать самостоятельно,nчто число таких

h

i

"

[ n ]+[

n ]

.

p2

Добавляя в показатель еще h

i

единиц,

получим

p

p

p2

p2

3

n

Затем учитываем члены, которые делятся на p

, добавляем [

] в пока-

p3

затель степени и т.д. Получаем формулу (6.2). Теорема доказана.

ПРИМЕР 1. Найти α – показатель степени, с которым p = 11 входит в

каноническое разложение числа a = 1000!.

Решение. Имеем α = [

1000 ] + [

1000 ] = 90 + 8 = 98. Ответ α = 98.

11

121

ПРИМЕР 2. Найти каноническое разложение числа 16!.

Решение. Имеем 16! = 2α1 · 3α2 · 5α3 · 7α4 · 11α5 · 13α6 . При этом

α1 =

16

+

16

+

16

+

16

= 15,

h

16i

i

h

16i

h

8

h16i16

h

2

h

4

i

h16 i

16i

16

α2 =

+

= 6, α3

=

= 3,

3

9

5

α4 = h

i = 2,

α5 = h

i = 1, α6 = h

i = 1.

7

11

13

Ответ 16! = 215 · 36 · 53 · 72 · 11 · 13.

23

Число делителей и сумма делителей натурального числа. Пусть n – произвольное натуральное число. Напомним, что под делителями числа n подразумеваются только положительные делители. Рассмотрим две функции τ(n) и σ(n), которые называются соответственно числом делителей и суммой делителей натурального числа n.

ОПРЕДЕЛЕНИЕ 6.3. Пусть n N. Тогда

τ(n) равно числу делителей натурального числа n, σ(n) равно сумме делителей натурального числа n.

Укажем формулы для вычисления значений функций τ(n) и σ(n).

ТЕОРЕМА 6.2. Пусть дано каноническое разложение

n = pα1 1 pα2 2 . . . pαk k .

Тогда число делителей натурального числа n вычисляется по формуле

τ(n) = (α1 + 1) · (α2 + 1) · . . . · (αk + 1).

(6.5)

Сумма делителей натурального числа n вычисляется по формуле

σ(n) =	p1α1+1 − 1	·	p2α2+1 − 1	·	. . .	·	pkαk+1 − 1	.	(6.6)
	p1 − 1		p2 − 1
							pk − 1

Доказательство. Рассмотрим произвольный делитель b числа n. По теореме 5.2 он имеет вид

b = p1β1 p2β2 . . . pkβk ,	(6.7)
где
0 6 β1 6 α1, 0 6 β2 6 α2, . . . , 0 6 βk 6 αk.	(6.8)
Чтобы получить все делители вида (6.7), выбираем	строки

(β1, β2, . . . , βk) с условием (6.8). При этом β1 имеет α1 + 1 способов выбора, а именно, 0, 1, 2, . . . , α1. Число β2 имеет α2 + 1 способов выбора и т.д. По комбинаторному «правилу произведения» получаем ровно (α1 + 1)(α2 + 1) . . . (αk + 1) способов выбора строки (β1, β2, . . . , βk). Для каждой такой строки составляем делитель (6.7). В силу однозначности записи натурального числа в каноническом виде, полученные делители попарно различны. Получаем формулу (6.5).

24

Установим формулу (6.6). Для этого рассмотрим выражение

S = (1+p1 +p21 +· · ·+pα1 1 )(1+p2 +p22 +· · ·+pα2 2 ) . . . (1+pk +p2k +· · ·+pαk k ).

Чтобы вычислить выражение S нужно каждый член из первой скобки умножить на каждый член из второй, третьей, и т.д., а затем просуммировать полученные произведения. При перемножении данных членов получаем произведения для суммирования, равные b = pβ11 pβ22 . . . pβkk , с условием (6.8) Однако эти произведения не что иное, как все делители числа n. Поэтому выражение S – это сумма всех делителей числа n, т.е. S = σ(n).

Вычислим это выражение другим способом. В каждой из k скобок в выражении S имеем сумму членов геометрической прогрессии. Применив формулу для этой суммы, получим, что значения скобок в правой части

выражения S равны соответственно
p1α1+1 − 1	,	p2α2+1 − 1	, . . . ,	p2αk+1 − 1	.
p1 − 1		p2 − 1		pk − 1

Перемножим эти дроби, и полученное произведение приравняем к σ(n). Получим формулу (6.6).

ЗАДАЧА 1. Найти число делителей и сумму делителей для n = 1000. Решение. Вначале найдем каноническое разложение числа n = 1000, а

затем применим формулы (6.5) и (6.6). Имеем 1000 = 103 = 23 · 53. Тогда

	τ(1000)	= (3 + 1)(3 + 1) = 16,
	σ(1000)	=	24 − 1	·	54 − 1	= 15	·	624	= 2340.
			1		4			4

ЗАДАЧА 2. Натуральное число n имеет ровно два простых делителя. Количество всех делителей числа n равно 6, а сумма делителей равна 28. Найти число n.

Решение. Так как n имеет ровно два простых делителя, то для канонического разложения n = pα1 1 pα2 2 получаем α1, α2 > 1. Поэтому α1 + 1 > 2

	и α2 + 1 > 2. По теореме 6.2
	τ(n) = (α1 + 1)(α2 + 1) = 6,						(6.9)
	σ(n) =	p1α1+1 − 1	·		p2α2+1 − 1	= 28.	(6.10)
		p1 − 1			p2 − 1

25

Из τ(n) = (α1 + 1)(α2 + 1) = 6, с учетом α1 + 1 > 2, α2 + 1 > 2, получаем, что 1) α1 + 1 = 2, α2 + 1 = 3 или 2) α1 + 1 = 3, α2 + 1 = 2. Поэтому возможен один из случаев:

1) α1 = 1, α2 = 2 или 2) α1 = 2, α2 = 1.

Если дан случай 2), то переименуем число p1 в p2, а число p2 – в p1. Получим случай 1). Поэтому далее считаем, что α1 = 1, α2 = 2.

Вместо (6.10) имеем

p12

− 1

p23

− 1

= 28. Получаем следующее равен-

· p2

p1

− 1

− 1

ство, где учтено, что p1, p2 > 2:

(p1 + 1) (p22 + p2 + 1) = 28.

Так как 3 не является |

{z

} |

{z

1} + 1 = 3

p1 + 1

4

p

>3

>7

6

>

делителем 28, то

. Тогда

и p22 + p2 + 1 > 7. Возможен единственный вариант для записи числа 28 в виде произведения двух таких сомножителей: 28 = 4 · 7. Поэтому

p1 + 1 =	4 и p22 + p2 + 1 = 7. Отсюда p1 = 3 и p2 = 2. Получили
n = 31 · 22	= 12. Ответ n = 12.

Функция π(x) Пусть x – натуральное число. Через π(x) обозначим количество простых чисел в промежутке от 1 до x. Проблема поведения функции π(x) при x → ∞ является одной из наиболее трудных и интересных задач теории чисел. Поскольку простых чисел бесконечно много, то

π(x) → ∞ при x → ∞.

Математики начала 19 века поставили задачу нахождения достаточно известной функции f(x), асимптотически эквивалентной функции π(x)

(записывается π(x) f(x)). Это означает, что lim π(x) = 1. Возникла

x→∞f(x)

гипотеза, что в качестве f(x) можно взять lnxx.

Это асимптотическое равенство, впервые доказанное ВаллеПуссеном и Адамаром в 1896 г., называется в настоящее время законом распределения простых чисел. Важный шаг к доказательству закона распределения простых чисел удалось сделать П.Л.Чебышеву. Он показал,

что для достаточно больших x выполняется неравенство
0, 9212 ·	x	< π(x) < 1, 1055 ·	x		(6.11)
				.
	ln x		ln x

26

Лекция 7. Теория сравнений.

Пусть m – натуральное число, которое будем называть модулем, a и b – произвольные целые числа.

ОПРЕДЕЛЕНИЕ 7.1 . Число a сравнимо с числом b по модулю m, если a и b имеют одинаковые остатки при делении на m.

То, что число a сравнимо с числом b по модулю m, записывается в виде

a ≡ b (mod m).

ПРИМЕР. Верно ли, что 11 ≡ 5 (mod 4)? Число 11 при делении на 4 имеет остаток 3, а число 5 при делении на 4 имеет остаток 1. Поэтому 11 6≡5 (mod 4). Однако следующие сравнения справедливы

17	≡ 5	(mod 4),
18	≡ −6	(mod 4),
15	≡ 0	(mod 5).

ТЕОРЕМА 7.1 . Пусть a и b – произвольные целые числа. Тогда равносильны следующие три утверждения :

1)a ≡ b (mod m),

2)a − b ... m,

3)существует число q Z с условием a = b + mq.

Доказательство 1) 2). Дано a ≡ b (mod m). Нужно доказать, что a − b ... m. По условию числа a и b имеют один и тот же остаток r при делении на m. Поэтому

a = mq1 + r, b = mq2 + r.

Вычтем из первого равенства второе. Получим a − b = m(q1 − q2), где q1 − q2 Z. Получили a − b ... m.

2)3). Дано a − b ... m, т.е. a − b = mq, где q Z. Отсюда a = b + mq.

3)1). Дано a = b + mq, где q Z. Разделим число b на m, получим некоторое частное q1 и остаток r1. Имеем b = mq1 + r1, где 0 6 r1 < m.

27

Тогда a = b + mq = (mq1 + r1) + mq = m(q + q1) + r1. Запись a = m(q + q1) + r1 и неравенство 0 6 r1 < m означают, что q + q1 – частное, r1 – остаток отделения a на m. Получили, что a и b имеют имеют один и тот же остаток r1 при делении на m, т.е. a ≡ b (mod m).

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

Итак, каждое из трех условий 1) – 3) в теореме 7.1 можно принять за определение сравнимости чисел. Утверждая сравнимость чисел a и b, мы будем в дальнейшем ссылаться на любое из этих трех условий.

Свойства сравнений. Отношение сравнимости целых чисел по модулю m обладает свойствами, во многом аналогичными свойствам отношения равенства чисел.

СВОЙСТВО 1. Отношение сравнимости является отношением эквивалентности.

Доказательство. Нужно проверить, что отношение сравнимости рефлексивно, симметрично и транзитивно.

Рефлексивность означает a ≡ a (mod ) для всех a Z. Это верно, т.к. числа a и a имеют один и тот же остаток при делении на m.

Симметричность. Дано a ≡ b (mod m). Нужно доказать, что b ≡ a (mod ). Если числа a и b имеют равные остатки при делении на m, то, очевидно, числа b и a имеют равные остатки при делении на m.

Транзитивность. Из a ≡ b (mod m) и b ≡ c (mod m) следует a ≡ c (mod m). Дано, что a и b имеют равные остатки при делении на m, а также b и c имеют равные остатки при делении на m. Тогда a и c имеют равные остаток при делении на m. Получили a ≡ c (mod m).

СВОЙСТВО 2 . Сравнения можно почленно складывать, вычи-

тать и умножать: если a ≡ b (mod m) и		c ≡ d (mod m), то
a + c ≡ b + d	(mod m),		(7.1)
a − c ≡ b − d	(mod m),		(7.2)
ac ≡ bd (mod m).			(7.3)
Доказательство утверждения	(7.1). Так	как a	≡ b (mod m)

и c ≡ d (mod m), то a − b ... m и c − d ... m. Тогда (a − b) + (c − d) ... m, т.е. (a + c) − (b + d) ... m и a + c ≡ b + d (mod m).

28

Самостоятельно проверить утверждения (7.2), (7.3), а также и после- " дующие свойства.

СВОЙСТВО 3. Обе части сравнения можно умножать на произвольное целое число

a ≡ b (mod m) ak ≡ bk (mod m).

Обе части сравнения можно разделить на число, взаимно простое с модулем

ak ≡ bk (mod m) (k, m) = 1 a ≡ b (mod m).

СВОЙСТВО 4. Обе части сравнения можно возводить в степень с показателем k N

a ≡ b (mod m) ak ≡ bk (mod m).

СВОЙСТВО 5. Обе части сравнения и модуль можно умножать на произвольное число k > 0

a ≡ b (mod m) ak ≡ bk (mod mk).

Обе части сравнения и модуль можно разделить на их общий делитель k > 0

ak ≡ bk (mod mk) a ≡ b (mod m).

СВОЙСТВО 6 . Если a ≡ b (mod m1) и a ≡ b (mod m2), то a ≡ b (mod m), где m = [m1, m2] – НОК модулей m1 и m2.

СВОЙСТВО 7. Если в выражении

s = axα1 1 xα2 2 . . . xαnn + bxβ11 xβ22 . . . xβnn + . . .

заменим числа a, b, . . . , x1, x2, . . . , xn на соответствующие, сравнимые по модулю m, числа a0, b0, . . . , x01, x02, . . . , x0n , то получим выражение

s0 = a0(x01)α1 (x02)α2 . . . (x0n)αn + b0(x01)β1 (x02)β2 . . . (x0n)βn + . . . ,

сравнимое по модулю m с исходным выражением s, т.е.

s0 ≡ s (mod m).

29

Классы вычетов. По свойству 1 отношение сравнимости по модулю m является отношением эквивалентности. Поэтому можно рассматривать классы эквивалентных элементов для отношения сравнимости ≡. Напомним необходимые определения и теоремы из вводного курса математики. Пусть R – отношение эквивалентности на множестве M и a M.

ОПРЕДЕЛЕНИЕ 7.2. Классом элементов, эквивалентных элементу a, называется множество

Ma = {x M | xRa}.

(7.4)

Перебирая элементы a из M, получим все классы Ma для отношения R. Пусть даны два таких класса Ma и Mb.

Справедлив следующий признак равенства классов эквивалентных элементов.

ТЕОРЕМА 7.2. Два класса Ma и Mb равны тогда и только тогда, когда элементы a и b эквивалентны, т.е.

Ma = Mb aRb.

(7.5)

Если говорим, что Ma, Mb, Mc, . . . – множество классов для отношения R, то считаем, что выписаны все классы и они выписаны без повторений. Справедливо следующее утверждение.

ТЕОРЕМА 7.3. Пусть R – отношение эквивалентности на множестве R. Тогда классы эквивалентных элементов Ma, Mb, Mc, . . .

образуют разбиение множествa M.

То, что классы эквивалентных элементов Ma, Mb, Mc, . . . образуют разбиение множествa M означает:

1)подмножества Ma, Mb, Mc, . . . не пусты;

2)объединение данных подмножеств равно M;

3)Ma, Mb, Mc, . . . пересекаются по пустому множеству.

Применим данные результаты к отношению сравнимости ≡.

ОПРЕДЕЛЕНИЕ 7.3 . Классом вычетов по модулю m называется класс эквивалентных элементов для отношения сравнимости по модулю m.

30