Простая математическая задачка?

Предлагаю вашему вниманию простую математическую задачу.


Нужно доказать, что при любых натуральных m, n > 1 выполняется неравенство:


3^m + 1 <> 2^n


Вместо 3 в общем случае может быть любое простое число.


Ответ опубликую завтра, кому будет интересно. Решение в несколько строк без всяких премудростей.
  • Вопрос задан
  • 4865 просмотров
Пригласить эксперта
Ответы на вопрос 8
@Otkrick
(2^n mod 8) = 0, когда (3^m+1) mod 8 c {2,4}
* мелочь руками отбросить
Ответ написан
@xaoc80
Доказать можно по индукции. Если верно это неравенство для какого-то натурального k, то требуется лишь доказать его верность для k + 1
И так, предположим, что неравенство верно для некого m. Тогда для m + 1 получим 3*3^m <> 2^n — 1. Если бы 3^m было равно 2^n — 1, то получили бы 3 == 1. А это не так
Ответ написан
barker
@barker
первое, что пришло в голову:
3^m+1 <> 2^n
=>
3^m <> 2^n-1
2^n-1 — простое число (см числа мерсена), а 3^m, очевидно, нет.
Ответ написан
@avrelian
Доказательство общего случая p^m + 1 <> 2^n
1) Предположим, что m — нечетое. Тогда после разложения полинома в левой части один из множителей окажется нечетным числом (не обязательно простым). При любом n это число не может появиться в правой части.
2) Предположим, что m — четное.
2.1) Рассмотрим случай четного n. После переноса p^m в правую часть и разложения на множители получим в правой части (2^(n/2) — p^(m/2)) * (2^(n/2) + p^(m/2)), что явно не может быть равно единице в левой части.
2.2) Рассмотрим случай нечетного n. Добавим к левой и правой части 2 * p^(m/2). В левой части получится квадрат (p^(m/2) + 1)^2, а в правой части 2 * (2^(n-1) + p^(m/2)), то есть левая часть делится на квадрат двойки, а правая, только на 2.
Ответ написан
@rainwall
Правая часть всегда четная.
Левая часть всегда нечетная, т.к.:
3^m+1=(2+1)^m+1 При разложении через бином ньютона получаем сумму степени двойки умноженную на биноминальный коэффициент. т.е. четное число. к нему прибавляем единицу и получаем нечетное.
Ответ написан
StanSemenoff
@StanSemenoff Автор вопроса
Мой вариант решения был, возможно такой, как предложен выше.
В двоичной системе последние 4 цифры для 3^m будут повторяться:
0011
1001
1011
0001
Что очевидно при прибавлении единицы никогда не даст все нули. Поэтому и не будет никогда равно 2^n ни при каких m и n > 1.

Аналогичные закономерности существуют для всех простых чисел, а не только для 3.
Для тех случаев, где закономерности не очевидны, можно отталкиваться от того, что у двоичной записи любого простого числа в любой степени больше 1 есть 0. При умножении такого числа на само себя никогда не избавит нас от этого 0. А для того, чтобы результат стал равен степени двойки при прибавлении 1, нужно чтобы все цифры были единицы, чего нет.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы