Условие
Натуральное число $M$ представили в виде произведения простых сомножителей. Затем каждый из них увеличили на 1, и произведение стало равно $N$. Оказалось, что $N$ делится на $M$. Докажите, что если теперь разложить $N$ на простые множители и каждый из них увеличить на 1, то полученное произведение будет делиться на $N$.
Решение 1
Если $N$ делится на $M$, то разложение $M$ на простые множители является частью разложения $N$ на простые множители. После того, как мы увеличим на 1 каждый сомножитель из разложения $N$, все входящие в него простые множители числа $M$ увеличатся на 1 и дадут в произведении число $N$.
Решение 2
Пусть $M = p_1\ldots p_k$, где $p_1 \leqslant\ldots\leqslant p_k$. Тогда $N = (p_1 + 1)\ldots(p_k + 1)$. Одна из скобок, скажем, $p_i +1$, должна делиться на $p_k$, и так как $p_i\leqslant p_k$, это возможно лишь в случае $p_i + 1 = p_k$, откуда $p_i = 2$, $p_k = 3$. Итак, $M = 2^l3^m$, $N = 3^l4^m = 2^{2m}3^l$, причём $m \leqslant l \leqslant 2m$. Значит, новое число равно $3^{2m}4^l$ и делится на $N = 3^l4^m$. (Интересно, что новое (третье) число — квадрат первого.)
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Турнир городов |
|
год/номер |
|
Дата |
2024/25 |
|
Номер |
46 |
|
вариант |
|
Вариант |
осенний тур, базовый вариант, 8-9 класс |
|
задача |
|
Номер |
3 |
