Республиканская олимпиада по математике, 2019 год, 11 класс

Найдите все натуральные $n$, $k$, $a_1, a_2,\ldots, a_k$ такие, что $n^{k+1}+1$ делится на $(na_1+1)(na_2+1)\ldots(na_k+1)$. ( Ануарбеков Т. )

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

Решение можете посмотреть на данном сайте в разделе математика:

Республика 2019

Пусть $s=\frac{n^{k+1}+1}{(na_1+1)(na_2+1)...(na_k+1)}$, тогда $s\equiv 1 \pmod n$, но $s<\frac{n^{k+1}+1}{n^{k}}<n+1$.

Следовательно, $s=1$ и $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)$.

Если $k=1$, мы сразу получаем $a_{1}=n$.

Если $k=2$, мы получаем $n^{3}+1=\left(na_{1}+1\right)\left(na_{2}+1\right)$, что эквивалентно $na_ {1}a_{2}+a_{1}+a_{2}=n^{2}$.

Итак, $n|a_{1}+a_{2}$ и $a_{1}a_{2}<n$, поэтому $\left(a_{1},a_{2}\right)=(1,n -1),(n-1,1)$.

Теперь предположим, что $k\geq 3$.

Если $n=1$, то мы легко видим, что дальнейших решений нет.

Если $n=2$, то $k<4$, поэтому $k=3$. Мы легко видим, что решений нет. Теперь предположим, что $n\geq 3$.

Мы легко видим $\left(1+\frac{1}{n}\right)^{n^2}>n$, поэтому $n^{n^{2}+1}<\left(n+1 \right)^{n^{2}}$. Следовательно, $k<n^{2}$.

Если существует $3$ различных $i$ таких, что $a_{i}=1$, то $\left(n+1\right)^3|n^{k+1}+1$.

Нетривиальными операциями получаем $\left(n+1\right)^2|k+1$, что означает $k\geq n^2+2n$. Итак, противоречие!

Следовательно, существует хотя бы $k-2$ различных $i$ таких, что $a_{i}\geq 2$.

Если $k\geq 5$, мы легко видим, что $a_{1}a_{2}\cdots a_{k}\geq a_{1}+a_{2}+\cdots a_{k}$.

Когда мы оцениваем обе стороны $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)$, тогда $n|a_{1} +a_{2}+\cdots a_{k}$.

Это означает, что $a_{1}a_{2}\cdots a_{k}\geq n$.

Но тогда $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)>n^{k}a_{1}a_{2} \cdots a_{k}+1\geq n^{k+1}+1$, противоречие.

$n|a_{1}+a_{2}+\cdots a_{k}$ и $a_{1}a_{2}\cdots a_{k}< n$ применимо к остальным случаям $k=3$, $k=4$ тоже.

Если $k=3$, то $n+1\not|n^{4}+1$, следовательно, $a_{i}\geq 2$ для всех $i$. Итак, мы легко видим, что решения нет.

Если $k=4$, то после грязной работы мы видим, что решения нет.

Следовательно, решения: $\boxed{k=1,a_{1}=n}$ и $\boxed{n\geq 2,k=2,\lbrace{a_{1},a_{2}\rbrace}= \lbrace{1,n-1\rbrace}}$