Мой вариант решения был, возможно такой, как предложен выше.
В двоичной системе последние 4 цифры для 3^m будут повторяться:
0011
1001
1011
0001
Что очевидно при прибавлении единицы никогда не даст все нули. Поэтому и не будет никогда равно 2^n ни при каких m и n > 1.
Аналогичные закономерности существуют для всех простых чисел, а не только для 3.
Для тех случаев, где закономерности не очевидны, можно отталкиваться от того, что у двоичной записи любого простого числа в любой степени больше 1 есть 0. При умножении такого числа на само себя никогда не избавит нас от этого 0. А для того, чтобы результат стал равен степени двойки при прибавлении 1, нужно чтобы все цифры были единицы, чего нет.
