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$ удовлетворяет утверждению

Answer 2

Для доказательства данного утверждения воспользуемся методом математической индукции.

1. Базовый случай (k = 1): Пусть k = 1, тогда нам нужно доказать, что существует натуральное число n такое, что n^n - m делится на 2. Рассмотрим два случая:

   a) Если m четное, то можно взять n = 2 и n^n - m будет делиться на 2. b) Если m нечетное, то можно взять n = 1 и n^n - m = 1 - m, что также делится на 2 (1 - m = -m, и -m делится на 2).

   Таким образом, базовый случай верен для k = 1.

2. Предположение индукции: Предположим, что для некоторого k = p (где p — натуральное число) существует натуральное число n, такое что n^n - m делится на 2^p.

3. Шаг индукции: Теперь докажем, что если утверждение верно для k = p, то оно верно и для k = p + 1.

   По предположению индукции, существует натуральное число n, такое что n^n - m делится на 2^p. Рассмотрим выражение n^(n+2) - m:

   n^(n+2) - m = n^n * n^2 - m.

   Заметим, что n^n делится на 2^p, поэтому остается только рассмотреть n^2 - m. Так как m — нечетное число (по условию), то m = 2q + 1, где q — некоторое натуральное число. Тогда:

   n^2 - m = n^2 - (2q + 1) = n^2 - 1 - 2q.

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

   a) Если n^2 - 1 делится на 2, то n^2 - 1 = 2r (где r — некоторое натуральное число). Тогда n^2 - m = 2r - 2q = 2(r - q), и это выражение делится на 2.

   b) Если n^2 - 1 не делится на 2, то можно взять n' = n * 2^p, где n' — новое натуральное число. Тогда n^2 - 1 = (n' / 2^p)^2 - 1 = (n'^2 / 2^(2p)) - 1. Заметим, что n'^2 делится на 2^(2p), а значит, и (n'^2 / 2^(2p)) делится на 2. Тогда n^2 - m = (n'^2 / 2^(2p)) - 1 - m = (n'^2 / 2^(2p)) - (2q + 1) = (n'^2 - 2^(2p)(2q + 1)) / 2^(2p). Поскольку n'^2 - 2^(2p)(2q + 1) делится на 2^(2p), то и (n'^2 - 2^(2p)(2q + 1)) / 2^(2p) делится на 2.

   Таким образом, в обоих случаях мы получаем, что n^2 - m делится на 2. Следовательно, если утверждение верно для k = p, то оно верно и для k = p + 1.

Таким образом, по принципу математической индукции, утверждение верно для любого натурального числа k и нечетного числа m.