Учебник по теории чисел Ильиных АП
.pdf
ТЕОРЕМА 3 Справедливы формулы для НОД и НОК двух чисел
(a, b) = p1min(α1,β1)p2min(α2,β2) . . . pmmin(αm,βm), |
(8) |
[a, b] = p1max(α1,β1)p2max(α2,β2) . . . pmmax(αm,βm). |
(9) |
Доказательство самостоятельно.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Лекция 6. Теоретико-числовые функции.
Рассмотрим функции, которые изучаются в теории чисел. Пусть x — произвольное действительное число.
ОПРЕДЕЛЕНИЕ 1 Целой частью числа x называется наибольшее целое число, не превосходящее x.
Целая часть числа x обозначается через [x].
ПРИМЕР. [2, 45] = 2, [3] = 3, [−3, 4] = −4.
Если представить изображение числа x на числовой оси, то целой частью числа x будет целое число [x] наиболее близко подходящее к x слева. Поэтому [−3, 4] = −4, а не число −3, которое уже больше числа x = −3, 4.
ОПРЕДЕЛЕНИЕ 2 Дробной частью числа x называется разность x− [x].
Дробная часть числа x обозначается через {x}.
ПРИМЕР. {2, 6} = 0, 6; {3} = 0; { − 3, 6} = 0, 4.
Укажем применение функции [x] для нахождения каноническое разложение числа n!.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
По определению n! = 1 · 2 · 3 · . . . · n. Например, 5! = 1 · 2 · 3 · 4 · 5 = 120. При большом n вычисление числа n! затруднительно. Укажем простой способ для вычисления n!.
Предположим, что
n! = p1α1 p2α2 . . . pkαk |
(1) |
каноническое разложение числа n!. Достаточно указать формулу для αi — показателя степени, с которым pi входит в каноническое разложение числа n!.
ТЕОРЕМА 1 Пусть α — показатель, с которым простое число p входит в каноническое разложение числа n!. Тогда
α = |
p |
+ |
p2 |
|
+ |
p3 |
|
+ . . . |
(2) |
|||
|
|
n |
|
|
n |
|
|
|
n |
|
|
|
Заметим, что в правой части этого равенства число слагаемых конечно. Дей-
ствительно, при некотором i имеем |
n |
< 1. Тогда |
n |
= 0 |
и эти слагаемые |
|
|
||||
pi |
pi |
отбрасываются.
Доказательство теоремы. Составим число n!. Для этого нужно перемножить числа
1, 2, 3, . . . , n. (3)
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Какие из сомножителей вносят в произведение сомножитель p? Это те числа, которые делятся на p. Выделим их в списке 1, 2, 3, . . . , n. Получим
1, 2, . . . p, . . . 2p, . . . 3p, . . . , . . . tp, . . . n. (4)
При этом tp — последнее число в (4), делящееся на p. Тогда tp 6 n и (t+ 1)p >
n. Отсюда |
|
|
|
|
|
t 6 |
n |
и t + 1 > |
n |
. |
(5) |
p |
|
||||
|
|
p |
|
||
Неравенства (5) означают, что t — наибольшее целое число, не превосходящее np , т. е. t = hnp i.
Перемножим все числа из (4), и каждое из выделенных чисел внесет в показатель степени для p единицу. Получим pt = p[ np ]. Однако некоторые сомножители в (4) делятся не только на p, но и делятся на p2. Они вносят в показатель двойку, а мы учли только 1. Нужно прибавить еще раз по единице для каждого такого сомножителя в показатель степени. Число таких сомножителей равно
|
n . Добавляя в показатель еще |
|
n |
|
|
получим |
|
[ np ]+[ pn2 ]. |
|
||||||||||
h |
|
i |
h |
|
|
i |
единиц, 3 |
|
p |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||||
p2 |
p2 |
|
|
|
n |
|
|||||||||||||
|
Далее учитываем члены, которые делятся на p |
, добавляем |
[ |
|
|
] в показатель |
|||||||||||||
|
p3 |
||||||||||||||||||
|
|
|
n |
|
|
|
n |
|
n |
|
|
|
|
|
|
|
|
||
степени и т.д. Получаем α = h |
|
i |
+ h |
|
i + h |
|
i + . . . . |
|
|
|
|
|
|
|
|||||
p |
p2 |
p3 |
|
|
|
|
|
|
|
||||||||||
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
ПРИМЕР. Определить показатель степени α, с которым p = 11 входит в число a = 1000!.
Имеем α = [100011 ] + [1000121 ] = 90 + 8 = 98.
Ответ. Число a = 1000! содержит 11 в 98 степени.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Число делителей и сумма делителей натурального числа Пусть n —
произвольное натуральное число. Напомним, что под делителями числа n подразумеваются только положительные делители.
ОПРЕДЕЛЕНИЕ 3 Числом делителей натурального числа n называется количество всех делителей числа n.
Число делителей числа n обозначается через τ(n).
ОПРЕДЕЛЕНИЕ 4 Суммой делителей натурального числа n называется сумма всех делителей числа n.
Сумма делителей числа n обозначается через σ(n).
ТЕОРЕМА 2 Пусть
n = pα1 1 pα2 2 . . . pαk k
каноническое разложение числа n. Тогда число делителей для n вычисляется по формуле
τ(n) = (α1 |
+ 1) · (α2 + 1) · |
. |
. . · (αk + 1). |
(6) |
|||||||||
Сумма делителей числа n вычисляется по формуле |
|
||||||||||||
σ(n) = |
p1α1+1 |
− 1 |
· |
p2α2+1 − 1 |
· |
. . . |
· |
pkαk+1 − 1 |
. |
(7) |
|||
|
|||||||||||||
|
|
p1 |
|
|
1 |
p2 1 |
|
pk 1 |
|
||||
След Пред Стр |
Начало Оглавление Обратно Меню Экран Выход |
|
|||||||||||
|
− |
|
|
− |
|
|
|
− |
|
||||
Доказательство. Рассмотрим произвольный делитель b числа n. По теореме 2 из предыдущей лекции он имеет вид
b = p1β1 p2β2 . . . pkβk |
(8) |
где 0 6 β1 6 α1, 0 6 β2 6 α2, . . . , 0 6 βk 6 αk. Чтобы получить все делители b в (8), выбираем β1 из множества 0, 1, 2, . . . , α1. Имеем α1 + 1 способов выбора. С каждым выбором β1 сочетаем выбор β2,— всего α2 +1 способов выбора и т.д. По правилу произведения в комбинаторике получаем (α1 + 1)(α2 + 1) . . . (αk + 1) способов выбора. В силу однозначности записи натурального числа в каноническом виде, полученные делители попарно различны. Получаем формулу (6).
Установим формулу (7). Для этого рассмотрим выражение
S = (1 + p1 + p21 + · · ·+ pα1 1 )(1 + p2 + p22 + . . . pα2 2 ) . . . (1 + pk + p2k + · · ·+ pαk k ). (9)
Чтобы вычислить выражение S нужно каждый член из первой скобки в (9) умножить на каждый член из второй, третьей, . . . и просуммировать полученные произведения. При перемножении данных членов получаем произведения для суммирования, равные b = pβ11 pβ22 . . . pβkk .
Однако, эти произведения не что иное, как делители числа n. Поэтому вы-
ражение S — это сумма делителей числа n, т.е. S = σ(n).
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Вычислим выражение S другим способом. В каждой из k скобок в выражении (9) для S имеем сумму членов геометрической прогрессии.
Значения скобок в правой части (9) равны |
|
|
||||
|
p1α1+1 − 1 |
, |
p2α2+1 − 1 |
, . . . , |
p2αk+1 − 1 |
, |
|
p1 − 1 |
p2 − 1 |
pk − 1 |
|||
|
|
|
|
|||
Перемножим эти дроби и произведение приравняем к σ(n). Получим формулу (7).
ЗАДАЧА 1. Вычислить сумму делителей и число делителей числа n = 1000.
Решение. Вначале найдем каноническое разложение для n = 1000, а затем применим формулы (6) и (7).
Имеем 1000 = 103 = 23 · 53. Тогда |
|
|
|
|
|
||||
τ(1000) |
= (3 + 1)(3 + 1) = 16, |
|
|
|
|||||
σ(1000) |
= |
24 − 1 |
· |
54 |
− 1 |
= 15 |
· |
624 |
= 2340. |
|
|
4 |
4 |
||||||
|
1 |
|
|
|
|||||
ЗАДАЧА 2. Найти натуральное число, зная, что оно имеет ровно два простых делителя, число всех делителей равно 6, а сумма делителей равна 28.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Решение. Рассмотрим каноническое разложение n = pα1 1 pα2 2 . При этом α1, α2 > 1, т.е. α1 + 1 > 2 и α2 + 1 > 2. Имеем
|
τ(n) = (α1 + 1)(α2 + 1) = 6, |
(10) |
||||
|
σ(n) = |
p1α1+1 − 1 |
· |
p2α2+1 − 1 |
= 28. |
(11) |
|
p1 − 1 |
|
||||
|
|
p2 − 1 |
|
|||
Из (10), с учетом α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. |
|
|
|
||||||||||||
Имеем |
p12 |
− 1 |
· |
p23 |
− 1 |
= 28, т.е. равенство со следующими ограничениями |
||||||||||
p1 |
p2 |
|||||||||||||||
|
1 |
− |
1 |
|
|
|
|
|
|
|
|
|
||||
на сомножители− |
|
|
|
(p1 + 1) (p22 + p2 + 1) = 28. |
||||||||||||
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
| |
|
{z |
|
} | |
|
{z |
|
} |
|
|
|
|
|
|
|
|
>3 |
|
|
|
>7 |
|
|
|||
Тогда возможен единственный вариант для записи 28 в виде двух таких сомножителей, а именно p1 + 1 = 4, p22 + p2 + 1 = 7. Отсюда p1 = 3, p2 = 2 и получаем n = 31 · 22. Ответ n = 12.
След Пред Стр Начало Оглавление Обратно Меню Экран Выход
Лекция 7. Теория сравнений.
Пусть m– натуральное число, которое будем называть модулем, a и b — произвольные целые числа.
ОПРЕДЕЛЕНИЕ 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). |
След Пред Стр Начало Оглавление Обратно Меню Экран Выход