Задачи с целыми числами Первая часть (материал для подготовки к ЕГЭ по математике (профильный уровень))
1
Задачи с целыми числами
Первая часть.
Дихтярь М. Б.
Простые и составные числа
Натуральные числа – это числа 1, 2, 3,… . Множество всех
натуральных чисел обозначается через N.
Целые числа – это числа
0, 1, 2, 3,
. Множество всех целых
чисел обозначается через Z.
Натуральное число b называется делителем целого числа a, если
существует целое число с такое, что
.abс=
Натуральное число
2р
называется простым, если его
натуральными делителями являются только числа 1 и р.
Наименьшим простым числом является число 2. Число 2 –
единственное простое чётное число.
Всякое простое число
3p
представимо в виде
61рk=+
или
6 1,рk=−
где
.kN
Натуральные числа называются взаимно простыми, если они не
имеют общих делителей, кроме единицы.
Например, числа
n
и
1n +−
взаимно простые; числа
21n +
и
23n +−
взаимно простые.
Если число делится на каждое взаимно простое число, то оно
делится на их произведение.
Если произведение
ab
делится на с, причём
a
и с взаимно простые
числа, то
b
делится на с.
Если произведение
12
,
т
p p p
где
12
, , ,
m
p p p
– простые числа,
делится на простое число
,p
то
p
совпадает с одним из чисел
12
, , ,
m
p p p
.
Натуральное число называется составным числом, если оно имеет
не менее трёх натуральных делителей, включая единицу и само число.
Если произведение
12
,
т
p p p
где
12
, , ,
m
p p p
– простые числа,
делится на составное число
,а
то
а
равно произведению из нескольких
сомножителей чисел
12
, , ,
m
p p p
.
Число
n
всегда является составным, если оно чётное (кроме
2n =
)
или, если оно кратно 5 (кроме
5n =
) или, если сумма цифр этого числа
делится на 3 (кроме
3n =
).
Для того чтобы показать, что данное число составное, достаточно
2
представить его в виде произведения двух натуральных чисел, ни одно
из которых не равно 1.
Единица – единственное натуральное число, которое не является ни
простым, ни составным.
Чтобы определить, что число р является простым (если не
очевидно, что оно составное), надо:
1) найти корень квадратный этого числа (найти
р
);
2) проверить делимость числа р на все простые числа, которые
меньше
.р
Пример. Проверить являются ли числа 151, 161, 171 простыми.
Решение. Так как числа 151, 161 не являются чётными, не делятся
на 5, не делятся на 3, то они могут быть простыми числами.
1. Проверяем число 151.
1) Находим
12 151 13.
2) Проверим делимость числа 151 на простые числа: 7, 11 (простые
числа меньше 12, но не равные 2, 3 и 5).
Так как число 151 не делится ни на одно из рассматриваемых
чисел, то оно является простым числом.
2. Проверяем число 161.
1) Находим
12 161 13.
2) Проверим делимость числа 161 на простые числа: 7, 11.
Так как число 161 делится на 7, то оно не является простым числом.
3. Проверяем число 171.
Так как сумма цифр числа 171 равна 9, то это число делится на 9.
Это означает, что число 171 не является простым числом.
Ответ. Число 151 является простым числом.
Каждое натуральное число
1n
можно единственным способом
представить в виде произведения степеней простых чисел:
12
12
m
k
kk
m
n p p p=
, где
12
, , ,
m
p p p
– простые делители числа n, числа
1
,k
2
,,
m
kk
– натуральные числа (
i
k
является числом повторений числа
i
р
). Такое представление числа n называется каноническим
разложением числа n. Число делителей числа n, включая единицу и
число n, равно произведению
( ) ( ) ( )
12
1 1 1
m
k k k+ + +
.
Деление с остатком.
Разделить натуральное число a на натуральное число b – значит
найти такие числа q и r, что
a bq r=+
, где
0 1.rb−
Число a
3
называется делимым, число b называется делителем, число q называется
частным, число r называется остатком.
Отметим:
1) любое целое число n можно представить в виде
,n kq r=+
где k
– натуральное число, q – целое число, r – целое число (остаток), который
принимает k значений, при этом
0,1, , 1rk−
или
0, 1, 2,r
;
Например,
281 8 33 17,= +
281 5 51 26= +
,
281 6 51 25.= −
2) если при делении натурального числа a на натуральное число b
остаток равен нулю, то число a делится на b без остатка (нацело) и
a bq=
(в этом случае говорят, что число a делится на число b или а
кратно b);
3) из
( )
1n+
целых чисел найдутся хотя бы два числа, которые при
делении на n имеют равные остатки (разность чисел с равными
остатками делится на n);
4) из n последовательных натуральных чисел одно и только одно
делится на n;
5) число
!1mn=+
не делится ни на какое натуральное число
,kn
так как
!n
делится на
,kn
а тогда при делении на
kn
числа
!1mn=+
получаем в остатке 1 (остаток не равен нулю);
6) числа
! 2; ! 3; ; !n n n n+ + +
являются составными идущими
подряд натуральными числами. Количество этих чисел равно
( )
1.n −
7) остаток от деления суммы (разности, произведения) двух чисел
на третье равен остатку от деления суммы (разности, произведения) их
остатков;
8) остаток от деления числа на 9 (на 3) равен остатку отделения
суммы цифр этого числа на 9 (на 3);
9) если целое число делится на произведение натуральных чисел, то
оно делится на каждый сомножитель.
Сравнение чисел по модулю
Определение. Целые числа a и b называются сравнимыми по
модулю
nN
, если при делении на число n они дают одинаковый
остаток. Обозначение
( )
mod .a b n
Отметим: если
( )
mod ,a b n
то
ab−
делится на n.
Например,
( )
7 2 mod5
так как
7 1 5 2, 2 0 5 2;= + = +
( )
9 1 mod5−
так как
( )
9 1 10− − = −
делится на 5.
Некоторые свойства сравнений чисел по модулю.
4
1.
( ) ( ) ( )
mod , mod mod .a b n b c n а c n
2.
( )
moda b n
и
( )
mod ,c d n
то
1)
( )( )
mod ,a c b d n+ +
2)
( )( )
mod .a c b d n
3.
( )
mod , ,a b n k N
то
( )
mod .
kk
a b n
Признаки делимости
В десятичной системе счисления натуральное число n записывается
в виде
1 2 1nn
n a a a a
−
=
12
1 2 1
10 10 10 ,
nn
nn
n a a a a
−−
−
= + + + +
где
11
1 9, 0 9, , 0 9.
nn
a a a
−
Отметим:
1 1 1 1 1 1
10 .
k
n n k k n n k k
aa а а а a a а а а
− + − +
= +
Например,
3
24657843 10 24657 843; 24657843 10 2465784 3.= + = +
1. Натуральное число делится на 4 тогда и только тогда, когда две
последние цифры этого числа, образуют число, которое делится на 4.
2. Натуральное число делится на 8 тогда и только тогда, когда три
последние цифры этого числа, образуют число, которое делится на 8.
3. Натуральное число делится на 11 тогда и только тогда, когда
разность суммы цифр, стоящих на нечетных местах и суммы цифр
стоящих на четных местах, делится на 11.
Например,
а) число 63976 делится на 11, так как число
( ) ( )
6 9 6 3 7 11+ + − + =
делится на 11;
б) число 282754 на 11 не делится, так как
( ) ( )
2 2 5 8 7 4 10+ + − + + = −
не делится на 11.
Наибольший общий делитель. Наименьшее общее кратное.
Общим делителем нескольких целых чисел, не равных
одновременно нулю, называется число являющееся делителем каждого
из этих чисел.
Наибольший из общих делителей называется наибольшим общим
делителем и обозначается НОД.
Обозначение:
12
( ; ; ; )
n
НОД a a a −
наибольший общий делитель
чисел
12
; ; ;
n
a a a
.
Если НОД(m, n)=d, то существуют взаимно простые натуральные
числа х и у таковы, что
,.m dx n dy==
Отметим: число х является
делителем
,m
а у является делителем числа
.n
5
Общим кратным нескольких целых чисел, не равных
одновременно нулю, называется число, которое делится на каждое из
этих чисел.
Наименьшие из общих кратных называется наименьшим общим
кратным и обозначается НОК.
Обозначение:
12
( ; ; ; )
n
НОК a a a −
наименьшее общее кратное чисел
12
; ; ;
n
a a a
.
Отметим:
( ; ) ( ; ) .НОД a b НОК a b а b =
Способы нахождения НОД
Первый способ.
Чтобы найти НОД нескольких чисел надо:
1) найти каноническое разложение каждого числа на простые
множители;
2) найти произведение их общих множителей в наименьших
степенях;
3) полученное число является НОД этих чисел.
Второй способ.
Чтобы найти НОД двух чисел, делят большее число на меньшее, и
если получается остаток, не равный нулю, то делят меньшее число на
остаток; если снова получается остаток, не равный нулю, то делят
первый остаток на второй и так продолжают до тех пор, пока в остатке
не получится ноль.
Последний делитель будет НОД этих чисел.
Для того чтобы найти НОД трёх и более чисел, то находят НОД
каких-нибудь двух чисел из данных. Затем находят НОД найденного
делителя и какого-нибудь третьего числа из данных чисел и так
продолжают до тех пор, пока не будут взяты все данные числа.
НОД последней пары и будет НОД данных чисел.
Способы нахождения НОК.
Чтобы найти НОК нескольких чисел надо:
1) найти каноническое разложение каждого числа на простые
множители;
2) найти произведение всех множителей, входящих хотя бы в одно
из разложений, при этом множители, входящие в каждое разложение,
надо брать в наибольших степенях;
3) полученное число является НОК.
6
Замечание. Если числа не имеют общих множителей, то их НОК
равен произведений этих чисел.
Пример. Найдите НОД чисел 726, 660, 504 двумя способами и
НОК этих чисел.
Найдём НОК и НОД первым способом.
Так как
2 2 3 2
726 2 3 11 , 660 2 3 5 11, 504 2 3 7,= = =
то
3 2 2
(726;660;504) 2 3 5 7 11 304920,
(726;660;504) 2 3 6.
НОК
НОД
= =
= =
Второй способ.
1) Сначала найдём НОД чисел 726, 660.
Разделим число 726 на 660 и получим
726 660 66.=+
Разделим число 660 на 66 и получим
660 10 66 0.= +
Так как 660 делится на 66 без остатка, то НОД(726; 660)=66.
2) Найдём НОД чисел 504, 66.
Разделим число 504 на 66 и получим
504 7 66 42.= +
Разделим число 66 на 42 и получим
66 42 24.=+
Разделим число 42 на 24 и получим
42 24 18.=+
Разделим число 24 на 18 и получим
24 18 6.=+
Разделим число 18 на 6 и получим
18 3 6 0.= +
3) Так как 18 делится на 6 без остатка, то НОД(726; 660; 504)=6.
Основные алгебраические формулы
1. Для произвольных чисел a и b и произвольного натурального
числа n справедлива формула бинома Ньютона
0 1 1 1 1
()
n n n i n i i n n n n
n n n n n
a b C a C a b C a b C ab C b
− − − −
+ = + + + + + +
, где
)!(!
!
ini
n
C
i
n
−
=
.
Если a и b целые числа, то
( )
1 1 2 1
( ) ( ) .
n n n n n n n
n
k целое число
ab а a C a b nb b a b kа b
− − −
−
+ = + + + + + = +
Таким образом, существует целое число k такое, что для
произвольных целых чисел a и b и произвольного натурального числа n,
выполняется равенство
( ) .
nn
a b kаb+ = +
2. Для произвольных чисел a и b и произвольного натурального
числа n справедлива формула
( )
( )
2 1 2 1 2 2 1 2 2 2 2 1 2n n n n n n n
a b a b a a b a b ab b
+ + − − −
+ = + − + − − +
Если a и b целые числа, не равные нулю, то
( )
( )
( )
2 1 2 1 2 2 1 2 2 2 2 1 2n n n n n n n
k целое число
a b a b a a b a b ab b k a b
+ + − − −
−
+ = + − + − − + = +
7
Таким образом, существует целое число k такое, что для
произвольных целых чисел a и b, которые не равны нулю, и
произвольного натурального числа n, выполняется равенство
( )
2 1 2 1
.
nn
a b k аb
++
+ = +
Это означает, что
( )
аb+
является делителем числа
( )
2 1 2 1
.
nn
ab
++
+
3. Для произвольных чисел a и b и произвольного натурального
числа n справедлива формула
( )
( )
1 2 3 2 2 1n n n n n n n
a b a b a a b a b ab b
− − − − −
− = − + + + + +
Если a и b целые числа, если
0аb
, то
( )
( )
( )
1 2 3 2 2 1
.
n n n n n n n
k целое число
a b a b a a b a b ab b k a b
− − − − −
−
− = − + + + + + = −
Таким образом, существует целое число k такое, что для
произвольных целых чисел a и b таких, что
0аb
, и произвольного
натурального числа n, выполняется равенство
( )
11
.
nn
a b k аb
−−
− = −
Это
означает, что
( )
аb−
является делителем числа
( )
11
.
nn
ab
−−
−
Задачи на простые числа
1. Докажите: если
3p −
простое число, то оно представимо в виде
6 1,рk=
где
kN
.
Решение. Пусть
6,рk
=+
где
kN
и
0, 1, 2, 3.
=
Если
0,
=
то
6;рk=
если
2,
=
то
( )
2 3 1 ;рk=
если
2,
=
то
( )
3 2 1 .рk=+
Так как
,kN
то числа
6,рk=
( )
2 3 1 ,рk=
( )
3 2 1рk= + −
составные. Если
1,
=
то число
61рk=
может быть простым.
2. Найдите простое число p, если
2
14 1p +−
простое число.
Решение. 1. Если
2,р =
то
22
14 1 57 14 1 3 19pp+ = + = −
составное число.
2. Если
3,р =
то
2
14 1 127p + = −
простое число.
3. Пусть
6 1,рk=
где
kN
и
3.p
Тогда, имеем
( ) ( )
2 2 2
14 1 14 36 12 1 1 3 168 56 5 .р k k k k+ = + + = +
Итак,
( )
( )
22
14 1 3 168 56 5 . 1р k k+ = +
Так как
( )
2
168 56 5 56 3 1 5 1,k k k k + = +
если
kN
, то из (1)
следует, что
2
14 1,p +
где
3,p
не является простым числом.
Ответ.
3.р =
8
3. Найдите все простые числа p и q, для которых число
( )
4
q
p +−
точный квадрат.
Решение. Если
2,q =
то при любом простом числе p
число
( )
2
4p +−
точный квадрат.
Если
2,q
то простое число q является нечётным числом, тогда
( )
4
q
p +
будет точным квадратом, если
( )
4p +−
точный квадрат. Если
( )
4p +−
точный квадрат, то найдётся число
kN
такое, что
( )( )
22
4 4 2 2 .p k p k p k k+ = = − = − +
Так как p является простым числом, то равенство
( )( )
22p k k= − +
возможно только в случае когда
2 1 3.kk− = =
Тогда из равенства
( )( )
22p k k= − +
следует, что
5.p =
Ответ.
2q =
и p любое простое число;
простое число
2q
и
5.p =
4. Докажите, что число
( )
1
2 2 1 ,
nn−
−
где
( )
21
n
−−
простое число, при
делении на 9 даёт остаток, равный 1, если
2.n
Решение. Если
2,n
то простое число
( )
2 1 5.
n
−
Так как простое
число
( )
2 1 5,
n
−
то
( )
2 1 6 1
n
k− =
, где
1.k
Рассмотрим два случая.
1) Если
2 1 6 1 2 6
nn
kk− = − = −
этот случай невозможен, так как
6k
делится на 3, а
2
n
не делится на 3.
2) Если
1
2 1 6 1 2 6 2 2 3 1.
n n n
k k k
−
− = + = + = +
Тогда
( )
( )( )
( ) ( )
1 1 2
2 2 1 3 1 6 1 2 2 1 9 2 1.
n n n n
k k k k
−−
− = + + − = + +
Так как
( ) ( )
12
2 2 1 9 2 1,
nn
kk
−
− = + +
если
2,n
то число
( )
1
2 2 1 ,
nn−
−
где
( )
21
n
−−
простое число, при делении на 9 даёт остаток, равный 1.
5. Найдите все тройки последовательных простых чисел, сумма
квадратов которых также является простым числом.
Решение. Пусть
1 2 3
,,p p p
последовательные простые числа.
1. Пусть одно из простых чисел равно 2. Так как
1 2 3
,,p p p
последовательные простые числа, то
1 2 3
2, 3, 5.p p p= = =
Найдём сумму квадратов последовательности 2, 3, 5:
2 2 2
2 3 5 38+ + = −
не простое число (последовательность 2, 3, 5 не
удовлетворяет условию задачи).
9
2. Пусть
1
3.p =
Так как
1 2 3
,,p p p
последовательные простые
числа, то
1 2 3
3, 5, 7.p p p= = =
Найдём сумму квадратов последовательности 3, 5, 7:
2 2 2
3 5 7 83+ + = −
простое число (последовательность 3, 5, 7
удовлетворяет условию задачи).
3. Пусть
1
3.p
Так как
1 2 3
,,p p p
простые числа, которые больше
3, то
1 1 2 2 3 3
6 1, 6 1, 6 1,р k р k р k= = =
где
1 2 3
,,k k k N
.
Тогда, имеем
( ) ( ) ( )
( )
( )
( )
( )
( )
2 2 2
2 2 2 2 2 2
1 2 3 1 2 3 1 2 3
222
1 2 3 1 2 3 1 2 3
6 1 6 1 6 1 36
12 3 3 12 4 1 .
р р р k k k k k k
k k k k k k k k k
+ + = + + = + +
+ + + = + + + + +
Итак,
( )
( )
( )
2 2 2 2 2 2
1 2 3 1 2 3 1 2 3
3 12 4 1 .р р р k k k k k k+ + = + + + + +
(1)
Так как
1 2 3
,,k k k N
, то
( )
( )
222
1 2 3 1 2 3
12 4 1 1.k k k k k k+ + + + +
Тогда
из (1) следует, что
222
1 2 3
ррр+ + −
составное число.
Ответ. 3, 5, 7
6. Найдите все простые числа, которые одновременно являются
суммами и разностями двух простых чисел.
Решение. Пусть
1 2 3 4
, , , ,р р р р р −
простые числа, удовлетворяющие
уравнениям
1 2 3 4
,.р р р р р р= + = −
Так как
12
,р р р=+
то
5.р
Так
как
5р
нечётное число, то
12
рр+
и
34
рр−
нечётные числа
(алгебраическая сумма двух нечётных чисел чётное число), а тогда
24
2.рр==
Таким образом, имеем
13
2, 2.р р р р= + = −
Так как простое число
5р
, то
6 1,рk=
где
1k
.
Тогда, имеем
( )
13
6 1 2, 6 1 2. 1k р k р = + = −
Рассмотрим два случая.
1) Если
6 1,рk=+
то уравнение
3
6 1 2k р = −
принимает вид
( )
3 3 3
6 1 2 6 3 3 2 1 .k р р k р k+ = − = + = +
Число
( )
3
3 2 1рk=+
будет
простым числом, если
2 1 1 0.kk+ = =
Этот случай невозможен, так как
1k
.
2) Если
6 1,рk=−
то уравнение
1
6 1 2k р = +
принимает вид
( )
1 1 1
6 1 2 6 3 3 2 1 .k р р k р k− = + = − = −
Число
( )
1
3 2 1рk=−
будет
простым числом, если
2 1 1 1.kk− = =
Если
1,k =
то
1
3,р =
5р =
. Так как
3
2,рр=−
то
3
7.р =
Итак,
5р =
удовлетворяет условию задачи.
10
Ответ. 5.
7. Докажите, что не существуют наибольшего простого числа.
Решение. Пусть
р −
наибольшее простое число.
Рассмотрим число
( )
2 3 5 1,n р= +
где
2, 3, 5, , р
все простые
числа не больше р. Очевидно,
.n р
Число
( )
2 3 5 р
делится на любое простое число, так как по
предположению
р
наибольшее простое число. Тогда остаток при
делении числа
( )
2 3 5 1n р= +
на любое простое равен 1. Значит, n
не делится ни на одно простое число.
Так как любое составное число
k
делится хотя бы на одно простое
число, которое меньше
k
, то число n является простым числом. Число n
не может быть простым числом, так как
,n р
а по предположению
р
наибольшее простое число.
Из предположения, что существует наибольшее простое число,
получили противоречие. Тогда не существует наибольшего простого
числа.
8.
Докажите, что ни одно из чисел
4 4,р и р где р+ − −
произведение первых т простых чисел, не является квадратом.
Решение. Так как
р −
произведение первых т простых чисел, то р
делится на 2 (является чётным числом) и не делится на 4.
1. Пусть
4р +
является квадратом целого числа п. Тогда
( ) ( )
22
4 4 2 2 .р п р п р п п+ = = − = − +
Так как р – чётное число, то из равенства
2
4рп+=
следует, что п
– чётное число, а тогда
( ) ( )
22пп− +
делится на 4. Так как р не делится
на 4, а
( ) ( )
22пп− +
делится на 4, то
( ) ( )
2
2 2 4 .р п п р п − + +
2. Пусть
4р −
является квадратом целого числа п. Тогда
22
4 4.р п р п− = = +
Так как р – чётное число, то
2
4п +−
чётное число. Тогда
существует число
mN
такое, что
( )
2 2 2
4 2 2 4 2 2 .п т п т п т+ = = − = −
Так как
( )
2
2 2 ,пт=−
то
( )
2т −
делится на 2, а тогда
2
п
и
2
4п +
делятся на 4. Так как р не
делится на 4, а
2
4п +
делится на 4, то
22
4 4 .р п р п + −
Из 1. и 2. следует: ни одно из чисел
44р и р+−
не является
квадратом.
9. Найдите все натуральные числа n такие, что числа
11
4, 6, 10, 30n n n n− + + + −
простые.
Решение. Так как
4n −
простое число, то
4 2.n −
1. Если
4 2 6,nn− = =
то числа
6, 10, 30n n n+ + +
не являются
простыми.
2. Если
4 3 7,nn− = =
то числа
6 13, 10 17, 30 37n n n+ = + = + =
являются простыми. Значит,
7n =
удовлетворяет условию задачи.
2. Пусть
4 5 9.nn−
.
Так как простое число
45n −
, то
4 6 1,nk− =
где
1k
.
Рассмотрим два случая.
1) Если
4 6 1 6 3,n k n k− = − = +
где
1,k
то, например,
30n +
не
будет простым числом, так как
( )
30 6 33 30 3 2 11n k n k+ = + + = + −
число составное (
1k
).
2) Если
4 6 1 6 5,n k n k− = + = +
где
1,k
то, например,
10n +
не
будет простым числом, так как
( )
10 6 15 10 3 2 5n k n k+ = + + = + −
число составное (
1k
).
Ответ. 7.
10. Найдите все простые числа p для которых число
4
2
p
p+
тоже
простое число.
Решение. 1. Если
2,p =
то
24
2 2 20+=
не является простым числом
2.
Если
3,p =
то
34
2 3 89+=
является простым числом
3. Пусть
5.p
Тогда простое число
p −
нечётное число.
Имеем
( ) ( ) ( ) ( )( )
4 4 2 2
2 2 1 1 2 1 1 1 .
p p p
p p p p+ = + + − = + + − +
Итак,
( ) ( )( )
( )
4 2 2
2 2 1 1 1 . 1
pp
p p p+ = + + − +
1) Докажем, что делится на 3. Так как
p −
нечётное число, то
найдётся число
kN
такое, что
21pk=+
. Тогда
( )
( ) ( )
21
11
2 1 2 1 2 4 1 2 3 1 1
2 3 3 1 1 2 3 2 3 3 .
k
p k k
k k k k
kk
+
−−
+ = + = + = + + =
= + + + + = + + +
Так как
( )
1
2 1 2 3 2 3 3
p k k
k
−
+ = + + +
, то
21
p
+
делится на 3.
2) Докажем, что
2
1p −
делится на 3.
Так как
p −
простое число и
5p
, то его можно представить в
виде
6,рk
=+
где
, 1.kN
=
Тогда
( ) ( )( )
2
2
1 6 1 6 1 6 1 .p k k k
− = + − = + − + +
12
Очевидно, если
1
=
, то
( )
61k
+−
делится на 3 и, если
1,
=−
то
( )
61k
++
делится на 3, а тогда
( )( )
2
1 6 1 6 1p k k
− = + − + +
делится на 3.
Итак, доказали:
2
1p −
делится на 3.
3) Так как
( ) ( )( )
4 2 2
2 2 1 1 1 ,
pp
p p p+ = + + − +
то из 1) и 2) следует,
что
4
2
p
p+
, где
5,p
делится на 3. Тогда, так как
4
23
p
p+
и кратно
3, то
4
2
p
p+
, если
5p
, не является простым числом.
Ответ.
3.p =
11. Числа
,рq−
простые числа, число
3
1q −
делится на
,р
а
1р −
делится на
.q
Докажите, что
2
1.р q q= + +
Решение. Так как
1р −
делится на
,q
то существует натуральное
число n
такое, что
1 1.р qn р qn− = = +
Так как
( )
( )
32
1 1 1q q q q− = − + +
делится на простое число
,р
то на
р
делится только одно из чисел
1q −
или
2
1.qq++
1. Пусть
1q −
делится на число
.р
Тогда существует натуральное
число т
такое, что
1 1.q рт q рт− = = +
Так как
1р qn=+
и
1,q рт=+
то
( )
11р рт n р= + + −
это
невозможно. Поэтому
1q −
не делится на число
.р
2. Пусть
2
1qq++
делится на число
.р
Тогда существует
натуральное число
k
такое, что
2
1.qq рk+ + =
а) Если
1,k =
то
2
1.р q q= + +
б) Если
2,k
то
( ) ( ) ( )
22
1 1 1 1 1 .qq рk q q рk k k q q р k k+ + = + = − + − + = − + −
Итак,
( ) ( ) ( )
1 1 1 .qq р k k+ = − + −
Так как
1р −
делится на
,q
то
1 1.р q р q− +
Так как
( ) ( ) ( )
1 1 1 ,qq р k k+ = − + −
( )
1qq+
и
1р −
делятся на
,q
то
1k −
делится на
.q
Это означает, что
1 1.k q k q− +
Так как
1рq+
и
1,kq+
то
( )
2
22
1 1 1qq рk q q q+ + = + + + −
это невозможно. Предположение, что
2,k
неверно. Поэтому
1.k =
Тогда
2
1.р q q= + +
12.
Докажите, что для любого простого числа
11р
число
42
85 324рр−+
делится на 120.
13
Решение. Обозначим:
( )( )
4 2 2 2
85 324 81 4 .q р р q р р= − + = − −
Отметим:
3
120 2 3 5=
.
1. Докажем, что число
( )( )
22
81 4q рр= − −
делится на 5.
Так как
р −
простое число то оно может оканчиваться на одно из
следующих цифр: 1, 3, 7, 9. Тогда
2
р
может оканчиваться на 1 или 9. В
этом случае
( )
2
81р −
или
( )
2
4р −
делится на 5, тогда
q
делится на 5.
2. Докажем, что число
( )( )
22
81 4q рр= − −
делится на 24.
а) Так как
p −
простое число и
11р
, то его можно представить в
виде
6 1.рk=
Тогда
22
36 12 1.p k k= +
Имеем
( ) ( ) ( ) ( )
( )
2 2 2 2
81 4 12 9 3 20 12 4 1 . 1q p p q k k k k= − − = − −
Из (1) следует, что
q
делится на 12.
б) Докажем, что
2
9 3 20kk−
делится на 2.
Если
k −
чётное число, то
2
9 3 20kk−
делится на 2.
Если
k −
нечётное число, то
2
93kk−
чётное число
(алгебраическая сумма двух нечётных чисел является чётным числом), а
тогда число
2
9 3 20kk−
является чётным числом, а значит, оно делится
на 2.
Так как
2
9 3 20kk−
делится на 2, то
q
делится на 24.
Было доказано, что
q
делится на 5. Тогда
q
делится на 120.
13. Какое наибольшее количество простых чисел, больших трёх,
встречается среди 13 последовательных натуральных чисел?
Решение. Любое натуральное число n можно представить в виде
6,n k r=+
где k – натуральное число, r – остаток
0, 1, 2,3r
. Число
6n k r=+
может быть простым только, если
1.r =
Тогда оно имеет вид
6 1,nk=
где
.kN
Пусть n – первый член последовательности 13 натуральных чисел.
Рассмотрим следующие случаи.
1. Пусть
6 2, .n k k N= −
Заданными числами являются числа:
( )
( )
6 2, 6 1, 6 , 6 1, 6 2, 6 3, 6 4, 6 5 6 1 1,
6 6, 6 7 6 1 1, 6 8, 6 9, 6 10.
k k k k k k k k k
k k k k k k
− − + + + + + = + −
+ + = + + + + +
В этом случае может быть не более 4 простых чисел:
( ) ( )
6 1, 6 1, 6 5 6 1 1, 6 7 6 1 1.k k k k k k− + + = + − + = + +
2. Пусть
6 1, .n k k N= −
Заданными числами являются числа:
14
( )
( ) ( )
6 1, 6 , 6 1, 6 2, 6 3, 6 4, 6 5 6 1 1, 6 6,
6 7 6 1 1, 6 8, 6 9, 6 10, 6 11 6 2 1.
k k k k k k k k k
k k k k k k k
− + + + + + = + − +
+ = + + + + + + = + −
В этом случае может быть не более 5 простых чисел:
( ) ( ) ( )
6 1, 6 1, 6 5 6 1 1, 6 7 6 1 1, 6 11 6 2 1.k k k k k k k k− + + = + − + = + + + = + −
3. Пусть
6 , .n k k N=
Заданными числами являются числа:
( )
( ) ( )
6 , 6 1, 6 2, 6 3, 6 4, 6 5 6 1 1, 6 6,
6 7 6 1 1, 6 8, 6 9, 6 10, 6 11 6 2 1, 6 12.
k k k k k k k k
k k k k k k k k
+ + + + + = + − +
+ = + + + + + + = + − +
В этом случае может быть не более 4 простых чисел:
( ) ( ) ( )
6 1, 6 5 6 1 1, 6 7 6 1 1, 6 11 6 2 1.k k k k k k k+ + = + − + = + + + = + −
4. Пусть
6 1, .n k k N= +
Заданными числами являются числа:
( ) ( )
( ) ( )
6 1, 6 2, 6 3, 6 4, 6 5 6 1 1, 6 6, 6 7 6 1 1,
6 8, 6 9, 6 10, 6 11 6 2 1, 6 12, 6 13 6 2 1,
k k k k k k k k k
k k k k k k k k
+ + + + + = + − + + = + +
+ + + + = + − + + = + +
В этом случае может быть не более 5 простых чисел:
( ) ( ) ( ) ( )
6 1, 6 5 6 1 1, 6 7 6 1 1, 6 11 6 2 1, 6 13 6 2 1.k k k k k k k k k+ + = + − + = + + + = + − + = + +
5. Пусть
6 2, .n k k N= +
Заданными числами являются числа:
( ) ( )
( ) ( )
6 2, 6 3, 6 4, 6 5 6 1 1, 6 6, 6 7 6 1 1, 6 8,
6 9, 6 10, 6 11 6 2 1, 6 12, 6 13 6 2 1, 6 14.
k k k k k k k k k
k k k k k k k k
+ + + + = + − + + = + + +
+ + + = + − + + = + + +
В этом случае может быть не более 4 простых чисел:
( ) ( ) ( ) ( )
6 5 6 1 1, 6 7 6 1 1, 6 11 6 2 1, 6 13 6 2 1.k k k k k k k k+ = + − + = + + + = + − + = + +
6. Пусть
6 3, .n k k N= +
Заданными числами являются числа:
( ) ( )
( ) ( )
6 3, 6 4, 6 5 6 1 1, 6 6, 6 7 6 1 1, 6 8, 6 9,
6 10, 6 11 6 2 1, 6 12, 6 13 6 2 1, 6 14, 6 15.
k k k k k k k k k
k k k k k k k k
+ + + = + − + + = + + + +
+ + = + − + + = + + + +
В этом случае может быть не более 4 простых чисел среди 13
последовательных натуральных чисел:
( ) ( ) ( ) ( )
6 5 6 1 1, 6 7 6 1 1, 6 11 6 2 1, 6 13 6 2 1.k k k k k k k k+ = + − + = + + + = + − + = + +
Например, 5 простых чисел будет среди следующих 13
последовательных натуральных чисел: 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23.
Ответ. 5.
14. Найдите число
12
154 ,n p p=
если
( )
1 2 2 1
,p p p p
простые числа
и каждое из чисел
12
4, 4pp−−
является делителем числа
.n
15
Решение. Так как
4, 1, 2,
i
pi−=
является делителем натурального
числа, то
2, 1, 2.
i
pi=
Так как
i
p
простое число и
2
i
p
, то
i
p
и
4
i
p −
нечётные числа Так как
21
,pp
то
12
4 , .p mp m N−
Если
4 , 1; 2, ,
ii
p mp i m N− = =
то уравнение
( )
1 4, 1; 2, ,
i
p m i m N− = =
не
имеет решений. Тогда
4 , 1; 2, .
ii
p mp i m N− =
1. Найдём значения
1
.p
Так как число
1
4p −
равно хотя бы одному нечётному делителю
числа
154 1 2 7 11,=
то
( )
1
4 1; 7;11; 77 .p −
Тогда
1)
11
4 1 5pp− = = −
простое число;
2)
11
4 7 11pp− = = −
простое число;
3)
11
4 11 15pp− = = −
составное число.
4)
11
4 77 81pp− = = −
составное число.
Итак,
22
154 5 770n p n p= =
или
22
154 11 1694 .n p n p= =
2. Найдём значения
2
.p
1) Пусть
22
770 1 2 5 7 11 .n p n p= =
Так как
21
,pp
то нечётное число
2
4p −
равно хотя бы одному
нечётному делителю числа
770 1 2 5 7 11,=
которые не принадлежат
множеству
1; 7;11; 77 .
Тогда
( )
2
4 5; 5 7;11 7;11 7 5 .p −
Итак,
а)
22
4 5 9pp− = = −
составное число;
б)
22
4 7 5 39pp− = = −
составное число;
в)
22
4 11 5 59pp− = = −
простое число;
г)
22
4 11 7 5 389pp− = = −
простое число.
Итак,
770 59 45430nn= =
или
770 389 299530.nn= =
2) Пусть
2
22
1694 1 2 7 11 .n p n p= =
Так как
21
,pp
то нечётное число
2
4p −
равно хотя бы одному
нечётному делителю числа
2
1694 1 2 7 11 ,=
которые не принадлежат
множеству
1; 7;11; 77 .
Тогда
( )
22
2
4 11 ; 7 11 .p −
Итак,
1)
22
4 121 125pp− = = −
составное число;
2)
2 2 2
4 7 121 851 23 37p p p− = = = −
составное число.
Ответ.
45430;n =
или
299530.n =
15. Какое наибольшее количество чисел можно выбрать из отрезка
натурального ряда чисел 1 до 3125 так, чтобы разность любых двух из
них не была простым числом?
16
Решение. 1. Если из исходного натурального ряда берутся числа
вида
2,nk
=+
где
, , 0, 1,k n N
=
то в этой последовательности
разность между двумя соседним числами равна 2 – простое число.
2. Если из исходного натурального ряда берутся числа вида
3,nk
=+
где
, , 0,1,2k n N
=
, то в этой последовательности
разность между двумя соседними числами равна 3 – простое число.
3. Пусть из исходного натурального ряда берутся числа
4,nk
=+
где
, , 0,1,2,3.k n N
=
а) Если
0,
=
то из исходного ряда чисел берётся
последовательность чисел
4, 8, , 781 4,
с общим членом
4,nk=
где
1; 2; ;781.k =
Рассматриваемая последовательность состоит из 781
чисел, разность между любыми двумя числами этой последовательности
кратна 4 (не является простым числом).
б) Если
1,
=
то из исходного ряда чисел берётся
последовательность
1, 5, , 781 4 1,+
с общим членом
4 1,nk=+
где
0;1; ; 781.k =
Рассматриваемая последовательность состоит из 782
чисел, разность между любыми двумя числами этой последовательности
кратна 4.
в) Если
2,
=
то из исходного ряда чисел берётся
последовательность
2, 6, , 780 4 2.+
с общим членом
4 2,nk=+
где
0;1; ; 780.k =
Рассматриваемая последовательность состоит из 781
чисел, разность между любыми двумя числами этой последовательности
кратна 4 (не является простым числом).
г) Если
3,
=
то из исходного ряда чисел берётся
последовательность
3, 7, , 780 4 3.+
с общим членом
4 3,nk=+
где
0;1; ; 780.k =
Рассматриваемая последовательность состоит из 781
чисел, разность между любыми двумя числами этой последовательности
кратна 4.
4. Если из исходного натурального ряда берутся числа вида
,n тk
=+
где
, , , 5, 0,1,2,3, , 1т k n N т т
= −
, то наибольшее
количество чисел, которое можно выбрать из отрезка натурального ряда
чисел 1 до 3125, меньше 782.
Ответ. 782.
Задачи на основные алгебраические формулы
В задачах 16.– 21. Используется следующее:
17
1. Для произвольных целых чисел a и b и произвольного
натурального числа n, существует целое число k такое, что
( ) .
nn
a b kаb+ = +
2. Для произвольных целых чисел a и b, которые не равны нулю, и
произвольного натурального числа n существует целое число k такое,
что
( )
2 1 2 1
.
nn
a b k аb
++
+ = +
Это означает, что
( )
аb+
является делителем
числа
( )
2 1 2 1
.
nn
ab
++
+
3. Для произвольных целых чисел a и b, где
0,ab
и
произвольного натурального числа n существует целое число k такое,
что
( )
.
nn
a b k аb− = −
Это означает, что
( )
аb−
является делителем числа
( )
.
nn
ab−
16. Найдите три последние цифры суммы
999 999 999 999
999 1999 2999 999999 .S = + + + +
Решение. Имеем
( ) ( ) ( ) ( ) ( )
999 999 999 999
1000 0 999 1000 1 999 1000 2 999 1000 999 999 . 1S = + + + + + + + +
Так как для произвольных чисел a и b и произвольного
натурального числа n, существует целое число k такое, что
( ) ,
nn
a b kаb+ = +
то каждое слагаемое суммы представим в виде
( )
999
999
1000 999 1000 999 , , .k k n k n N + = +
Так как число слагаемых в сумме (1) равно 1 000, то
( )
999
999
1000 1000 999 1000 999 , .S m S m m N= + = +
Так как сумма S делится на 1 000, то три последние цифры: 0, 0, 0.
Ответ. 0, 0, 0.
17. Докажите, что число
396 396
32+
делится на 97.
Решение. Имеем
( ) ( )
( ) ( )
99 99
99 99
396 396 4 4
3 2 3 2 81 16 .+ = + = +
Существует натуральное число m такое, что
( ) ( ) ( ) ( ) ( )
99 99 99 99
81 16 81 16 81 16 97 .тт+ = + + =
.
Итак,
( ) ( )
99 99
81 16+
делится на 97,
а тогда и
396 396
32+
делится на 97.
18. Докажите, что число
57 23
57 23−
делится на 5.
Решение. Так как
( )
57
57
57 55 2=+
, то существует целое число k такое,
что
( )
57
57 57 57
55 2 55 2 57 55 2 .kk+ = + = +
Так как
( )
23
23
23 25 2=−
, то существует целое число m такое, что
( ) ( )
23 23
57 23
25 2 25 2 23 25 2 .mm− = + − = −
Итак,
18
( )
( )
( )
57 23 57 23 23 34
57 23 55 2 25 2 5 11 5 2 2 1 .
целое число
А k m k m= − = + − − = − + +
Число
А делится на 5, если число
34
21+
делится на 5.
Так как
34 17
2 1 4 1,+ = +
то существует целое число n такое, что
( )
17
4 1 4 1 5 .nn+ = + =
Итак, число
34
21+
делится на 5,
а тогда и число А делится на 5.
19. Докажите, что
1345
532)(
++
+=
nnn
nA
при любом
n
N делится на 37.
Решение. Так как
( )
( ) ( )
44
2 3 2 3 2 81 162
n
nn
n n n
= = =
, то
( ) ( )
( ) ( ) ( )
5 4 3 1 5 4 3 5
555
5 5 5
( ) 2 3 5 2 2 3 5 5 2 162 5 125
2 162 2 125 2 125 5 125
2 162 125 2 5 125 2 162 125 37 125 .
n
n n n n n n n
n n n n
n n n n n n
An
++
= + = + = + =
= − + + =
= − + + = − +
Существует натуральное число m такое, что
( ) ( ) ( ) ( ) ( )
162 125 162 125 162 125 37 .
n n n n
тт− = − − =
.
Итак,
5
( ) 2 37 37 125 , .
n
An т m N= +
Так как каждое слагаемое
()An
делится на 37, то
()An
делится на 37.
20. Докажите, что
( )
2 2 1
56
nn
Аn
++
=+
при любом
n
N делится на 31.
Решение. Так как
2 2 1 2 2 1
5 6 5 5 6 5 6 6 ,
n n n n n n+ + + +
+ = + − +
то
( )
( ) ( )
( )
( )
2 2 1 2 2 1 2
5 6 5 5 6 6 5 6 5 25 6 6 6 5 .
n n n n n n n n n
Аn
+ + + +
= + = + + − = + + −
Итак,
()An
делится на 31 при любом
n
N, если
( )
2
65
nn
−
делится
на 31 при любом
n
N. Так как
( ) ( )
2
6 5 36 5 ,
n n n n
− = −
то существует целое
число m такое, что
( )
( )
36 5 36 5 31
nn
mm− = − =
.
Итак,
( )
36 5 31
nn
m−=
делится на 31 при любом
n
N,
а тогда и
()An
делится на 31 при любом
n
N.
21. Докажите, что
( )
21
2 1 2 1 2 1
1 2 3 2 , , ,
n
n n n
Smгде m n N
+
+ + +
= + + + +
делится на
( )
2 1 .m +
Решение. Представим данную сумму в виде
( ) ( ) ( ) ( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
2 1 2 1 2 1 2 1
2 1 2 1
2 1 2 1 2 1
2 1 2 1 2 1
1 2 2 1 2 2 1 2 1 1 2 1
1 2 1 2 1 2
1 2 2 2 1 1 .
n n n n
nn
n n n
n n n
делится на m m делится на m m делится на m m m
S m m m m
S m m m m
+ + + +
++
+ + +
+ + +
+ = + + − = + + + = +
= + + + + + + + − +
= + + + − + + + +
19
Так как каждое слагаемое суммы делится на
2 1,m +
то и S делится
на
2 1.m +
Задачи на делимость
22. Натуральное число n такое, что числа
31n +
и
10 1n +
являются
квадратами натуральных чисел. Докажите, что число n делится на 8.
Решение. Так как по условию числа
31n +
и
10 1n +
являются
квадратами натуральных чисел, то существуют натуральные числа
k
и
m
такие, что
2
10 1nk+=
и
2
3 1 .nm+=
Так как
2
10 1nk+=
, то
k
– нечётное число. Тогда
k
можно
представить в виде
2 1,kp=+
где
,.k p N
Таким образом,
( )( ) ( ) ( )
22
10 1 10 1 10 1 1 10 4 1 5 2 1 .n k n k n k k n p p n p p+ = = − = − + = + = +
Так как
( )
5 2 1 ,n рр=+
то
n −
чётное число.
Так как
n −
чётное число и
2
3 1 ,nm+=
то
m
– нечётное число.
Тогда
m
можно представить в виде
2 1,mq=+
где
,.т q N
Так как
21kp=+
и
2 1,mq=+
то
( ) ( ) ( ) ( ) ( ) ( )
22
10 1 3 1 4 1 .n n m k m k m k q p q p+ − + = − = − + = − + +
Итак,
( ) ( ) ( ) ( ) ( ) ( )
10 1 3 1 4 1 7 4 1 .n n q p q p n q p q p+ − + = − + + = − + +
Получили, что
( ) ( ) ( )
7 4 1 . 1n q p q p= − + +
Возможны следующие случаи.
1) Если
p
и
q
одной чётности, то
( )
qp−
является чётным числом и
делится на 2. Тогда из (1) следует, что
n
делится на 8.
2) Если
p
и
q
разной чётности, то
( )
1qp++
является чётным
числом и делится на 2. Тогда из (1) следует, что
n
делится на 8.
Доказали, что
n
делится на 8.
23. Найдите цифры х, у, z, при которых число
xyzxyz
делится на 7,
11, 13.
Решение. Искомое число запишем в виде
( ) ( ) ( ) ( )( )
5 4 3 2
5 2 4 3 3 2
10 10 10 10 10
10 10 10 10 10 1 10 1 10 10 .
nxу z x y z
x у z х у z
= + + + + + =
= + + + + + = + + +
Итак,
( )( )
32
10 1 10 10 .n х у z= + + +
Так как
3
10 1 7 11 13,+ =
то число
xyzxyz
делится на 7, 11, 13 при
любых значениях х, у, z (
,,x y z −
цифры числа), удовлетворяющих
условиям
1 9, 0 9,xy
0 9.z
Ответ.
1 9, 0 9, 0 9.x y z
20
24. Найдите цифры х, у при которых число
7 8 6xy
делится на 88.
Решение. Натуральное число
7 8 6a x y=
делится на 88 тогда и
только тогда, когда оно делится на 8 и на 11.
1. Число а делится на 8 тогда и только тогда, когда число
86by=
делится на 8. Перебирая все значения у, если
0 9,y
находим, что
число
b
делится 8, если у принимает одно из значений: 1, 5, 9.
2. Число а делится на 11 тогда и только тогда, когда делится на 11
число
( )
7 8 6 21 .c x y c x y= + + − − = − +
Так как х, у цифры числа, то
0 18.xy +
Тогда число
( )
21c x y= − +
делится на 11, если
10xy+=
и
1;5;9 .y
Из уравнения
10xy+=
, где
1;5; 9 ,y
находим: если
1,y =
то
9;x =
если
5,y =
то
5;x =
если
9;y =
то
1.x =
Ответ. 79 816, 75 856, 71 896.
25. Найдите цифры х, у при которых число
1 2345xy
делится на 31.
Решение. 1. Искомое число запишем в виде
6 5 4 3 2
10 10 10 10 2 10 3 10 4 5nx у= + + + + + +
, где
1 9, 0 9.xy
Если числа
6 5 4 3 2
10 ,10 ,10 ,10 ,10
разделить на 31, то получим
соответственно остатки 2; 25; 18; 8; 7. Тогда найдутся числа
1 2 3 4 5
, , , ,m m m m m N
такие, что
6 5 4
1 2 3
32
45
10 31 2 ; 10 31 25; 10 31 18 ;
10 2 31 8 2; 10 3 31 7 3.
x m x m у m у
mm
= + = + = +
= + = +
Число n запишем в виде
( ) ( )
( ) ( ) ( )
1 2 3 4 5
1 2 3 4 5
31 2 31 25 31 18 31 8 2 31 7 3 40 5
31 2 25 18 16 21 45
31 2 18 31 3 14 31 3 2 9 7 .
mN
n m x m m у m m
m m m m m x у
mxу m x у
= + + + + + + + + + + + =
= + + + + + + + + + + =
= + + + + = + + + +
Итак,
( ) ( )
31 3 2 9 7 .n m x y= + + + +
2. Число n делится на 31, тогда и только тогда, когда число
97k x y= + +
делится на 31.
Оценим число k.
Так как
1 9, 0 9,xy
то
1 9 0 7 9 7 9 9 9 7 8 9 7 97 8 97.x y x y k+ + + + + + + +
Итак,
8 97.k
Из двойного неравенства
8 97,k
следует: так как число k кратно
31, то оно принимает хотя бы одно из значений: 31, 62, 93.
21
3. Найдём значения х и у из уравнения
97k x y= + +
, если
31; 62;93 ,k
1 9, 0 9.xy
1) Если
31,k =
то
9 7 31 24 9 .x y x у+ + = = −
Решение последнего
уравнения – это
6, 2.xy==
Искомое число
6122345
.
2) Если
62,k =
то
9 7 62 55 9 .x y x у+ + = = −
Решение последнего
уравнения – это
1, 6.xy==
Искомое число
1162345
.
3) Если
93,k =
то
9 7 93 86 9 .x y x у+ + = = −
Решение последнего
уравнения – это
5, 9.xy==
Искомое число
5192345
.
Ответ.
6122345
,
1162345
,
5192345
.
26. Докажите, что число
1251 1251
11 1144 44
делится на 37.
Решение. Имеем
( )
1251 1251
1251 1251 1251 1251 1251
11 1144 44 11 11 10 44 44 11 11 10 4 .= + = +
Докажем, что
1251
11 11
делится на 37.
Очевидно,
111 3 37=
и
1251 3 417.=
Тогда
( )
1248 1245 3
1251
1248 1245 3
1251
11 11 111 10 111 10 111 10 111
11 11 3 37 10 10 10 1 .
= + + + +
= + + + +
Итак,
( )
1248 1245 3
1251 1251
11 1144 44 3 37 10 10 10 1 .= + + + +
Из последнего равенства следует, что данное число делится на 37.
27. Найдите наименьшее натуральное число
n
при котором число
1122 211
n
А =
делится на В=9 999 999.
Решение. 1. Имеем
( )
( ) ( )
( ) ( )
( )
3 2 1 3 2
3 2 1 3 2 1 3 2
3 2 1 3 2 1 3 2
2 1 1
1122 211 10 10 2 10 10 10 10 10 1
10 10 10 10 10 10 10 10 10 10 10 1
10 10 10 10 10 10 10 10 10 10 10 1
10 10 10 10 10 1 10
n n n n
n
n n n n n n
n n n n n n
n n n
A
+ + +
+ + + +
+ + + +
+−
= = + + + + + + + + =
= + + + + + + + + + + + + + =
= + + + + + + + + + + + + + =
= + + + + + +
( )
( )
1 3 2
11
2
10 10 10 10 1
101 10 10 10 10 1 101 11 1.
nn
n n n
n
+
+−
+
+ + + + + + =
= + + + + + =
Итак,
2
101 11 11.
n
A
+
=
22
2. Легко проверить, что число
9 1111111В =
не делится на 101. Тогда
число
2
101 11 11
n
A
+
=
делится на В, если
2
11 11
n
а
+
=
делится на В. Так как В
делится на 9, то а должно делится на 9 и делится на 1 111 111.
Если
2
11 11
n
а
+
=
делится на 9, то число цифр (единиц) в числе а
кратно 9. Тогда существуют натуральное число
k
такое, что
2 9 .nk+=
Так как а делится на 1 111 111, то перепишем число а в виде
9 7 9 14 9 7
29
11 11 1111111 10 1111111 10 1111111 10 .
k k k т
nk
а
− − −
+=
= = + + + + +
Наименьшее значение числа а, при котором число а делится на
1 111 111, находим из уравнения
9 7 0 9 7 .k т k т− = =
Наименьшим значением т, которое удовлетворяет уравнению
9 7 ,k т=
является
9.т =
Тогда
9 63.k =
Так как
2 9 ,nk+=
то
2 63 61.nn+ = =
Ответ.
61.n =
28. Докажите, что существует натуральное число, записанное
одними единицами, которое делится на 271.
Решение. Рассмотрим 272 числа:
272
1, 11, 111, , 11 11.
единицы
Число
остатков при делении на 271, равно 271, а чисел 272. Тогда хотя бы два
числа при делении на 271 имеют равные остатки. Это означает, что
разность чисел с одинаковыми остатками делится на 271.
Пусть числа
11 11
n единиц
и
11 11, ,
k единиц
nk
имеют одинаковые остатки.
Рассмотрим разность
11 11 11 11 11 1100 00 11 11 10 .
k
n единиц k единиц n k единиц n k единиц
k нулей
а а а
−−
= − = =
Так как число
11 11 10
k
nkединиц
а
−
=
делится на число 271, а число
10
k
не
делится на 271, то число
11 11
nkединиц−
делится на 271. Число
11 11
nkединиц−
удовлетворяет условию задачи. Отметим:
271 41 11111.=
29. Если числа 4 118 и 3 469 разделить на одно и то же число, то
получим соответственно остатки 14 и 11. Найдите этот делитель.
Решение. Пусть d искомый делитель. Так как остатки равны 14 и
11, то
14.d
Если d делитель чисел 4 118 и 3 469, то существуют целые
числа х и у такие, что
23
33
4118 14 4104 2 3 19 38 9 12 ;
3469 11 3458 2 7 13 19 38 7 13 .
d x d x d x d x
d x d y d y d y
= + = = =
= + = = =
Так как
38 9 12 38 7 13,dx и d y = =
и
14,d
то
19, 38 .d
Ответ.
19, 38 .d
30. Число при делении на 1970 и 1971 даёт остаток, равный 69.
Найдите остаток, который даёт при делении на 15 это число.
Решение. 1) Если число х при делении на 1970 даёт остаток, равный
69, то
69х −
делится на
1970 2 5 197=
, а тогда
69х −
делится на 5.
2) Если число х при делении на 1971 даёт остаток, равный 69, то
69х −
делится на
1971 3 9 73=
, а тогда
69х −
делится на 3.
Так как 5 и 3 простые числа, то из 1) и 2) следует, что
69х −
делится на
15 3 5.=
Тогда
( ) ( )
69 9 60 9 69 15 4.х х х х− = − − − = − +
Так как
69х −
делится на
15
и
( )
9 69 15 4,хх− = − +
то
9х −
делится
на 15. Тогда число х при делении на 15 даёт остаток, равный 9.
Ответ. 9.
31. Докажите, что натуральное число имеет нечётное число
делителей тогда и только тогда, когда оно является точным квадратом.
Решение. Если d делитель числа х, то
xd
также делитель числа х.
Делители числа х, разбиваем на пары
( )
;,d x d
где
.x x d
Если
2
,x у=
то ровно в одной паре
( )
2
;у у у
делители совпадают, это означает, что в
этом случае число делителей нечётно.
Обратно, если число делителей числа х нечётно, то в одной паре
делителей
( )
;d x d
делители совпадают, то есть
2
d x d хd= =
.
Доказали: натуральное число имеет нечётное число делителей
тогда и только тогда, когда оно является точным квадратом.
32. Натуральные числа а и b имеют ровно по 57 натуральных
делителей (считая 1 и само число). Может ли произведение этих чисел
иметь 300 делителей.
Решение. Так как числа а и b имеют по нечётному числу
натуральных делителей, то они являются точными квадратами. Тогда их
произведение аb тоже точный квадрат, а это означает, что число
делителей аb должно быть нечётным. Поэтому аb не может иметь 300
делителей.
33. Докажите, что
1500!
делится на
149
11 .
24
Решение. По определению
1500! −
это произведение чисел от 1 до
1500, то есть
1500! 1 2 3 1499 1500.=
Обозначение:
.х целая часть числа х−
В произведении
1500! 1 2 3 1499 1500=
число чисел, делящихся
на 11, равно
1500:11 136,n ==
делящихся на
2
11 121=
, равно
1500:121 12,k ==
делящихся на
3
11 1331=
, равно
1500:1331 1.m ==
Следовательно, число
1500!
делится на
136 12 1 149
11 11 .
++
=
Отметим:
число
1500!
делится на
11 ,
l
где целое число l
удовлетворяет условию
0 149l
и не делится на
11 ,
m
если
150.m
34. Найдите наибольшее натуральное число n, для которого число
1111! делится на
.
n
n
Решение. Имеем
( )
1110 30 37 1111 36 31 1116. 1= =
1. Докажем, что число
1111! не делится на
37
37 .
Так как число 37 простое, то среди чисел
1, 2, , 30 37,1111
(2)
всего 30 чисел кратных 37. Это числа:
1 37, 2 37, , 30 37
(следует из
(1)). Поэтому число
1111! делится на
30
37 ,
но не делится на
37
37 .
2. Докажем, что число
1111! делится на
36
36 .
1) Среди чисел
(2) имеется 30 чисел вида
36 ,k
где
1, 2, , 30.k =
Это числа:
1 36, 2 36, , 30 36 1080. =
2) Из чисел
(2) можно получить более 6 чисел, которые делятся на
36, например, такие 7 чисел:
2 18, 3 12, 4 9, 6 24, 8 72, 14 54, 16 27.
Итак, из чисел
1, 2, ,1080,1081, ,1111
. можно получить более 36
чисел, которые делятся на 36, поэтому число
1111! делится на
36
36 .
Так как число
1111! не делится на
37
37 ,
то искомое число
36.n =
Ответ 36.
35. Сумма квадратов двух целых чисел делится на 7, тогда и только
тогда когда каждое число делится на 7.
Решение. Каждое из чисел
,ab
при делении на 7 может давать
остатки
0, 1, 2, 3.
Тогда
7,an
=+
7,bm
=+
где
,,n m N
, 0, 1, 2, 3.
=
Найдём
( ) ( )
( ) ( )
22
2 2 2 2 2 2
7 7 7 7 2 7 2 .
kN
a b n m n n m m
+ = + + + = + + + + +
Так как
22
7 2 7 2 ,n n m m k
+ + + =
,kN
то
( )
( )
2 2 2 2
7 . 1a b k
+ = + +
25
1. Если а и
b
делятся на 7, то
0
=
и
0.
=
Откуда следует, что
22
0.
+=
Тогда из (1) следует, что
22
ab+
делится на 7.
Итак, если оба числа делятся на 7, то сумма квадратов двух целых
чисел делится на 7.
2. Из (1) следует, если
22
ab+
делится на 7, то
( )
22
0,
02
0.
=
+ =
=
Если
22
ab+
делится на 7, то из (2) следует, что
a
и
b
делятся на 7.
36.
Докажите, что если сумма натуральных чисел делится на 6, то
и сумма пятых степеней этих же чисел делится на 6.
Решение. Пусть при делении числа а на 6 остаток равен
.
Тогда
6,аk
=+
где
, 0,1, 2, 3, 4, 5kN
=
и
( )
5
5
6.аk
=+
Существует натуральное число m такое, что
( )
5
5
6 6 ,а k а m
= + = +
где
,mN
0,1, 2, 3, 4, 5.
=
Докажем, что числа а и
5
a
при делении на 6 имеют одинаковые
остатки. Имеем
( )
5 5 5
5 5 5
0 6 0 0, 1 6 0 1, 2 6 5 2,
3 6 40 3, 4 6 170 4, 5 6 520 5. 1
= + = + = +
= + = + = +
Из (1) следует: если при делении на 6 число
, 1, 2, , ,
i
a N i n=
имеет остаток, равный
,
i
то и число
5
a
делении на 6 имеют остаток,
равный
.
i
Тогда, если сумма
( )
1 2 1
,
nn
а a а а
−
+ + + +
где
, 1, 2, , ,
i
a N i n=
делится на 6, то и сумма пятых степеней этих же
чисел делится на 6, так как сумма остатков в обоих случаях равна нулю.
Таким образом, доказали: если сумма натуральных чисел делится
на 6, то и сумма пятых степеней этих же чисел делится на 6.
37. Докажите, что число
2
3 8 1
n
n−−
при любом
n
N делится на 64.
Решение. Воспользуемся формулой
( )
( )
( )
1 2 3
1 1 1 . 1
n n n n
a a a a a a
− − −
− = − + + + + +
Имеем
26
( ) ( ) ( )
( )
( ) ( ) ( )
( )
2 1 2 1 0
1 2 1 1 2 1
3 1 8 9 1 8 (9 1) 9 9 9 9 8
8 9 9 9 1 1 1 1 1 8 9 1 9 1 9 1 .
n n n n n
n n n n
n слагаемых
n слагаемых
А n n n
−−
− − − −
= − − = − − = − + + + + − =
= + + + + − + + + + = − + − + + −
Так как каждое слагаемое последней суммы при любом
n
N
делится на 8, то и
2
3 1 8
n
n−−
при любом
n
N делится на 64.
38. Найдите значение
nN
,
при котором
10 5 2 3
n n n n
А = + − −
делится на 56.
Решение. 1. Пусть
2 , .n k k N=
Замечание. Для произвольных чисел a и b, где
0,ab
и
произвольного натурального числа n существует целое число k такое,
что
( )
.
nn
a b k аb− = −
Тогда
( )
аb−
является делителем числа
( )
.
nn
ab−
а) Докажем, что А делится на 7. Имеем
( ) ( )
2 2 2 2 2 2 2 2
10 5 2 3 10 3 5 2 .
k k k k k k k k
А = + − − = − + −
Из замечания следует: число
( )
22
10 3
kk
−
делится на
10 3 7,−=
число
( ) ( )
22
52
kk
−
делится на
25 4 7 3.− =
Итак, при
2,n k k N=
, число А делится на 7.
б) Докажем, что А делится на 8. Имеем
( ) ( )
2 2 2 2
10 2 5 3 .
k k k k
А = − + −
Из замечания следует: число
( )
22
10 2
kk
−
делится на
10 2 8,−=
число
( ) ( )
22
53
kk
−
делится на
25 9 8 2.− =
Итак, при
2,n k k N=
, число А делится на 8.
Так как при
2,n k k N=
, число А делится на 7 и на 8, то при
2,n k k N=
, число А делится на 56.
2. Пусть
2 1, .n k k N= +
Имеем
( ) ( )
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
10 5 2 3 10 3 5 2 .
k k k k k k k k
А
+ + + + + + + +
= + − − = − + −
а) Из замечания следует: число
2 1 2 1
10 3
kk++
−
делится на
10 3 7.−=
б) Имеем
( )
2 1 2 1 2 2 2 2 2 2 2
5 2 5 5 2 2 3 2 3 2 5 5 2 3 2 .
k k k k k k k k k++
− = − − + = − +
Итак,
( )
2 1 2 1 2 2 2
5 2 5 5 2 3 2 .
k k k k k++
− = − +
27
Выше было доказано, что
22
52
kk
−
делится на 7, но
2
32
k
не делится
на 7.
Тогда
( ) ( )
2 1 2 1 2 2 2
10 3 5 5 2 3 2
k k k k k
А
++
= − + − +
не делится на 7, а значит
и не делится на 56, если
2 1, .n k k N= +
Ответ.
2,n k k N=
.
39. Докажите: если натуральное число
3n
и нечётно, то
( )
12 8 4
99А n n n n= − − +
делится на 256.
Решение. Разложим
( )
Аn
на множители:
( ) ( ) ( ) ( )
( )( ) ( )( )( )( )( )
12 8 4 12 8 4 8 4 4
4 8 2 2 2 2 4
9 9 9 9 9 9
9 1 3 3 1 1 1 .
А n n n n n n n n n
n n n n n n n
= − − + = − − − = − − − =
= − − = − + − + +
Итак,
( )
( )( )( )( )( )
2 2 2 2 4
3 3 1 1 1 .А n n n n n n= − + − + +
Так как число
n
– нечётное натуральное число, то
2 1,nk=+
где
.kN
Тогда для любого
kN
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )( )( )( )
( )
( )
( )( )
( )
( )
( )
( )
2 2 2 2 4
4
2 2 2 2
4
6 2 2 2
2 1 3 2 1 3 2 1 1 2 1 1 2 1 1
4 4 2 4 4 4 4 4 4 4 2 2 1 1
2 2 2 1 1 1 2 2 1 2 1 1 .
А k k k k k
k k k k k k k k k
k k k k k k k k k
= + − + + + − + + + + =
= + − + + + + + + + =
= + − + + + + + + +
Числа
( )
,1kk+
являются последовательными натуральными
числами, поэтому их произведение делится на 2. Число
( )
( )
4
2 1 1k ++
является чётным числом, поэтому оно делится на 2.
Итак, если
3n
и нечётно, то
( )
Аn
делится на
8
2 256.=
40. Докажите, что число
6 5 4 3 2
3 5 15 4 12А n n n n n n= − − + + −
при
любом
n
N делится на 720.
Решение. Разложим число А на множители:
( ) ( ) ( )
( )
( )
( )
( )
( )( )
( )( )( ) ( )( )
6 5 4 3 2 4 2
4 2 2 2
3 5 15 4 12 3 5 3 4 3
3 5 4 3 1 4
3 2 1 1 2 .
А n n n n n n n n n n n n
n n n n n n n
n n n n n n
= − − + + − = − − − + − =
= − − + = − − − =
= − − − + +
Итак,
( )( )( ) ( )( )
3 2 1 1 2 .А n n n n n n= − − − + +
Число А является произведением шести последовательных
натуральных чисел. Поэтому число А делится на
6! 720.=
41.
Докажите, что при любом
n
N число
( ) ( )
29 20 21 30 50
nn
− + −
делится на 30450.
28
Решение. 1. Обозначим
( ) ( ) ( )
29 20 21 30 50.
nn
fn= − + −
Пусть
( ) ( ) ( )
1.n f n f n
= + −
Тогда
( ) ( ) ( ) ( ) ( )
( )
( ) ( )
( )
( ) ( ) ( ) ( ) ( ) ( ) ( )
( )
11
11
1 29 20 20 21 30 30
29 20 1 20 1 21 30 30 1 10 29 21 2 1 3 .
n n n n
n n n n n
nn
n f n f n
++
++
= + − = − − − + − =
= − + + − = − +
Итак,
( ) ( ) ( )
( )
( )
1
10 29 21 2 1 3 . 1
nn
nn
n
+
= − +
Из (1) следует, что
( )
n
, где
1,n
делится на
29 21 10 6090. =
Так как
( ) ( ) ( )
1,n f n f n
= + −
то
( ) ( ) ( )
1.f n n f n
+ = +
Таким образом,
( ) ( ) ( )
( )
( )
1
1 10 29 21 2 1 3 .
nn
nn
f n f n
+
+ = − + +
2. Рассмотрим
( )
.fn
а) Так как
( ) ( ) ( )
29 20 21 30 50,
nn
fn= − + −
то
( )
1 0.f =
б) Так как
( ) ( ) ( )
1f n n f n
+ = +
и
( )
1 0,f =
то
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
2 1 , 3 1 2 , , 1 2 1 , 2.f f f n n где n
= = + = + + + −
Очевидно, что
( ) ( ) ( )
( )
1
10 29 21 2 1 3 , ,
nn
nn
n где n N
+
= − +
делится на
29 21 10 6090. =
Тогда
( ) ( ) ( ) ( )
1 2 1 ,f n n
= + + + −
если
1,n
делится на
29 21 10 6090. =
3. Число
( )
fn
, если
1,n
делится на
5 6090 30 450,=
, если число
( ) ( ) ( )
( )
1
10 29 21 2 1 3 , 1,
nn
nn
n где n
+
= − +
делится на 5. Число
( )
n
, где
1,n
делится на5, если
( ) ( )
1
2 1 3
n
nn
gn
+
= − +
, где
1,n
делится на 5.
а) Пусть
2.nk=
Тогда
( ) ( ) ( )
( ) ( )
( ) ( ) ( )
21
2 2 2 2
2 2 1 3 2 3 2 2 9 4 .
kk
k k k
kk
g k g k g k
+
= − + = − = −
Так как существует натуральное число m такое, что
( )
9 4 9 4 5 ,
kk
тт− = − =
то
( )
2 9 4
kk
gk=−
делится на 5.
б) Пусть
2 1.nk=+
Тогда
( ) ( ) ( )
22
2 1 2 1 2 1 2 1
2 1 2 1 3 2 1 3 2 .
k
k k k k
g k g k
+
+ + + +
+ = − + + = +
Так как существует натуральное число m такое, что
( )
2 1 2 1
3 2 3 2 5 ,
kk
тт
++
+ = + =
то
( )
2 1 2 1
2 1 3 2
kk
gk
++
+ = +
делится на 5.
Доказали, что число
( ) ( )
1
2 1 3
n
nn
gn
+
= − +
делится на 5, если
1.n
Тогда исходное число делится на
30450.
42. Найдите натуральные значения n, при которых число
( ) ( )
1
( ) 1 1
n
n
а n n n
+
= + +
делится на 3.
29
Решение. Любое натуральном число
n
можно представить
в виде
3,nk
=+
где
0, 0,1,2.k
=
1. Если
3,nk=
где
1,k
то
()аn
принимает вид
( ) ( )
3 1 3
3 3 1 ,
kk
kk
+
++
одно слагаемое, которого делится на 3, а другое слагаемое не делится на
3, поэтому сумма не делится на три.
2. Если
3 1,nk=+
где
0,k
то
()аn
принимает вид
( ) ( ) ( ) ( )
( )
31
3 2 3 1 3 2
3 1 3 2 3 1 3 1 1 .
k
k k k
k k k k
+
+ + +
+ + + = + + + −
Существуют целые числа
12
,тт
такие, что
( ) ( ) ( )
( )
( ) ( )
31
3 2 3 2 3 1
12
3 1 3 1 , 3 1 1 3 1 1 .
k
k k k
kkт k k т
+
+ + +
+ = + + − = + + −
Таким образом, имеем
( ) ( ) ( ) ( )
( )
( ) ( ) ( ) ( )
( )
( )
( )
31
3 2 3 1 3 2
3 2 3 1 3 1
12
3 1 3 2 3 1 3 1 1
3 1 3 1 1 3 1 1 1 .
k
k k k
k k k
k k k k
k т k n k m k m
+
+ + +
+ + +
+ + + = + + + − =
= + + + + − = + + + + −
Так как k,
12
,mm−
целые числа, то
( )
3 1 2
31т k т k т= + + −
целое
число. Итак,
( ) ( ) ( )
( )
3 2 3 1 3 1
3
3 1 3 2 3 1 1 ,
k k k
kkт
+ + +
+ + + = + + −
где
3
т −
целое
число. Число
( ) ( )
3 2 3 1
3 1 3 2
kk
kk
++
+ + +
делится на 3, если
( )
( )
( )
3 1 3 1
1 1 0 1 1 2 , .
kk
k m m N
++
+ − = − = − =
Итак,
( )
аn
делится на 3, если
2
3 1 6 1.
km
n k n m
=
= + = +
3. Если
3 2, 0,n k k= +
то
( )
аn
принимает вид
( ) ( )
3 3 3 2
3 2 3 3 ,
kk
kk
++
+ + +
одно слагаемое, которого делится на 3, а другое слагаемое не делится на
3, поэтому сумма не делится на три.
Ответ.
6 1, .n m m N= +
Задачи на НОД и НОК
43. Найдите два натуральных числа, сумма которых равна 344, а
общий наибольший делитель равен 43.
Решение. Пусть a и b являются искомыми числами. Так как, по
условию задачи, НОД (а; b)=43, то существуют взаимно простые
натуральные числа х и у такие, что
43 , 43 .а х b y==
Тогда
( )
344 43 344 8.ab х у х у+ = + = + =
Уравнению
8ху+=
удовлетворяют пары взаимно простых чисел
( ) ( ) ( ) ( )
1; 7 , 3; 5 , 5; 3 , 7;1
. Тогда искомыми числами являются числа: 43 и
301, 129 и 215.
Ответ. 43 и 301, 129 и 215.
30
44. Найдите наибольший общий делитель натуральных чисел m и n,
если он увеличивается в 15 раз при увеличении числа m на 10.
Решение. Пусть НОД(m , n)=d. Тогда НОД(m+10, n)=15d.
Воспользуемся следующим: если целое число делится на
произведение натуральных чисел, то оно делится на каждый
сомножитель.
Отметим:
15 5 3 .dd=
1.Так как НОД(m+10, n)=15d, то 5 и
d
являются делителями чисел
m+10 и n. Так как НОД(m , n)=d, то
d
является делителем чисел m и n.
Тогда
а) m+10 делится на 5 и так как 10 делится на 5, то m
делится на 5;
б) n делится на 5.
Из а) и б) следует, что 5 делитель чисел m и n. Так как
d
наибольший общий делитель чисел m и n, то 5 делитель
d
, то есть
d
кратно 5.
в) m+10 делится на
d
,
и так как m
делится на
d
, то 10 делится на
d
.
И так как
d
кратно 5, то
5;10 .d
2. Пусть
5;10 .d
1) Если
5,d =
то НОД(m, n)=5 и НОД(m+10, n)=75. Тогда, например,
10 75 65mm+ = =
и
75n =
. Итак,
5d =
удовлетворяет условию задачи.
2) Если
10,d =
то НОД(m, n)=10 и НОД(m+10, n)=150. Тогда,
например,
10 150 140mm+ = =
и
150.n =
Итак,
10d =
удовлетворяет
условию задачи.
Ответ.
5 или 10.
45. Различные натуральные числа m и n таковы, что
НОД (m, n)+НОК (m, n) =m+n.
Докажите, что одно из чисел является делителем другого.
Решение. Пусть НОД (m, n)=d. Тогда существуют взаимно простые
натуральные числа х и у таковы, что
,.m dx n dy==
Так как
( ) ( )
, , ,НОД m n НОК m n m n =
то
( )
,.НОК m n dxy=
Тогда
( ) ( )
( ) ( ) ( ) ( )( )
0
,,
1 1 1 1 1 1 0.
d
НОД m n НОК m n m n d dxy dx dy
d xy d x y xy x y х у х х у
+ = + + = +
+ = + + = + − = − − − =
Рассмотрим уравнение
( )( )
1 1 0.ху− − =
Если
1 0 1,хх− = =
то
.m dx m d= =
Тогда, так как
,n dy=
то
.n my=
Из равенства
n my=
следует, что m является делителем числа n.
31
Если
1 0 1,уу− = =
то
.nd=
Тогда, так как
,m dx=
то
.mnх=
Из
равенства
mnх=
следует, что n является делителем числа m.
46. Пусть
1 2 15
, , ,а а а −
натуральные числа, сумма которых равна
2 737. Какое наибольшее значение может принимать их наибольший
общий делитель?
Решение. Если
( )
1 2 15
, , , ,d НОД а а а=
то существуют взаимно
простые натуральные числа
1, 1 15
i
ni
такие, что
.
ii
а dn=
Тогда
( )
( )
1 2 15
1 2 15 1 2 15
1 2 15
1
2737
182,4 6 .
15
i
n
а а а
а а а d n n n d
n n n
dd
+ + +
+ + + = + + + =
+ + +
Так как
( )
1 2 15 1 2 15
а а а d n n n+ + + = + + +
, то
d
является
делителем числа
1 2 15
2737 7 17 23.а а а+ + + = =
Итак,
d
является
делителем числа
7 17 23,
при этом
182.d
Наибольшим значением
d
(
182d
)
является
7 23 161.dd= =
Например,
161d =
является наибольшим общим делителем чисел:
1 13 14 15
161, , 161, 322, 322,а а а а= = = =
сумма которых равна 2 737.
Ответ. 161.
47. Пусть НОК(a, b)=504 и НОК(a, с)=378, где a, b, c натуральные
числа. Найдите НОК(b, с).
Решение. Разложим числа 504 и 378 на простые множители:
3 2 3
504 2 3 7, 378 2 3 7.= =
Так как
( )
32
, 2 3 7НОК a b =
и
( )
3
, 2 3 7,НОК a с =
то найдутся
целые неотрицательные числа
, , ,
i i i
n m k
где
1, 2, 3i =
, таковы, что
3 3 3
1 1 1 2 2 2
2 3 7 , 2 3 7 , 2 3 7 .
n m k
n m k n m k
a b c= = =
Из определения наименьшего общего кратного следует:
( )
1 2 1 2 1 2
max , max , max ,
, 2 3 7 ,
n n m m k k
НОК a b =
( )
( )
1 3 1 3 1 3
2 3 2 3 2 3
max , max , max ,
max , max , max ,
, 2 3 7 ,
, 2 3 7 .
n n m m k k
n n m m k k
НОК a c
НОК b c
=
=
Для того чтобы найти НОК(b, с) надо найти
2 3 2 3 2 3
max , , max , , max , .n n m m k k
Имеем
32
( )
( )
1 2 1 2 1 2
12
max , max , max ,
12
32
12
max , 3,
, 2 3 7 ,
max , 2,
, 2 3 7;
max , 1.
n n m m k k
nn
НОК a b
mm
НОК a b
kk
=
=
=
=
=
( )
( )
1 3 1 3 1 3
13
max , max , max ,
13
3
13
max , 1,
, 2 3 7 ,
max , 3,
, 2 3 7;
max , 1.
n n m m k k
nn
НОК a с
mm
НОК a с
kk
=
=
=
=
=
1. Найдём
23
max , .nn
а) Так как
13
max , 1nn =
, то
1
0,1 ,n
3
0,1 .n
б)
Так как
12
max , 3nn =
и
1
0,1 ,n
то
2
3.n =
в) Так как
2
3,n =
и
3
0,1 ,n
то
23
max , 3.nn=
2. Найдём
23
max , .mm
а) Так как
12
max , 2mm =
, то
1
0,1, 2m
и
2
0,1, 2m
.
б) Так как
13
max , 3mm =
и
1
0,1, 2m
, то
3
3m =
.
в) Так как
3
3m =
и
2
0,1, 2m
, то
23
max , 3.mm=
3. Найдём
23
max , .kk
Так как
12
max , 1kk =
и
13
max , 1,kk =
то
1
0,1k
,
2
0,1k
и
3
0,1 .k
Тогда имеется две возможности для значения
23
max , .kk
1) Если хотя бы одно из значений
2
k
или
3
k
равно 1, то
23
max , 1.kk=
2) Если
23
0,kk==
то
23
max , 0kk=
.
Имеем
( )
2 3 2 3 2 3
max , max , max ,
, 2 3 7 .
n n m m k k
НОК b c =
1) Если
23
max , 3,nn=
23
max , 3,mm=
23
max , 1kk=
, то
( ) ( )
33
, 2 3 7 , 1512;НОК b c НОК b c= =
2) Если
23
max , 3,nn=
23
max , 3,mm=
23
max , 0kk=
, то
( ) ( )
3 3 0
, 2 3 7 , 216.НОК b c НОК b c= =
Ответ.
1 512, 216.
48. Пусть наибольший общий делитель натуральных чисел
m
и
n
равен единице. Какое наибольшее значение может принимать НОД
чисел
1000mn+
и
990nm+
?
Решение. Пусть
1000 ,а m n=+
990b n m=+
и
( )
,.d НОД a b=
33
Выразим
m
и
n
через a и b из системы
1000 , 990 990 990 1000 , 990 989999 ,
990 ; 990 ; 990 ;
990 989999 ,
989 999 989999 989999 990 ;
990 989999 ,
989 999 990 989999 990 ;
990 989999 ,
99000
а m n а m n а b n
b n m b n m b n m
а b n
b n m
а b n
bb аm
а b n
= + = + − =
= + = + = +
−=
= +
−=
+ − =
−=
990 989999 ,
0 990 989999 990 ; 1000 989999 .
а b n
b а m b а m
−=
− = − =
Итак,
( )
990 989999 , 1000 989999 . 1а b n b а m− = − =
Так как
d
является наибольшим общим делителем чисел a и b,
то
d
является делителем чисел
m
и n (следует из (1)). Так как числа
m
и
n взаимно простые числа, то
d
является делителем числа 989 999.
Покажем, что найдутся взаимно простые числа
m
и
n
такие, что
989999.d =
Пусть, например,
999 27 37, 989 23 43.mn= = = =
Очевидно,
m
и
n взаимно простые числа. Тогда
999 1000 989 989999аа= + =
и
989 990 999 989999.bb= + =
Итак,
( )
, 989999.НОД a b =
Ответ.
989 999.
49. Пусть НОД(m, n)=d и НОК (m, n) =q, где
,,qd
m и n
натуральные числа. Найдите наименьшее значение числа
qd
, если
выполнено условие
5 8 14.mn−=
Решение. Так как НОД(m, n)=d, то существуют взаимно простые
натуральные числа х и у такие, что
,.m dx n dy==
Так как
( ) ( )
, , ,НОД m n НОК m n m n =
то
( )
0
, : .
d
НОК m n dxy q dxy q d xy
= = =
Надо найти значения х и у, при которых
xy q d=
принимает
наименьшее значение, если
5 8 14.mn−=
Так как
,,m dx n dy==
то
( )
0
5 8 14 5 8 14 5 8 14 5 8 14 .
d
m n dx dy d x y x y d
− = − = − = − =
Так как
х и у натуральные числа, то из уравнения
5 8 14x y d−=
следует, что
1; 2; 7;14d
(14 делится на
d
)
34
Найдём значения
xy
, если х и у взаимно простые натуральные числа
и они являются решением уравнения
5 8 14 8 5 14 5 ,x y d x y d− = = +
где
1; 2; 7;14d
.
Отметим: наименьшее значение
xy
является искомым значением.
Так как
1х =
и
1у =
не являются решением уравнения
5 8 14x y d−=
(в
этом случае, левая часть уравнения меньше нуля, а правая часть больше
нуля), то
2.xy
1) Если
14,d =
то уравнение (1) принимает вид
( )
81
8 5 1 5 5
5
y
x y x
+
= + =
. Уравнение (5) имеет целые решения,
если
81у +
делится на 5. Тогда
3у =
является наименьшим значением,
при котором х принимает целое число, равное 5
.
Итак, если
14,d =
то
3у =
и
5.х =
Тогда
15 : 15.xу q d= =
2) Если
7,d =
то уравнение (1) принимает вид
( )
41
8 5 2 5 2 4
5
y
x y x
+
= + =
. Уравнение (4) имеет целые решения,
если
41у +
делится на 5. Тогда
1у =
является наименьшим значением,
при котором х принимает целое число, равное 2. Итак, если
7,d =
то
1у =
и
2х =
(
1у =
и
2х =−
взаимно простые натуральные числа). Тогда
2 : 2.xу q d= =
Так как
2,xy
то наименьшим значением
:qd
является найденное
значение
: 2.qd=
Ответ.
2.qd=
Задачи на сравнение чисел по модулю
Воспользуемся следующим: Если
( )
mod ,a k n
где k целое число,
то k является остатком от деления числа а на n.
Если
( )
moda b n
и
( )
mod ,c d n
то
1)
( )( )
mod ,a c b d n+ +
2)
( )( )
mod ;a c b d n
если
( )
mod , ,a b n k N
то
( )
mod .
kk
a b n
50. Найдите остаток от деления числа
162
6
на 17.
Решение. Так как
( )
( )
81
81
162 2
6 6 36==
и
36 17 2 2,= +
то
( ) ( )
81 81
36 2 mod17 36 2 mod17
( )
162 81
6 2 mod17 .
Так как
8
2 256 17 15 1,= = +
то
35
( )
( )
( ) ( )
10
8 8 10 81
2 1 mod17 2 1 mod17 2 2 mod17 .
Так как
( )
162 81
6 2 mod17
и
( )
81
2 2 mod17 ,
то
( )
162
6 2 mod17
Так как
( )
162
6 2 mod17
, то остаток от деления
162
6
на 17 равен 2.
Ответ. Равен 2.
2. Найдите остатки от деления числа
1930
2а =
на 5, 11, 13.
Решение. 1) Так как
( )
44
2 16 2 1 mod5 1930 4 482 2,и= = +
то
( )
( ) ( ) ( ) ( )
482
485
1930 4 2
2 2 2 mod5 1 4 mod5 4 mod5 .
Так как
( )
1930
2 4 mod5 ,
то остаток от деления числа а на 5 равен 4.
2) Так как
( )
55
2 32 2 3 11 1= = −
и
1930 5 386,=
то
( )( )
( )
( ) ( ) ( )
1930 5 386
386
386
5 5 1930
2 1 mod11 2 1 mod11 2 1 mod11 .
=
− −
Так как
( )
1930
2 1 mod11 ,
то остаток от деления числа а на 11 равен 1.
3) Так как
( )
66
2 64 2 5 13 1= = −
и
1930 6 321 4,= +
то
( )( )
( )
( ) ( )
( )( ) ( )
1930 6321 4
321
321
6 6 4
1930 1930
2 1 mod11 2 2 1 16 mod13
2 1 13 2 10 mod13 2 10 mod13 .
= +
− −
− −
Так как
( )
1930
2 10 mod13 ,
то остаток от деления а на 13 равен 10.
Ответ. 4, 1, 10.
51. Найдите последнею цифру числа
1969 1537
3 19 .а =+
Решение. Последняя цифра числа а совпадает с остатком от деления
числа а на 10. Поэтому надо найти наименьшее целое число k такое, что
( )
mod10 .ak
1) Так как
4
3 81=
, то
( )
( )
( ) ( ) ( )
1969 4 492 1
492
492
4 4 1 1969
3 1 mod10 3 3 1 3 mod10 3 3 mod10 .
= +
Итак,
( )
1969
3 3 mod10 .
2) Так как
2
19 361=
, то
( )
( )
( ) ( ) ( )
1537 2 768 1
768
768
2 2 1537
19 1 mod10 19 19 1 19 mod10 19 9 mod10 .
= +
Итак,
( )
1537
19 9 mod10 .
2) Так как
( )
1969
3 3 mod10
и
( )
1537
19 9 mod10 ,
то
( )
( )( )
( )
( )
1969 1537 1969 1537
3 19 3 9 mod10 3 19 2 mod10 .+ + +
Последняя цифра числа а равна 2, так как
( )
( )
1969 1537
3 19 2 mod10 .+
Ответ. 2.
52. Найдите две последние цифры числа
1971
7.а =
36
Решение. Две последние цифры числа а совпадает с остатком от
деления числа а на 100. Поэтому надо найти наименьшее целое число k
такое, что
( )
mod100 .ak
Так как
4
7 301=
, то
( ) ( )
( )
( ) ( )
( )
1971 4 492 3
492
492
4 4 4 3
1971
7 301 mod100 7 1 mod100 7 7 1 343 mod100
7 43 mod100 .
= +
Итак,
( )
1971
7 43 mod100 .
Так как
( )
1971
7 43 mod100 ,
то две последние цифры числа а равны 43.
Ответ. 43.
53. Найдите наименьшее натуральное число, представимое в виде
суммы 1892 натуральных слагаемых с одинаковыми суммами цифр и в
виде суммы 1987 натуральных слагаемых с одинаковыми суммами цифр.
Решение. Если искомое натуральное число n является суммой 1892
натуральных чисел, сумма цифр каждого из которых равна k, то сумма
цифр числа n, равна
1892 .k
Если искомое натуральное число n является суммой 1987
натуральных чисел, сумма цифр каждого из которых равна m, то сумма
цифр числа n, равна
1987 .m
Воспользуемся следующим: остаток от деления числа на 9 равен
остатку отделения суммы цифр этого числа на 9.
Так как остатки от деления чисел n,
1892 ,k
1987 m
на 9 равны, то
( )
( )
( )
( ) ( ) ( ) ( )
1892 mod9 ,
1892 1987 mod9
1987 mod9 ;
210 9 2 220 9 7 mod9 2 7 mod9 .
nk
km
nm
k m k m
+ +
Числа 2k и 7m сравнимы по модулю 9, если k кратно 7, а m кратно 2.
Так как надо найти наименьшее натуральное число n, то рассмотрим
случай когда
7, 2km==
.
Отметим: если сумма цифр числа равна 7, то числами могут быть,
например, такие: 7, 16, 25; если сумма цифр числа равна 2, то числами
могут быть, например, такие: 2, 11, 20.
Так как, любое натуральное число не меньше суммы своих цифр, то
7
2
1892 , 13244,
13244.
1897 ; 3794;
k
m
n k n
n
n m n
=
=
1) Докажем, что число
13244n =
представимо в виде суммы 1892
натуральных слагаемых, каждое из которых равно 7.
Имеем
37
1892
13244 7 1892 13244 7 7 7.
семёрка
= = + + +
Итак, число
13244n =
представимо в виде суммы 1892 натуральных
слагаемых, если сумма цифр каждого слагаемого равна 7.
2). Докажем, что число
13244n =
представимо в виде суммы 1987
натуральных слагаемых, сумма цифр каждого слагаемого равна 2.
Пусть а – число слагаемых, каждое из которых равно 2 и b– число
слагаемых, каждое из которых равно 11. Тогда имеем
( )
13244 2 1987 11 ,
13244 2 11 , 9 9270, 1030,
1987; 1987; 957.
1987;
bb
a b b b
a b a b a
ab
= − +
= + = =
+ = + = =
+=
Итак, имеем
957 1030
13244 2 957 11 1030 13244 2 2 2 11 11 11.= + = + + + + + + +
Число
13244n =
представимо в виде суммы 1987 натуральных
слагаемых, если сумма цифр каждого слагаемого равна 2.
Таким образом, искомым числом является число
13244n =
.
Ответ. 13 244.
Алгебра - еще материалы к урокам:
- Самостоятельная работа по алгебре "Умножение одночлена на многочлен" 7 класс
- Электронное пособие для подготовки к ОГЭ по алгебре в 9 классе (повторение по базовым темам алгебры 7-9 класса)
- Самостоятельная работа по алгебре "Многочлен" 7 класс
- Презентация "Наибольшее и наименьшее значения функции" 11 класс
- Методическая разработка урока алгебры "Линейная функция и её график" 7 класс
- Итоговый контрольный срез по алгебре за 1 полугодие 8 класс (по учебнику А.Г. Мерзляк)
