3 / 9
Примем следующие обозначения:
N
0
— множество всех натураль-
ных чисел и {0};
N
— множество всех натуральных чисел;
{
q
}
—
множество всех простых и составных чисел;
{
c
}
— множество всех
составных чисел;
{
p
}
— множество всех простых чисел.
Для нумерации простых чисел подряд по возрастанию используем
левый верхний индекс:
1
p
= 2
;
2
p
= 3
;
3
p
= 5
;
4
p
= 7
и т.д. Отметим,
что 1 является единственным натуральным числом, не являющимся
ни простым, ни составным, т.е.
{
q
}
=
N
\{
1
}
.
Представление составных чисел через простой сомножитель.
Согласно
основной теореме арифметики
, каждое натуральное число
n >
1
единственным образом представимо в виде
n
=
k
Y
i
=1
p
α
i
i
,
(1)
где
k
∈
N
;
p
1
< p
2
< . . . < p
k
— упорядоченные по возрастанию
простые числа;
α
1
, α
2
, . . . , α
k
∈
N
. Представление числа
n
в виде (1)
называется его
каноническим разложением
.
Используя каноническое разложение для составных чисел, нетруд-
но показать, что верно утверждение
о единственном представлении
составного числа через его наименьший простой делитель
.
Утверждение 1.
Каждое составное число единственным образом
представимо в виде
c
=
p
1
q,
(2)
где
p
1
— наименьший простой делитель
c
;
величина
q
удовлетворяет
условию
p
1
≤
q
.
Сформулируем утверждение о представлении составных чисел че-
рез их простые делители.
Утверждение 2.
Каждое составное число представимо в виде
c
=
pq,
(3)
где p — простой делитель
c
:
p
≤ √
c
; величина
q
удовлетворяет
условию
p
≤
q
.
Существование представления (3) следует напрямую из предста-
вления (2). При этом условие
p
≤ √
c
для
c
=
pq
следует из условия
p
≤
q
.
Отметим, что представление составных чисел через их простые де-
лители (3) не всегда является единственным для конкретного состав-
ного числа, однако применимо для каждого его простого делителя, не
превышающего
√
c
.
Обобщение теоремы о полном множестве простых чисел.
Определим индексы
i, j, k
∈
N
. Введем следующие обозначения:
{
q
+1
2
k
}
=
{
2
k
+ 1
}
— множество всех нечетных чисел (за исключени-
ем 1);
{
c
+1
2
j
}
=
{
2
j
+ 1
}
— множество всех нечетных составных чисел;
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 91