Тема 01 · Математика, углублённый уровень · подтема 5 из 5

Цифры и запись чисел

Натуральные числа и делимость. 100 заданий.

Решено

Правильно

Точность

Простыми словами

Делимость — это вопрос «можно ли разложить поровну без остатка». 60 конфет можно раздать поровну 12 детям, а 7 детям — нет: останется 4. Почти все задачи темы решаются тремя инструментами: признаки делимости, разложение на простые множители и остатки.

Число $a$ делится на $b$ ( $b$ — делитель $a$ , $a$ — кратное $b$ ), если $a = b \cdot k$ для натурального $k$ .

Простое число имеет ровно два делителя: $1$ и само себя ( $2, 3, 5, 7, 11, 13, \dots$ ). Составное — больше двух делителей. Число $1$ ни простое, ни составное.

Признаки делимости и неизвестные цифры

На	Признак
2, 5, 10	по последней цифре (чётная; 0 или 5; 0)
4, 25	число из двух последних цифр делится на 4 (на 25)
8	число из трёх последних цифр делится на 8
3, 9	сумма цифр делится на 3 (на 9)

Составной делитель раскладывают на взаимно простые множители (у них нет общих делителей, кроме 1) и проверяют каждый признак:

12 = 4 \cdot 3, 18 = 2 \cdot 9, 20 = 4 \cdot 5, 24 = 8 \cdot 3, 36 = 4 \cdot 9, 45 = 5 \cdot 9, 72 = 8 \cdot 9

$36 = 6 \cdot 6$ не годится: $6$ и $6$ не взаимно просты. Число $30$ делится на $6$ , но не на $36$ . Так же $24 \neq = 4 \cdot 6$ : число $12$ делится и на 4, и на 6, но не на 24.

Какую цифру поставить вместо $*$ , чтобы $3068 * 8$ делилось на $24$ ?

$24 = 8 \cdot 3$ — нужны оба признака.
На 8: три последние цифры $8 * 8$ . Из $808, 818, \dots, 898$ на 8 делятся $808, 848, 888$ — цифра $0$ , $4$ или $8$ .
На 3: сумма цифр $3 + 0 + 6 + 8 + * + 8 = 25 + *$ делится на 3 при $* = 2, 5, 8$ .
Общая цифра — $8$ . Ответ: $8$ .

Чтобы число было наибольшим, ставим в старшие неизвестные разряды самые большие подходящие цифры, наименьшим — самые маленькие. Пример: $756 * *$ делится на $20 = 4 \cdot 5$ → последняя цифра $0$ , число из двух последних цифр $* 0$ делится на 4 → десятки чётные, наибольшая $8$ : $75680$ .

Простые множители и число делителей

Любое составное число единственным образом раскладывается в произведение простых множителей. Удобно делить «деревом»:

Листья дерева — простые числа; их произведение равно

900

n = p^{a} \cdot q^{b} \cdot r^{c} \Rightarrow делителей (a + 1) (b + 1) (c + 1)

p, q, r

— разные простые множители,

a, b, c

— их показатели степени

Почему: делитель содержит $p$ в степени от $0$ до $a$ — это $a + 1$ вариант, и так для каждого множителя. Для $900 = 2^{2} \cdot 3^{2} \cdot 5^{2}$ : $(2 + 1) (2 + 1) (2 + 1) = 27$ делителей.

Точный квадрат — все показатели чётные; точный куб — все показатели делятся на 3.

Наименьшее $k$ , при котором $4719 \cdot k$ — точный куб.

Раскладываем: $4719 = 3 \cdot 1 1^{2} \cdot 13$ .
Доводим каждый показатель до 3: не хватает $3^{2}$ , $1 1^{1}$ , $1 3^{2}$ .
$k = 9 \cdot 11 \cdot 169 = 16731$ .

Единственное чётное простое число — $2$ . Поэтому сумма двух простых чисел нечётна, только если одно из них равно $2$ .

НОД и НОК

НОД — наибольший общий делительБерём общие простые множители в наименьших степенях.

НОД (60, 90) = 2 \cdot 3 \cdot 5 = 30

НОК — наименьшее общее кратноеБерём все простые множители в наибольших степенях.

НОК (60, 90) = 2^{2} \cdot 3^{2} \cdot 5 = 180

НОД (a, b) \cdot НОК (a, b) = a \cdot b

верно для любых двух натуральных чисел

«Разложить поровну, использовав всё, на наибольшее число подарков» — НОД. «Снова совпадут», «наименьшее число, которое делится на…» — НОК.

Прямоугольник $99 \times 45$ режут на наибольшие одинаковые квадраты: сторона $НОД (99, 45) = 9$ , квадратов $(99 : 9) \cdot (45 : 9) = 11 \cdot 5 = 55$ . Из плиток $11 \times 3$ складывают наименьший квадрат: сторона $НОК (11, 3) = 33$ , плиток $(33 : 11) \cdot (33 : 3) = 3 \cdot 11 = 33$ .

$НОД = 3$ , $НОК = 495$ , одно число $33$ . Найдите другое.

$33 \cdot b = 3 \cdot 495 = 1485$ .
$b = 1485 : 33 = 45$ .

Деление с остатком

a = b \cdot q + r, 0 \leq r < b

a

— делимое,

b

— делитель,

q

— неполное частное,

r

— остаток

В сумме и произведении числа можно заменять их остатками. Если $a$ даёт остаток $5$ при делении на $8$ , а $b$ — остаток $1$ , то $2 a + 9 b$ даёт тот же остаток, что $2 \cdot 5 + 9 \cdot 1 = 19$ , то есть $3$ .
Одинаковый остаток $r$ при делении на несколько чисел — значит, $n - r$ делится на их НОК.
Остатки на 1 меньше делителей — значит, $n + 1$ делится на НОК.

Наименьшее число с остатками $6$ при делении на 7, $8$ — на 9, $11$ — на 12.

Каждый остаток на 1 меньше делителя, поэтому $n + 1$ делится на 7, 9 и 12.
$НОК (7, 9, 12) = 7 \cdot 9 \cdot 4 = 252$ .
$n = 252 - 1 = 251$ .

Цифры числа

Остаток при делении на $3$ (на $9$ ) такой же, как у суммы цифр. Число $527527 \dots 527$ (5 раз): сумма цифр $14 \cdot 5 = 70$ , остаток от деления на 3 равен $1$ .
Последняя цифра степени повторяется с периодом 1, 2 или 4: у $7^{n}$ — $7, 9, 3, 1, 7, \dots$
Нулей на конце у $1 \cdot 2 \cdot \dots \cdot n$ столько, сколько пятёрок в разложении: $[n : 5] + [n : 25] + [n : 125] + \dots$ (берём неполные частные).

Наименьшее число, кратное 5, с суммой цифр 45.

Чем меньше цифр, тем меньше число; цифры не больше 9.
Последняя цифра $5$ (если $0$ — нужно шесть цифр $999990$ , это больше).
Остальные дают $40$ : минимум пять цифр, $4 + 9 \cdot 4$ . Ставим маленькую впереди: $499995$ .

Подсчёты: делители, остатки, цифры

Делим на простые $2, 3, 5, 7, 11, 13, \dots$ , пока квадрат делителя не больше числа. Ни одно не подошло — число простое. $251$ : проверяем до $13$ ( $1 7^{2} = 289 > 251$ ) — простое. А $203 = 7 \cdot 29$ , $893 = 19 \cdot 47$ .

сумма делителей 2^{a} \cdot 3^{b} \dots = (1 + 2 + \dots + 2^{a}) (1 + 3 + \dots + 3^{b}) \dots

для каждого простого множителя складываем все его степени от нулевой

$90 = 2 \cdot 3^{2} \cdot 5$ : $(1 + 2) (1 + 3 + 9) (1 + 5) = 3 \cdot 13 \cdot 6 = 234$ .

Делитель по частному и остатку. $404 = d \cdot 40 + 4$ → $d \cdot 40 = 400$ , $d = 10$ (остаток $4 < 10$ ✓).

Сколько чисел от 1 до $N$ дают остаток $r$ при делении на $b$ . Это числа $r, r + b, r + 2 b, \dots$ Для остатка $4$ при делении на $5$ до $1838$ : $4, 9, \dots, 1834$ ; их $(1834 - 4) : 5 + 1 = 367$ .

Сколько цифр в записи $1, 2, \dots, N$ . Однозначных чисел $9$ (9 цифр), двузначных $90$ (180 цифр), трёхзначных $900$ (2700 цифр). До $984$ : $9 + 180 + (984 - 99) \cdot 3 = 9 + 180 + 2655 = 2844$ .

На нумерацию страниц ушло $3373$ цифры. Сколько страниц?

Страницы $1$ – $999$ — это $9 + 180 + 2700 = 2889$ цифр.
Осталось $3373 - 2889 = 484$ цифры — это $484 : 4 = 121$ четырёхзначная страница.
Страниц $999 + 121 = 1120$ .

Посмотреть и посчитать

Калькуляторы

Разложение на простые множители

Серия: 0