Делимость чисел

70

И. Г. Булавко
Делимость чисел

Все вы хорошо знаете, что такое делимость чисел. А умете ли вы решать задачи на делимость? Задачи эти нередко предлагаются и на математических олимпидах, и на вступительных экзаменах в математические школи. В этой статье мы подробно разбираем несколько задач на делимость; к каждой задаче дается совет, который может оказаться полезным и при решении других задач.

Напомним основные сведения из теории делимости.

О пределене. Пусть $a$ и $b$ — целые числа и $b \neq 0$. Будем говорить, что $a$ делится на $b$, записывают так: $a \mid b$, или же говорят, что $b$ делит $a$, и пишут: $b/a$ (соответственно, если $a$ не делится на $b$ (то есть $b$ не делит $a$), пишут $a \neq b$).

Теоремы

1. Если $a$ делится на $b$, $b$ делится на $c$, то $a$ делится на $c$:
   $(a \mid b \text{ и } b \mid c) \Rightarrow (a \mid c)$.
2. Если $a$ делится на $m$, то $m$ и $ab$ делится на $m$ ($b$ — любое целое число):
   $(a \mid m) \Rightarrow (ab \mid m)$.
3. Если $a$ делится на $m$ и $b$ делится на $m$, то $m$ и $a + b$ делится на $m$:
   $(a \mid m \text{ и } b \mid m) \Rightarrow (a + b \mid m)$.

*) Латинскими буквами $a, b, c, d, \dots$ мы впервые будем обозначать целые числа; если число при этом простое, обозначим его буквой $p$.

4. Если $a + b$ делится на $m$ и $a$ делится на $m$:
   $(a + b \mid m \text{ и } a \mid m) \Rightarrow (b \mid m)$.
5. Если $a$ делится на $m$, и $a$ делится на $k$, причем $m$ и $k$ взаимно просты*), то $a$ делится на произведение $mk$:
   $(a \mid m \text{ и } a \mid k \text{ и } (m, k) = 1) \Rightarrow \Rightarrow (a \mid mk)$.
6. Если $ab$ делится на $m$ и $a$ взаимно просто $c$ $m$, то $b$ делится на $m$:
   $(ab \mid m \text{ и } (a, m) = 1) \Rightarrow (b \mid m)$.

В дальнейшем мы будем пользоваться этим теореми без специальных ссылок на них.

Задача 1. Если к некоторому прямизначному числу**) приписать справа цифру $6$ и полученное новое число умножить на $4$, то получится первоначальное число с приписанной цифрой $6$ впереди. Найти получшееся число.

Совет. Прежде чем решать задачу, записите (по возможности — удачнее) ее текст на математическом языке.

Решение.

$$\frac{\times \frac{abcde}{4}}{6abcde}.$$

Выполняя умножение, последовательно нахождение цифры искомого числа: $e = 4$, $d = 8$ и так далее.

Ответ. 615384.

Задача 2. Записали одну за другой четыре последовательные цифры, затем перевеibe две помещали местами

*) Говорят, что число $a$ взаимно просто $c$ $b$, если наиболее общий делитель $a$ и $b$ равен 1. Обозначют наиболее общий делитель чисел $a_1, a_2, \dots, a_n$ через $(a_1, a_2, \dots, a_n)$. Тогда то, что $a$ взаимно просто $c$, записывается так: $(a, b) = 1$.

**) Многозначное, например, $n + 1$-значное, число приято обозначать следующим образом: $a_n a_{n-1} \dots a_0$, где $a_i$ ($i = 0, 1, 2, \dots, n$) — цифры числа; цифры можно обозначать также буквами $a, b, c, \dots$

72

получаются из формулы $a = 5q + r$, то есть вместе равенств $a = 5q$, или $a = 5q + 1$, или $a = 5q + 2$, или $a = 5q + 3$, или $a = 5q + 4$, учитывая (2), можно записать, что $a - \text{либо } 5m$, либо $5m \pm 1$, либо $5m \pm 2$.

Очевидно, что такая форма записи более компактна. (В приведенном примере вместе $r = 3$ и $r = 4$ мы записали $(5 - r)$, то есть $-1$ и $-2$.) Решение. Пусть $a$ и $b$ — два числа, удовлетворяющие условию задачи. Выясним, какие значения могут принимать остатки от деления этих чисел и их квадратов на 24. Представим число $a$ в виде $a = 24q + r$, где $0 \leq r < 24$. Так как $a$ не кратно 2 и не кратно 3, то $r$ может принимать лишь значения 1, 5, 7, 11, 13, 17, 19, 23. Следовательно, $a$ можно записать в одной из формум: $a = 24m_1 \pm 1$, $a = 24m_2 \pm 5$, $a = 24m_3 \pm 7$, $a = 24m_4 \pm 11$. Нетрудно проверить, что в любом из этих случаях остаток от деления $a^2$ на 24 равен 1.

Аналогично получим, что $b^2 = 24n + 1$. Тогда $a^2 - b^2 = 24(m - n)$, то есть $a^2 - b^2$ делится на 24. Задача решения.

Уражение 3. Докажите, что число $5q + 2$ не является квадратом целого числа при каком значении $q$.

Задача 5. Докажите, что $A = n^5 - 5n^3 - 6n$ делится на 10.

Совет. При решении задачи на делимость часто помогает следующая теорема: из $n$ последовательных натуральных чисел odно и молко odно делится на $n$.

Докажите эту теорему самостояльно. Сформулируйте и докажите аналогичные теоремы для $n$ последовательных нечетных чисел и $n$ последовательных четных чисел (здесь уже существует то, каково $n$ — четное или же нечетное).

Решение. $A = n(n^4 - 5n^2 - 6) = n(n^4 - 5n^2 + 4) - 10n = n[(n^4 - n^2) - (4n^2 - 4)] - 10n = n(n^2 - 1)(n^2 - 4) - 10n = (n - 2)(n - 1)n(n + 1) \times (n + 2) - 10n$.

Произведение $(n - 2)(n - 1)n(n + 1)(n + 2)$ делится, согласно упомянутой теореме, и на 2, и на 5, то есть делится на 10. Но, значит, и все разность (равная $A$) также делится на 10, что и требовалось доказать.

Задача 6. Докажать, что число $N = \underbrace{11 \dots 1}_{k \text{ цифр}} \underbrace{12 \dots 2}_{k \text{ цифр}} \underbrace{2 \dots 2}_{k \text{ цифр}}$ есть произведение двух последовательных натуральных чисел.

Совет. Если задача не поддается решения в обшем виде, рассмотрите несколько ее частных случаев и затем попытайте перейти от них к общему случаю.

Решение. Заметим, что $12 = 3 \cdot 4$, $1122 = 33 \cdot 34$, $111222 = 333 \cdot 334$.

Естественно предположить, что и в общем случае $N = \underbrace{11 \dots 1}_{k \text{ цифр}} \underbrace{12 \dots 2}_{k \text{ цифр}} = \underbrace{33 \dots 3}_{k \text{ цифр}} \underbrace{33 \dots 34}_{k \text{ цифр}}$.

Докажем равенство (3). Имеем: $33 \dots 3 \cdot 33 \dots 34 = 3 \cdot 11 \dots 1 \times \times (33 \dots 3 + 1) = 11 \dots 1 \times \times (99 \dots 9 + 3) = 11 \dots 1 \times (10^k + 2) = 11 \dots 122 \dots 2$, что и требовалось доказать.

Задача 7. Докажать, что $A_n = 2^{n+2} \cdot 3^n + 5n - 4$ делится на 25 при любом натуральном $n$.

Совет. Такие утверждения разумно доказывать методом математической индукции.

Решение. 1) При $n = 1$ утверждение справедливо:

$A_1 = 2^3 \cdot 3 + 5 - 4 = 25$ делится на 25.

73

2. Предложим, что утверждение уже доказано для всех $n \leq k$; доказем, что оно верно также и для $n = k + 1$, то есть доказем, что $A_{k+1}$ делится на 25. Имеем:

$$A_{k+1} = 2^{k+3} \cdot 3^{k+1} + 5k + 1 = 2 \cdot 2^{k+2} \cdot 3 \cdot 3^k + 5k + 1 = 6 (2^{k+2} \cdot 3^k) + 5k + 1 = 6 (2^{k+2} \cdot 3^k + 5k - 4) - 25k + 25 = 6A_k - 25 (k - 1)$$

делится на 25, так как $A_k$ делится на 25 согласно индукционному предположению.

Следовательно, $A_n$ делится на 25 при любом натуральном $n$.

Задача 8. Чем выраженное число, являющееся полным квадратом, обладает следующим свойством: если все его цифры уменьшить на одно и то же число, то получится целый разряд числа, также являющееся полным квадратом. Найти все целые разряд числа с описанным свойством.

Совет. В некоторых случаях целесообразно поprobовать решить задачу подбором. При этом следует помнить, что подбор обязательно должен быть исчерпывающим, иначе задача не может считаться решенной.

Решение. Дано, что

$$\frac{abcd}{(a-k)(b-k)(c-k)(d-k)} = B^2.$$

Ясно, что

$$a \geq k, b \geq k, c \geq k, d \geq k.$$

Рассмотрим разность $A^2 - B^2$:

$$A^2 - B^2 = (1000a + 100b + 10c + d) - [1000(a-k) + 100(b-k) + 10(c-k) + (d-k)] = 1111k,$$

то есть

$$(A + B)(A - B) = 11 \cdot 101k.$$

Так как $A^2$ и $B^2$ — целые разряд числа, то $32 \leq A \leq 99$ и $32 \leq B \leq 99$; значит, во всяком случае

$$64 < A + B < 200,$$

$$0 < A - B < 67.$$

Отсюда сразу следует, что $A + B = 101$, $A - B = 11 \cdot k$. Разумма $A + B$ число нечетное, то и разность $A - B$ число нечетное. Поэтому и $k$ должно быть нечетным. Так как $A - B < 67$, то могут подойти следующие значения $k$: 1, 3, 5. Подходит лишь $k = 1$ и $k = 3$.

Ответ. a) $3136 = 56^2$; $2025 = 45^2$.

6. $4489 = 67^2$, $1156 = 34^2$.

И, наконец, главный совет: решайте как можно больше задач, ведь договора и смекалка приходит только с опытом.

Упражнения

4. Докажите, что $A = m(m^2 - 7)$ делится на 6 при любом натуральном $m$.

5. Докажите, что если к любому трехзначному числу приписать справа это же число, то полученное шестизначное число делится на 7, 11 и 13.

6. Найти двузначное число, равное неполонному квадрату суммы его цифр.

7. Докажите, что число, состоящее из $3^n$ единиц, делится на $3^n$.

8. Докажите, что не существует целых чисел $a, b, c$, удовлетворяющих равенствам: $abc + a = 3333, abc + b = 5555, abc + c = 7777$.

9. Докажите, что если $p$ — простое число, большее 3, то $N = p^2 + 3n + 2$ — составное при любом натуральном $n$.

10. Докажите, что $S = 3 + 3^3 + 3^5 + \dots + 3^{4n-1}$ делится на 10.

11. Найти пятизначное число, превосходящие в 45 раз произведение его цифр.

12. Докажите, что сумма

$$\underbrace{11 \dots 1}_{m\text{ цифр}} \cdot \underbrace{100 \dots 5}_{m+1\text{ цифра}} + 1$$

является квадратом натурального числа.