Областная олимпиада по математике, 2023 год, 11 класс

Найдите все пары натуральных чисел $m$ и $n > 2$, для которых число $\frac{m^n+1}{n}$ — простое.

Комментарий/решение

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

$n>1$

заметим что это можно поставить так $m^n=pn-1$ заметим что $n \equiv 0 \pmod {4}$ не может и заметим что $p\ne 4k+3$ (по теореме Жерара) пусть теперь $n=2d$ где $k$ нечет и $p=4k+1$ $\Rightarrow$ $(m^d-1)(m^d+1)=2(4kd+d-1)$ легко понять что $d=1$откуда $8k=(m-1)(m+1)$ откуда $(k=3,m=5),(m=3,k=1)$$\Rightarrow (n,p,m)=(2,13,5);(2,5,3)$

теперь у нас $n=4k+3$ при $k\geq1 $ нет решений тогда $n=3$$\Rightarrow m=2,p=3$ если $n=4k+1$ Опять $k\geq 1 $ не может быть тогда $n=1$ и тогда для любых $m$ и $p$ но т.к. $m,n>2$ то нету решений

$p≠4k+3$ только если $n$ четное же, и почему легко понять что $d=1$?

я это написал про $p$

Чтобы решить эту проблему, мы воспользуемся тем фактом, что если p — простой множитель (m^n+1)/n, то p либо равно n, либо имеет вид 2kn+1, где k — натуральное число.

Во-первых, давайте рассмотрим случай, когда n простое число. В этом случае мы знаем, что n делит m ^ n - 1 (по малой теореме Ферма). Таким образом, мы имеем:

м^п + 1 = (м^п - 1) + 2

(м^п + 1)/п = [(м^п - 1)/п] + 2/п

Поскольку n простое число, оно не делит m^n - 1, и, следовательно, n делит (m^n + 1)/2. Это означает, что любой простой множитель (m^n + 1)/n должен быть либо равен n, либо иметь вид 2kn+1.

Теперь давайте рассмотрим случай, когда n составное. Пусть p — простой множитель числа n. У нас есть:

м ^ п ≡ -1 (по модулю р)

м ^ (2n) ≡ 1 (mod p)

Следовательно, порядок m по модулю p равен либо n, либо 2n. Если это n, то имеем:

м ^ п ≡ -1 (по модулю р)

(м ^ п + 1)/п ≡ 0 (по модулю р)

В противном случае порядок m по модулю p равен 2n, и мы имеем:

м ^ (2n) ≡ 1 (mod p)

(м ^ п) ^ 2 ≡ 1 (по модулю р)

(m ^ n + 1) (m ^ n - 1) ≡ 0 (mod p)

Поскольку p является фактором n, мы имеем:

(м ^ п + 1)/п ≡ 0 (по модулю р)

Следовательно, любой простой множитель (m^n + 1)/n должен быть либо равен n, либо иметь вид 2kn+1, где k — натуральное число.

Теперь давайте рассмотрим случай, когда n является степенью числа 2, скажем, n = 2^k. В этом случае имеем:

м ^ (2 ^ к) + 1 = (м ^ (2 ^ (к-1)) + 1) (м ^ (2 ^ (к-1)) - 1) + 2

Так как 2 делит n, мы имеем:

(m ^ (2 ^ k) + 1)/n = [(m ^ (2 ^ (k-1)) - 1)/n][(m ^ (2 ^ (k-1))) + 1) /2]

Обратите внимание, что (m^(2^(k-1))) + 1)/2 — нечетное целое число, и, следовательно, любой простой множитель (m^(2^(k-1))) + 1)/2 должно иметь вид 2kn+1, где k — натуральное число. Точно так же любой простой множитель (m ^ (2 ^ (k-1))) - 1) / n должен быть либо равен n, либо иметь форму 2kn + 1.

Следовательно, любой простой множитель (m^n + 1)/n должен быть либо равен n, либо иметь вид 2kn+1, где k — натуральное число. Поскольку n > 2, должен быть хотя бы один простой делитель n, больший 2. Следовательно, любая пара (m, n), удовлетворяющая условию, должна иметь n вида 2^k или простого числа.

В случае, когда n является степенью числа 2, мы можем использовать аналогичный аргумент, чтобы показать, что любой простой множитель (m ^ n - 1)/n должен быть либо равен n, либо иметь форму 2kn+1, где k равно а