ЗАДАЧИ НА ДЕЛИМОСТЬ ЧИСЕЛ

А. Б. Василевский
ЗАДАНИЯ ДЛЯ ВНЕКЛАССНОЙ РАБОТЫ ПО МАТЕМАТИКЕ
9—11 КЛАССЫ КНИГА ДЛЯ УЧИТЕЛЯ

Задание 2. ЗАДАЧИ НА ДЕЛИМОСТЬ ЧИСЕЛ

Скачать бесплатно в формате PDF с хорошим качеством: А. Б. Василевский ЗАДАНИЯ ДЛЯ ВНЕКЛАССНОЙ РАБОТЫ ПО МАТЕМАТИКЕ «Задание 1,2».

Смотреть онлайн:

Текст для быстрого ознакомления . Возможны неточности по формулам. Рекомендуем скачать книгу выше.

Задание 2. ЗАДАЧИ НА ДЕЛИМОСТЬ ЧИСЕЛ

При решении задач на делимость чисел часто находят
применение формуле:
an_ bn = ^ a _ b) ( ап -1 + ап-2 Ь +
+ an-3b2 + … + b n~{), (1)
где п — натуральное число;
а
п + Ь п = (а + Ь) (а п~ л — а п~ 2Ь +… +
+ ( _ 1 у-‘Ь п -‘\ (2)
где п = 2k + 1, k — любое натуральное число.
Для того чтобы убедиться в справедливости
формул (1) и (2), достаточно перемножить выражения,
стоящие в скобках.
З а д а ч а 1. Докажите, что число \7 п — 1 \ п делится
на 6 при любом натуральном значении п.
Р е ш е н и е . По формуле (1)
17″— 11″ = (17— 11).(17л-г’+ 17п-2 • 11 + . . . +
+ 1Г-1).
Утверждение задачи доказано.
29

———-

З а д а ч а 2. Доказать, что 2 • 7″ + 1 делится на 3 при
любом натуральном п.
Так как 2 • 7″ + 1 = 2(7″ — 1) + 3 и делимость
7″ — 1 на 3 следует из формулы (1), то утверждение
задачи доказано.
З а д а ч а 3. Доказать, что 32″ + 1 + 2″ + 2 делится на
7 при любом натуральном значении п.
Р е ш е н и е . Очевидно,
32„ +1 + 2, + 2 = 9„ . з + 2
п. 4 = 3(9″ — 2″) +
+ 3 • 2я + 4 . 2″ = 3(9″ — 2″) + 7 • 2″.
Число 9″ —2″ делится на 7 в силу формулы (1).
Число 7 • 2″ также делится на 7. Задача решена.
Математическая индукция — метод доказательства, основанный
на следующем принципе:
1) Некоторое свойство X верно при k — \ .
2) Из предположения, что свойством X обладает какое-либо
натуральное число /г^1, следует, что этим свойством обладает
число k 1.
Тогда свойство X имеет всякое натуральное число.
З а д а ч а 4. Доказать, что число 8″ + 6 кратно 7
при любом целом 1.
Р е ш е н и е . При п= 1 утверждение задачи верно.
Допустим, что оно верно при n = k т. е.
8* + 6 = 7m, (1)
где т — натуральное число.
Проверим теперь, что утверждение задачи верно и
при ti = k + 1, т. е. верно
8* + ‘ +6 = 7/, (2)
где t — натуральное число.
Из равенства (1) получаем 8 k = 7m — 6. Поэтому
8* + 1 + 6 = 8 — 8 * + 6 =
= 8(7m — 6) + 6 = 7 • 8m — 42 — 7(8m — 6),
т. е. t = 8m — 6.
Таким образом, t — натуральное число, и, следовательно,
в силу равенства (2) утверждение задачи доказано.
З а д а ч а 5. Доказать, что при любом натуральном
п выражение 32″ + 2+ 26″+1 делится на 11.
Р е ш е н и е . При п= 1 утверждение задачи верно.
Допустим, что это утверждение верно при п = k(k > 1),
т. е.
32& + 2 _|_ 2+1 = l l m j ( ! )
где m — натуральное число.
30

———

Докажем, что утверждение задачи верно и при
п = к + 1, т. е.
32(А+1)+2+2#*+1Н.»= П р’ (2)
где р — натуральное число.
Из равенства (1) имеем
3 2 k + 2= Пт — 2“+| (3)
С учетом равенства (3) сумма
^2(6 + 1) + 2 _|_ 2б)& + 1)+ 1 __ ^2 в ^2(6 -f 1) _|_ 0+ 1 _
= 32(11 т — 2 6 k + l) + 26(* + ,)+l = З2 • 1 lm — З2 • 2 X
X 26* + 27 • 2“ = З2 • 11т + 26*(27 — 2 X 32) = З2-11т +
+ 26*- 110= 11(9т+ 10-2м).
Итак, доказана справедливость равенства (2):
р = 9т + 10-2“
З а д а ч а 6. Могут ли числа я2 + Зп + 39 и п 2 + п +
+ 37 (п — натуральное число) одновременно делиться
на 49?
П е р в о е р е ш е н и е . Если при некотором значении
п выражения п 2 + Зп + 39 и /г + п + 37 делятся на
49, то на 49 должна делиться и их разность:
(.п 2 + Зп + 39) — {п 2 + п + 37) = 2(п + 1).
Выражение 2(ti + 1) делится на 49, если п + 1 = 49&
(k — натуральное число). Отсюда п = 49к— 1.
Подставив я = 49/г—1 в выражение п 2 + Зп + 39,
получаем
(49/г- I)2 + 3(49& — I) + 39 =
= 492Аг — 2 • 496 + 3 • 49/г + 37.
Последнее выражение на 49 не делится. Следовательно,
данные выражения одновременно делиться на 49 не
могут.
В т о р о е р е ш е н и е . Так как п 2 + Зп + 39 =
= (п + 5) • (п — 2) + 49, то п 2 + Зп + 39 делится на 49 в
том и только в том случае, когда произведение
(п + 5) • (п — 2) делится на 49. Но оба множителя в
этом произведении отличаются на 7, и поэтому либо
одновременно делятся на 7, либо одновременно не делятся
на 7. Первый случай имеет место при п = 7k + 2.
Аналогично получаем, что выражение
п 2 + п + 37 = (п + 4). (п — 3) + 49
делится на 49 при п — 7& + 3, и, следовательно, дан31

———-

ные в условии задачи выражения одновременно делиться
на 49 не могут.
З а д а ч а 7. Рассматриваются всевозможные семизначные
числа /(, записанные цифрами 1, 2, 3, 4, 5, 6, 7,
расположенными в произвольном порядке. Существуют
ли среди этих чисел два таких числа М и N, что М делится
на /V?
Р е ш е н и е . Во-первых, сумма цифр числа К равна
28. Поэтому М и N не делятся на 3 и 6.
Во-вторых, 7654321 является наибольшим из чисел
К , а 1234567 — наименьшим. Так как 7654321:
: 1234567 ^ 6,3, то ясно, что при делении М на N может
получиться только 2, 4 или 5.
Если число М делится на 5, то оно должно оканчиваться
цифрой 5. Ясно, что первой цифрой числа М может
быть только 6 или 7. Рассмотрим несколько примеров
(вычисления ведутся при помощи микрокалькулятора)
:
7643215:5 = 1528643, 7436125:5= 1487225,
7432165:5 = 1486433, 6374125:5 = 1274825,
6142375:5= 1228475, 6137245:5= 1227449.
Замечаем, что все частные содержат цифру 8 или 9.
Но почему? Да потому, что при делении на 5 всегда
приходится делить число 41, 42, 43 или 45 на 5.
Таким образом, осталось выяснить, существует ли
равенство 2N = М или 4N = М.
Рассмотрим несколько примеров:
3765421 • 2 = 7530842, 3765412 • 2 = 7530824,
2563714 • 2 = 5127428, 1654372 • 2 = 3308744,
2134567 • 2 = 4269134, 1234765 • 2 = 2469530.
После рассмотрения этих примеров становится понятным,
что при умножении любого числа N на 2 получаем
число с цифрой 8, если после 4 в N стоит цифра 1, 2
или 3. Если в N после цифры 4 стоит цифра 5, 6 или 7,
то при его умножении на 2 получаем число с цифрой 9.
Осталось выяснить, существует ли равенство
4А7 = Л1. Рассмотрим несколько примеров:
1765432
1273456
1354627
124.7653
1275643
4 = 7061728, 1276543
4 = 5093824, 1374625
4 = 5418508, 1257346
4 =4990612, 123J654
4 = 5102572, 1526743
4 = 5106172,
4 = 5498500,
4 = 7029384,
4 = 4950616,
4 = 6106972,
32

———-

1567234 4 = 6268936, 1742356 4 = 6969424,
1723654 4 = 6893616, 1243576 4 = 4974304,
1245763 4 =4983052, 1724653 4 = 6898612,
1725364 4 = 6901456, 1254763 4 = 5019052,
1256734 4 = 5026936, 1263754 4 = 5055016,
1526473
1274536
44
= 6105892,
= 5098144.
1726543 4 = 6906172,
Во-первых, ясно, что N может начинаться только
цифрой 1 и не может оканчиваться цифрами 2, 7 или 5.
Во-вторых, М везде содержит цифру 0, 8 или 9.
И это зависит от того, какие две цифры стоят в N
после 2:
34, 35, 36, 37, 43, 45, 46, 47, 53, 54,
56, 57, 63, 64, 65, 67, 73, 74, 75, 76.
Таким образом, доказано, что задача не имеет решения.
З а д а ч а 8. Может ли число 5″ — 1 делиться на
4 п — I, если п — натуральное число?
Р е ш е н и е . Обозначим М(п) = 5п — I, К(п) = 4 п —
— 1. Для поиска гипотезы составим таблицу значений
М(п) и К(п):
п М ( п ) К ( п )
I 4 3
2 24 15
3 124 63
4 624 255
5 30 124 1 023
6 150 624 4 095
7 753 124 16 383
8 3 765 624 65 535
9 18 818 124 262 143
10 94 090 624 1 048 575
11 370 045 124 4 194 303
12 1 852 265 624 16 777215
13 9 261 328 124 67 108 863
14 46 306 640 624 268 435 455
15 231533 203 124 1073 741823
Что дает рассмотрение таблицы?
1) Число М оканчивается цифрой 4.
2) Число К оканчивается цифрой 3 или 5. Причем,
если п — нечетное, то К оканчивается цифрой 3,
а если п — четное, то К оканчивается цифрой 5.
Следовательно, сумма цифр числа К делится на 3,
2 А. Б. Василевский

———

Потому что
4п — 1п = (4 — 1) • Р(п)
где Р(п) — многочлен.
Теперь ясно, что число М не делится на число К ,
если п — четное. Суммы цифр числа М (при нечетных /?)
дают основание предположить, что число М при всех
нечетных п не кратно 3. Но как это доказать?
Итак, как доказать, что число Q = 5 2 к +1 — 1
(.к — натуральное число) не делится на 3?
Представить Q так:
Q = ( 6- 1)2*+ 1 — 1.
Если к = 1, то Q = (6 — 1 )3 — 1 = (63 — 3 • 62 • 1 +
+ 3- 6- I2- I3)- 1.
Если к = 2, то Q = (6 — I)5 — 1 = (6 — 1)3(6 — I)2 —t
— 1 = (63 — 3 — 62 • 1-ЬЗ . 6 . 1 — 1). (62 — 2 . 6 . 1 +1) — 1.
Если к = 3, то Q = (6 — I)7 — 1 = (6 — 1 )3(6 —1 )4 —
— 1 — (63 — 3 • 62 • 1 3 • 6 — 1 — 1) • (62 — 2 • 6 • 1 +
+ 1)2-1.
Вообще,1
Q = ( 6- \ f k + ] — 1 = (63 — 3 • 62 — 1 + 3 — 6 . 1 — 1) X
X (62 — 2 • 6 • 1 + I)'»1 — 1.
Теперь ясно, что Q можно представить в следующем
виде:
Q = (6L- 1)- 1 =61-2.
Отсюда понятно, что Q не делится на 3.
Таким образом, ни при каком натуральном значении
п число Ъ п — 1 не делится на число 4П — 1.
Для решения этой задачи можно применить и метод математической
индукции.
З а д а ч а 9. Восстановить числа (х обозначают
цифры от 0 до 9):
(1) ^ 7 ^ ^ ^ ^
(2)
(3) * * 7
(4) * * * * * * *
(5) *7* * * *
(6) *7****
,7) * * * * * * *
(3) * * * *у * *
(9) _ * * * * * *
* * * * * *
(Ю) 0

————

которых записаны числа, получаемые в процессе
деления.
Делитель — шестизначное число. Третья цифра
частного — 7. При умножении шестизначного числа на
7 получили шестизначное число (6-я строчка). Но это
возможно только в том случае, если делитель начинается
цифрой 1. Итак, делитель имеет вид: 1**7*.
Для упрощения рассуждений делитель и частное
запишем соответственно в виде: 1АБВ7Г, ДЕ7ЖК.
Далее, шестизначные числа записаны во 2-й, 6-й,
10-й строчках, семизначные — в 4-й и 8-й строчках.
Поэтому Е-8 или Е-9, Ж-8 или Ж-9, 1 ^ А ^ 4.
Если при умножении числа 1АБВ7Г на 8 или 9 получается
семизначное число, то оно обязательно начинается
цифрой 1.
Допустим А = 4. Тогда число из 6-й строчки начиналось
бы цифрой 9. Но этого не может быть, так как при
вычитании из шестизначного числа (строчка 5) шестизначного
числа (строчка 6) получаем шестизначное
число (строчка 7). Итак, А ф4. По этой же причине
А Ф 3. Следовательно, А = 1 или К —2.
Допустим, что А = 1. Тогда на основании 6-й строчки
получаем, что Б=1 (Б не может быть равно нулю
в силу 4-й и 8-й строчек; Б не может быть больше 1 в силу
6-й строчки).
Итак, допустим, что делитель имеет вид 111В7Г.
В силу 4-й и 8-й строчек В Ф 0. С другой стороны,
В«<4 (в силу 6-й строчки). Если делитель имеет вид
11117Г, 11127Г или 11137Г, то при любом значении Г
в 8-й строчке третья цифра справа не будет равна 7.
Следовательно, А Ф 1 и В >> 3.
Итак, делитель имеет вид 12БВ7Г.
Все, до сих пор установленное, внесем в данный
пример: I 12БВ7Г
I ДЕ7ЖК
******
******
0
35

———

Теперь понятно, что первой цифрой 5-й строчки
является 9, а 7-я и 8-я строчки начинаются цифрами
1 и 0:
**7******* \ 12БВ7Г
***** 7 *
I * * * * * *
97 ****
87****
10*****
10**7**
******
******
ДЕ7ЖК
Так как 120-9 = 1080, 121 -9 = 1089, 122 — 9= 1098,
123 *9=1107, то в силу 8-й строчки третья цифра этой
строчки не может быть больше 2, если Ж = 9. Но
120-7 = 840, 121-7 = 847, 122-7 = 854.
Поэтому в силу 6-й строчки Жф9. Итак, Ж = 8.
Далее 123 — 7 = 861, 124 — 7 = 868, 125-7 = 875,
126 — 7 = 882. Отсюда и в силу 6-й строчки следует, что
Б = 4 или Б = 5. Но Б Ф 4, так как 1249-8 = 9992
(см. 8-ю строчку). Следовательно, Б = 5.
Сравнивая 3-ю и 4-ю строчки, получаем, что 3-я
строчка начинается с 1 (больше единицы первая цифра
3-й строчки не может быть еще и потому, что первая
цифра делителя 1). Кроме того, 125 — 8 = 1000, 126 — 8 =
= 1008. Поэтому третья цифра 8-й строчки 0. Тепепь-
имеем такую картину:
**7******* | 125В7Г
****** | ДЕ78К
I****7*
1 * * * * * *
97****
87****
1Q*****
100*7**
‘i’ *i» ‘f*
ф * :5с :}с $ *
о
36

————-

8771, 1254-7 = 8778, 1255-7 = 8785, 1256-7 = 8792,
1257•7 = 8799, 1258 • 7 = 8806.
Поэтому (см. 6-ю строчку) 1 ^ В ^ 7.
При умножении числа 125В7Г (при любом значении
Г) на 8 третья цифра справа (в 8-й строчке) будет
равна 7 только в том случае, если произведение В-8
оканчивается цифрой 2 (8В — число четное). Это
возможно, если В = 4 или В = 9. Но 1 ^ В ^ 7.
Итак, В = 4.
Так как 7*8 = 56, то Г • 9 < 40, т. е. Г ^ 4. Далее,
125470 • 7 = 878290 и 125474 • 7 = 878318. Поэтому
третья цифра слева в 6-й строчке 6, третья цифра слева
в 5-й строчке 9, тогда
******
1 * * * * 7 *
1 * * * * * *
_____ 979***
878***
101****
100*7**
1 *****
о
Из 9-й строчки следует, что К = 1.
Так как 125471 — 8= 1003768, 125474-8 = 1003792,
то при Г ^ 4 четвертая цифра слева в 7-й строчке 6
(6, а не 5, потому что 7 + 5=12). Теперь получаем
**7******* | 1254 Г
****** 1ДЕ781
1****7*
1 * * * * * *
_ 979***
878***
1016***
10037**
_ 12547*
12547*
0
12547Г
ДЕ78К
37

————-

цифра слева в б-й строчке не должна быть больше 3.
А это возможно, если 2 ^ Г ^ 4.
В 7-й строчке пятая цифра слева может быть равна
2 или 3. Но так как 125472-8=1003776, 125473-8 =
= 1003784, 125474-8= 1003792, то пятая цифра слева
в 7-й строчке может быть только 3 и четвертая цифра
в 6-й строчке 3. С учетом этого получаем:
**7*******
— ******
1 * * * * 7 *
1 ******
9799**
8783**
_ 10163**
10037**
12547*
12547*
0
Сравнивая 3, 4 и 5-ю строчки, получаем, что в 4-й
строчке вторая цифра справа может быть 8 или 7. Но
12547-9=112923 и 1 8 < 9 Г < 40. Поэтому Е Ф 9,
т. е. Е = 8. Но 12547-8=100376 и 16<8Г<32.
Поэтому Г = 2 или Г = 3, и, следовательно, получаем:
**7******* | 12547Г
****** | ДЕ781
1 * * * * 7
j * * * * * *
9799**
8783**
10163**
~10037**
_12547*
12547*
Сравнивая 3, 4 и 5-ю строчки, получаем, что в 4-й
строчке вторая цифра справа может быть 8 или 7.
Но 12547-9= 112923 и 18<9Г<40. Поэтому Е ф9,
т. е. Е = 8. Но 12547-8= 100376 и 16<8Г<32.
Поэтому Г = 2 или Г = 3, и, следовательно, получаем:
12547Г
ДЕ781
38

————

**7******* | 12547Г
****** ] Д8781
_ 110177*
10037**
9799**
8783**
_ 10163**
10037**
_ 12547*
12547*
0
Из первых трех строчек ясно, что в 3-й строчке
третья цифра слева 6 или 7. Непосредственной проверкой
убеждаемся, что это будет только в том случае, если
Д = 3 или Д = 5 соответственно.
Легко проверить, что Д Ф 3. Итак, Д = 5. Теперь
очевидно, что Г = 3.
Окончательно находим: при делении числа
7375428413 на 125473 получаем 58781.