Эйлер 2025 · Математика · 8 кл., №5

Условие

Дано натуральное число $n$ Докажите, что при некотором натуральном $m$ у числа $m^3+m$ ровно один или ровно два различных простых делителя, больших $n$

О задаче · 8 класс

Олимпиада: Олимпиада имени Леонарда Эйлера, XVII олимпиада
Этап: Заключительный этап
Предмет / класс: Математика · 8 класс
Дата: 24–27 марта 2025

Возьми конкретное $n$ например $n = 10$ и поищи подходящее $m$ разложи $m^3+m$ на простые множители и посчитай простые, большие $n$ Для одного $n$ это нетрудно — трудность в том, чтобы указать способ выбрать $m$ при любом $n$ и доказать, что больших простых делителей окажется не ноль и не больше двух. В модели «Охота на большие простые» можно быстро перебрать много пар $n$ и $m$ и проверить свой способ при разных $n$

Задача на доказательство: ответ — способ выбрать $m$ по данному $n$ и обоснование, что больших простых делителей получится ровно один или ровно два, а не одно число.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеОхота на большие простые

Пробуй свои варианты. Разбор останется закрытым.

Своя гипотеза

Охота на большие простые

Выбери n и m. Модель разложит m и m² + 1 на простые множители, выделит простые, большие n, и посчитает их. Найди способ выбирать m по n так, чтобы их всегда было один или два, — и проверь его при разных n.

Без JavaScript модель не работает. Возьми на бумаге несколько n, для каждого — своё m, разложи m и m² + 1 на простые множители и отметь простые, большие n.

Подсказка 1

Разложи: $m^3+m = m\cdot(m^2+1)$ Большие простые делители проще всего сосчитать у множителя $m$ если взять его простым и большим $n$ тогда такой делитель ровно один — само $m$ Остаётся понять, как не дать «лишним» большим простым появиться в $m^2+1$

Подсказка 2

Возьми в качестве $m$ наименьшее простое число, большее $n$ Тогда любое другое простое число, большее $n$ больше $m$ то есть не меньше $m+1$ Может ли $m^2+1$ делиться сразу на два различных простых числа, каждое из которых не меньше $m+1$

Разобрать решение по шагам

Разбиваем число на два множителя

Назовём простое число большим, если оно больше $n$ Нужно найти $m$ у которого число $m^3+m$ имеет ровно один или ровно два различных больших простых делителя.

Вынесем $m$ за скобки:

m^3+m = m\cdot(m^2+1).

Каждый простой делитель произведения делит хотя бы один из сомножителей. Значит, большие простые делители числа $m^3+m$ — это большие простые делители числа $m$ вместе с большими простыми делителями числа $m^2+1$

Почему нельзя брать $m$ наугад: при $n = 2$ и $m = 15$ получаем

15\cdot 226 = 2\cdot 3\cdot 5\cdot 113,

больших простых три: $3$ $5$ и $113$ А «удобное» правило $m = n+1$ ломается при $n = 17$

18\cdot 325 = 2\cdot 3^2\cdot 5^2\cdot 13,

больших простых нет вовсе. Поэтому план такой: выбрать $m$ так, чтобы держать под контролем каждый из двух множителей.

Первый множитель: берём m простым

Проще всего сосчитать большие делители множителя $m$ если $m$ — простое число, большее $n$ тогда у него ровно один большой простой делитель — оно само.

Возьмём $m$ равным наименьшему простому числу, большему $n$ Такое есть: простых чисел бесконечно много (это доказал ещё Евклид), значит, среди чисел, больших $n$ простые встречаются, а среди них есть самое маленькое. Например, при $n = 10$ это $m = 11$ при $n = 13$ — $m = 17$

Зачем именно наименьшее, станет ясно в следующем шаге: из-за этого выбора все остальные большие простые числа оказываются больше $m$

Большие делители m² + 1 не меньше m + 1

Пусть $s$ — большой простой делитель числа $m^2+1$ Сначала заметим, что $s \ne m$ число $m^2+1 = m\cdot m + 1$ при делении на $m$ даёт остаток $1$ поэтому на $m$ не делится.

Итак, $s$ — простое число, большее $n$ и не равное $m$ Но $m$ — наименьшее простое число, большее $n$ между $n$ и $m$ простых чисел нет. Поэтому $s$ больше $m$ то есть

s \ge m+1.

Вот где пригодился выбор наименьшего простого: условие «больше $n$ » для делителей $m^2+1$ превратилось в гораздо более сильное «не меньше $m+1$ ».

Двух больших делителей у m² + 1 нет

Предположим, что $m^2+1$ делится на два различных больших простых числа $s$ и $t$ Различные простые числа входят в разложение $m^2+1$ на простые множители оба, поэтому $m^2+1$ делится на их произведение $s\cdot t$ а значит, не меньше его. По шагу 3 каждое из чисел $s$ $t$ не меньше $m+1$ поэтому

\begin{aligned}m^2+1 &\ge s\cdot t\\[0.45em]&\ge (m+1)^2\\[0.45em]&= m^2+2m+1.\end{aligned}

Но $m^2+2m+1 > m^2+1$ ведь $2m > 0$ Получилось $m^2+1 > m^2+1$ — противоречие. Значит, у $m^2+1$ не больше одного большого простого делителя.

На примере $n = 10$ $m = 11$ (рисунок ниже): $m^2+1 = 122$ а два больших простых делителя, каждый не меньше $12$ дали бы произведение не меньше $12\cdot 12 = 144$ — больше, чем $122$ И действительно, $122 = 2\cdot 61$ большой делитель один, $61$

При

n = 10

берём

m = 11

Все остальные простые числа, большие

10

не меньше

12

два таких делителя дали бы произведение не меньше

12\cdot 12 = 144

m^2+1 = 122

меньше.

Собираем ответ

Сложим вклады двух множителей. Множитель $m$ даёт ровно один большой простой делитель — само $m$ Множитель $m^2+1$ даёт не больше одного, и он отличен от $m$ (шаг 3). Значит, у числа $m^3+m$ различных простых делителей, больших $n$ ровно один или ровно два, что и требовалось доказать.

Встречаются оба случая — поэтому в условии и сказано «один или два»:

$n = 6$ $m = 7$ большой делитель один — $7$ (а $5 < 6$ ), потому что

7\cdot 50 = 2\cdot 5^2\cdot 7;

$n = 10$ $m = 11$ больших делителей два — $11$ и $61$ потому что

11\cdot 122 = 2\cdot 11\cdot 61.

Какой из случаев получится, заранее знать не нужно: для доказательства важно только, что их не ноль и не больше двух.

Проверка

Проверим на числах. При $n = 1$ $m = 2$ $2^3+2 = 10 = 2\cdot 5$ — два больших делителя ( $2$ и $5$ ). При $n = 5$ $m = 7$ $7\cdot 50 = 2\cdot 5^2\cdot 7$ — один ( $7$ ). При $n = 11$ $m = 13$ $13\cdot 170 = 2\cdot 5\cdot 13\cdot 17$ — два ( $13$ и $17$ ). Компьютерный перебор в тесте модели проверил выбор «наименьшее простое, большее $n$ » для всех $n$ от $1$ до $999$ отдельной простой программой (деление на все числа до корня): каждый раз больших простых делителей один или два, и оба случая встречаются. Перебор не заменяет доказательства, но подтверждает, что в рассуждении нет арифметической ошибки.

Ответ

Доказано: если $m$ — наименьшее простое число, большее $n$ то у числа $m^3+m = m(m^2+1)$ ровно один или ровно два различных простых делителя, больших $n$ само $m$ и, возможно, ещё один простой делитель числа $m^2+1$

Ответ

Главная идея

Разложить $m^3+m = m(m^2+1)$ и взять $m$ наименьшим простым числом, большим $n$ Тогда множитель $m$ даёт ровно один большой простой делитель, а все большие простые делители $m^2+1$ не меньше $m+1$ — двух таких не поместится, потому что $(m+1)^2 > m^2+1$

Признаки: нужно доказать, что при любом параметре $n$ найдётся число с малым количеством простых делителей, больших $n$ Приём: разложить выражение на множители; один множитель сделать простым; выбрать его наименьшим подходящим — тогда «больше $n$ » для остальных делителей превращается в «не меньше $m+1$ »; дальше оценка размера: число, меньшее произведения двух таких простых, не может делиться на оба.

Где легко ошибиться

Проверить несколько маленьких $n$ и взять «удобное» правило вроде $m = n+1$ при $n = 17$ получаем $18\cdot 325 = 2\cdot 3^2\cdot 5^2\cdot 13$ — ни одного простого делителя больше $17$ Другая ошибка — взять любое простое $m > n$ не обязательно наименьшее: при $n = 2$ $m = 13$ выходит $13\cdot 170 = 2\cdot 5\cdot 13\cdot 17$ — три больших делителя, потому что делитель $5$ числа $m^2+1$ больше $n$ но меньше $m$ и оценка через $(m+1)^2$ не работает.

Источник и авторство

Олимпиада имени Леонарда Эйлера · XVII олимпиада, сезон 2024/25 · заключительный этап · второй день · 24–27 марта 2025 · математика · 8 класс. Официальная задача 5, 7 баллов.

Материалы этапа (ZIP организатора) ↗ · Архив олимпиады ↗

Условие — из официального файла организатора. Подсказки, объяснение и модели — Popov Academy. Авторский разбор Popov Academy проверен; результат сопоставлен с официальными материалами.

Продолжить тему: Делимость и простые множители →

Тема, знания и приёмы

Делимость и простые множители · Начальный вход

Разложение натурального числа на простые множители
Если число делится на два различных простых числа, то оно делится и на их произведение
Простых чисел бесконечно много
Остаток от деления m^2 + 1 на m равен 1 (при m > 1)

Приёмы решения: Разложение на множители · Оценка и достижимость · Обоснованный жадный выбор

Задать вопрос по задаче →