Question

Пусть k— натуральное число, а m— нечетное число. Докажите, что существует натуральное число n такое, что n^n - m делится на 2^k

Answer 1

Случай $k=1$ тривиален, возьмем $n=1$. Предположим, что существует натуральное число $n$ такое, что $2^k|n^n-m$, скажем, $n=n_0$ или имеем $2^k|n_0^{n_0}-m$ и, очевидно, $n_0$ нечетно

Рассмотрим два случая

1. Если $2^{k+1}$ делит $n_0^{n_0}-m$

утверждение ясно, потому что нам нужно только взять $n = n_0$.

2. Если $2^{k+1}$ не делит $n_0^{n_0}-m$.

Мы можем положить $n_0^{n_0}-m=u\cdot 2^k$ с нечетным числом $u$ и по теореме Эйлера, для каждого нечетного числа $a$ мы имеем $a^{2^{k}}\equiv 1\pmod{2^{k+1}}$, следовательно, мы имеем

$(2^k+n_0)^{2^k+n_0}-m=(2^k+n_0)^{2^k}\cdot (2^k+n_0)^{n_0}-m\equiv (2^k+n_0)^{n_0}-m\\\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\cdot 2^k -m=(u+n_0^{n_0})2^k\equiv 0\pmod{2^{k+1}}$

потому что и $u$, и $n_0$ нечетны.

Следовательно, $n=2^k+n_0$ удовлетворяет утверждению