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

Определите все тройки натуральных чисел $(m, n, k)$ такие, что $(m^n - 1)$ делится на $k^m$ и $(n^m - 1)$ делится $k^n$. ( Сатылханов К. )

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

Ответ:$(m,n,k)=(a,b,1),(1,1,c),\forall a,b,c\in\mathbb N$

Лемма 1: $\forall a>b\geq 3$ верно неравенство $a^b<b^a$ $(a,b\in\mathbb N)$

Лемма 2: Если $m^2>2^m$ то $m=3$ $(m\in\mathbb N)$

При $k=1$, утверждение задачи верно для $\forall m,n\in\mathbb{N}$, далее $k>1$.

Если $n=1$ и $m\neq 1$, то $k^m\mid m-1 \implies 2^m\leq k^m\leq m-1$, что невозможно. Значит $n=1 \iff m=1$, далее $m,n>1$

Если $n=2$, то $k^m\mid m^2-1$ откуда $2^m\leq k^m\leq m^2-1$, откуда $m=3$, но тогда $k\mid 7$ и $k\mid 8$, что неверно, далее пусть $m,n>2$

Пусть простое число $p\mid k$, тогда $p^m\mid m^n-1$ и $p^n\mid n^m-1$, откуда $(m,p)=(n,p)=1$.

По теореме Ферма-Эйлера $p^m\mid m^{φ(p^m)}-1=m^{p^{m-1}(p-1)}-1$.

Пусть $d$-показатель числа $m$ по модулю $p^m$. Тогда $d\mid n$ и $d\mid p^{m-1}(p-1)$, но $(p,n)=1$, значит $d\mid p-1$, откуда $p^m\mid m^{p-1}-1$.Заметим, что $m^p>m^{p-1}-1\geq p^m$.

Если $p\geq 3$, то $m<p$, аналогично $n<p$.Пусть $m\geq n$, откуда $n^m\geq m^n$, но $p^m\leq m^n-1$, т.к. $p^m\mid m^n-1$, следовательно $n^m\geq m^n>p^m$, значит $p>n>p$ противоречие.

Значит $p=2$, откуда $2^m\leq m-1$ т.к. $2^m\mid m-1$, что невозможно.