Данный материал будет полезен при изучении основ теории делимости в 8 физико-математическом классе (учебный комплекс А.Г. Мерзляк, В. М. Поляков), при работе с детьми интересующимися математикой и в старших классах при подготовке к ЕГЭ. Материал включает торию и свойства делимости, ее применение при решении уравнений с двумя переменными в целых числах, теорию остатков, сравнение по модулю, примеры применения сравнения по модулю при доказательстве утверждений
Df: Число а делится на число b (b≠0), если существует такое к
(кZ), что а=bк
а – кратное для b
b – делитель для а
ОСНОВНЫЕ СВОЙСТВА ДЕЛИМОСТИ
.1
Если
а
,0
аато
0
а
bakто
то
а
,0
,
bа
cbиbа
,
nbиmа
.2
Если
.3
Если
.4
Если
.5
Если
caто
,
mn
abто
сbaто
.6
Если
сbиса
,
Решить
3
у
х
уравнение
8
у
х
3
2
9
х
2
у
8
в
целых
числах
818
42
8
1
2
4
,1
;8
3
х
у
3
х
у
Zух ,
у
у
х
3
,8
3
х
;1
Zух ,
3
3
х
у
,2
;4
у
у
х
х
,1
;1
3
3
х
х
х
у
,4
;2
у
у
,1
;1
,1
;8
у
у
3
х
3
х
Zух ,
3
3
,8
;1
у
у
х
х
Zух ,
Ответ
,1;1,1;1:
,1;1
.1;1
3
3
х
х
у
у
,2
;4
3
3
х
х
у
у
,4
;2
х
у
,1
;1
х
у
,1
;1
Th
:
Если
атоNbZа
,
,
bq
r
,
где
0
b
.
r
Если
:
Th
дают
,
равные
иNmZbZа
числа
mbaто
остатки
,
,
bиа
при
делениина
т
:
Если
Th
делениина
т
остатки
тоmbaиNmZbZа
,
числа
bиа
при
,
дают
,
равные
числа
bиа
,
Nтгдет
называются
если
числа
эти
сравнимыми
при
делении
по
тна
:
Целые
,
Df
модулю
дают
равные
остатки
.
bа
mod
m
:
того
чтобы
Th
Для
модулю
Nтгдет
mba
.
,
bиа
целые
числа
,
необходимо
и
достаточно
,
были
сравнимы
по
чтобы
СВОЙСТВА СРАВНЕНИЯ
.1
Если
.2
Если
.3
Если
bа
mod
bа
mod
mod
b
а
cbm
,
m
m
,
,
m
mod
cbcато
,
ато
c
mod
m
m
аcто
bc
mod
mod
m
.4
Если
а
b
.5
Если
bа
.6
Если
bа
mod
mod
mod
cm
,
cm
m
,
,
d
d
mod
mod
,
m
,
ато
n
n
b
аcто
mod
bd
m
m
dbcато
m
mod
m
mod
Докажите, что n² + 1 не делится на 3 ни при каком целом n.
Решение:
Каждое целое число n сравнимо по модулю 3 либо с 0, либо с 1, либо с 2.
Если n
Если n
Если n
≡
≡
≡
0 (mod 3), то n²
≡
0 (mod 3) – (св. 6) и n² + 1
≡
1 (mod 3) – (св. 2).
1 (mod 3), то n² + 1
2 (mod 3), то n² + 1
≡
≡
2 (mod 3).
2 (mod 3).
Таким образом, ни в одном случае мы не получим n² + 1
≡
0 (mod 3).
Вывод: n² + 1 не делится на 3
Докажите, что число вида 3m+2 (при целом m) не является полным
квадратом.
Доказательство.
Проведем от противного.
Пусть 3m + 2 = n2 при некотором натуральном n.
Рассмотрим остатки от деления n на 3:
если n
≡
0(mod 3), то n
2
≡
0(mod 3),
если n
если n
≡
≡
1(mod 3), то n
2
≡
1(mod 3),
2(mod 3), то n
2
≡
4(mod 3)
≡
1(mod 3).
Но n2 = 3m + 2
≡
2(mod 3) — противоречие.
Вывод: число вида 3m+2 (при целом m) не является полным квадратом.