Разделы 
Дополнительно
Задача по математике - 1514
2019-01-19 
Даны натуральные числа $m$ и $n$. Докажите, что число $2^n - 1$ делится на число $(2^m - 1)^2$ тогда и только тогда, когда число $n$ делится на число $m(2^m - 1)$.
Решение:
Из равенства
$2^{kn} - 1 = (2^n - 1)(2^{n(k-1)} + 2^{n(k-2)} + \cdots + 1)$
следует, что $2^kn - 1$ делится на $2^n - 1$, поэтому $2^{kn+d}-1 = 2^{kn+d} - 2^d + 2^d -1 = 2^d(2^{kn} - 1) + 2^d - 1 = 2^d - 1 (mod 2^n -1)$. Таким образом $2^n - 1$ делится на $2^m - 1$ тогда и только тогда, когда $n$ делится на $m$. Если $n = km$, то
$ \frac {2^{km} - 1}{2^m - 1} = 1 + 2^m + \cdots + 2^{m(к - 1)}$.
Каждое слагаемое дает остаток 1 при делении на $2^m - 1$, поэтому
$ \frac{2^{km} - 1}{2^m - 1} \equiv k (mod 2^m - 1)$,
Поэтому $2^{km} - 1$ делится на ${(2^m - 1)}^2$ тогда и только тогда, когда $k = \frac {n}{m}$ делится на $2^m - 1$, что равносильно тому, что $n$ делится на $m(2^m - 1)$.
Даны натуральные числа $m$ и $n$. Докажите, что число $2^n - 1$ делится на число $(2^m - 1)^2$ тогда и только тогда, когда число $n$ делится на число $m(2^m - 1)$.
Решение:
Из равенства
$2^{kn} - 1 = (2^n - 1)(2^{n(k-1)} + 2^{n(k-2)} + \cdots + 1)$
следует, что $2^kn - 1$ делится на $2^n - 1$, поэтому $2^{kn+d}-1 = 2^{kn+d} - 2^d + 2^d -1 = 2^d(2^{kn} - 1) + 2^d - 1 = 2^d - 1 (mod 2^n -1)$. Таким образом $2^n - 1$ делится на $2^m - 1$ тогда и только тогда, когда $n$ делится на $m$. Если $n = km$, то
$ \frac {2^{km} - 1}{2^m - 1} = 1 + 2^m + \cdots + 2^{m(к - 1)}$.
Каждое слагаемое дает остаток 1 при делении на $2^m - 1$, поэтому
$ \frac{2^{km} - 1}{2^m - 1} \equiv k (mod 2^m - 1)$,
Поэтому $2^{km} - 1$ делится на ${(2^m - 1)}^2$ тогда и только тогда, когда $k = \frac {n}{m}$ делится на $2^m - 1$, что равносильно тому, что $n$ делится на $m(2^m - 1)$.
