теория - Докажите утверждение

Прежде всего, из условия, что $%2^n-1$% делится на $%2^m-1$%, следует, что $%n$% делится на $%m$%. Чтобы в этом убедиться, достаточно поделить $%n$% на $%m$% с остатком: $%n=mq+r$%; $%0\le r < m$%. Тогда $%2^n=(2^m)^q\cdot2^r$%, и коль скоро $%2^m$% при делении на $%2^m-1$% даёт в остатке $%1$%, то это же верно и для $%(2^m)^q$%, в результате чего оказывается, что не только $%2^n-1$%, но и $%2^r-1$% делится на $%2^m-1$%. Из условия $%r < m$% сразу ясно, что $%r=0$%, то есть $%n=mq$%.

Теперь можно записать $$2^n-1=(2^m)^q-1=(2^m-1)((2^m)^{q-1}+(2^m)^{q-2}+\cdots+2^m+1).$$ Делимость $%2^n-1$% на $%(2^m-1)^2$% равносильна делимости второго сомножителя на $%2^m-1$%. Заменяя в этом сомножителе $%2^m$% числом $%1$%, то есть остатком от деления на $%2^m-1$%, мы получаем вместо второго сомножителя сумму $%q$% единиц, которая также должна делиться на $%2^m-1$%. То же рассуждение работает и в обратную сторону. Отсюда $%n=mq$% делится на $%(2^m-1)^2$%.

Это рассуждение выглядело бы ещё проще, если излагать его на языке сравнений. Тогда мы бы сказали, что $%2^m\equiv1\pmod{2^m-1}$% с последующим возведением этого сравнения в степени.