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

Question

[StanSemenoff]

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


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


3^m + 1 <> 2^n


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


Ответ опубликую завтра, кому будет интересно. Решение в несколько строк без всяких премудростей.

Comments

[Eddy_Em]

А что такое "<>"? Это "!=" или нечто эдакое, особенное?

[StanSemenoff]

Да, <> означает не равно, эквивалент !=

Answer 1

[Otkrick]

(2^n mod 8) = 0, когда (3^m+1) mod 8 c {2,4}
* мелочь руками отбросить

Comments

[iLexx_13]

Интересное решение, а почему именно 8?

И еще при m=> 34 (3^m+1) mod 8 = 0.
Хотя возможно мой калькулятор сломался)))

[StanSemenoff]

А как быть, когда вместо 3 любое простое число?

[Otkrick]

iLexx_13,

сломался у вас калькулятор

(3^34+1)/8 = 16677181699666570/8 = 2084647712458321.25

см. машинное эпсилон

[Otkrick]

iLexx_13, а у вас не Windows ли?

[iLexx_13]

Otkrick,
Нет, у меня убунту…
но считал так.
Спасибо про «машинное эпсилон».

[Otkrick]

StanSemenoff, обе функции возрастающие(без точек перегиба) => могут пересекаться в одной точке, которая пролетает по условию m,n>1

[StanSemenoff]

Не очень понятна фраза «обе функции».
Функция одна F(a, m, n) = a^m + 1 — 2^n
И про нее нельзя сказать, что она возрастающая или убывающая, есть ли у нее перегибы или нет. Это какое-то множество чисел.
И вопрос, а есть ли среди них 0?

[Otkrick]

0 не входит, иначе точек было бы две: + M2(1,0) для тройки, например. Нет функции F(a,m,n). Для каждого a, f(m)=a^m+1 и g(n)=2^n…

[StanSemenoff]

Изменим постановку:
пусть левая часть теперь будет не 3^m+1, а 4^m.
Очевидно, что задача будет иметь бесконечное число решений, т.е. комбинаций (m, n) при которых 4^m = 2^n.

Как трактовать тогда фразу «обе функции возрастающие(без точек перегиба) => могут пересекаться в одной точке, которая пролетает по условию m,n>1»?
Как это фраза что-то доказывает или ничего не доказывает?

Answer 2

[AJ]

42

Answer 3

[oleg1977]

3^1+1=2^2?

Comments

[Константин Власов]

m,n>1

Answer 4

[Андрей]

Доказать можно по индукции. Если верно это неравенство для какого-то натурального k, то требуется лишь доказать его верность для k + 1
И так, предположим, что неравенство верно для некого m. Тогда для m + 1 получим 3*3^m <> 2^n — 1. Если бы 3^m было равно 2^n — 1, то получили бы 3 == 1. А это не так

Answer 5

[barker]

первое, что пришло в голову:
3^m+1 <> 2^n
=>
3^m <> 2^n-1
2^n-1 — простое число (см числа мерсена), а 3^m, очевидно, нет.

Comments

[Константин Власов]

2^n-1 — простое число

Дык не при любых же n. 2^4-1=15 — никак не простое.

[barker]

ой, вот я тупанул, вообще не так понял чо надо))

Answer 6

[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.

Answer 7

[rainwall]

Правая часть всегда четная.
Левая часть всегда нечетная, т.к.:
3^m+1=(2+1)^m+1 При разложении через бином ньютона получаем сумму степени двойки умноженную на биноминальный коэффициент. т.е. четное число. к нему прибавляем единицу и получаем нечетное.

Comments

[rainwall]

хотя это не так

Answer 8

[StanSemenoff]

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

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

Comments

[jcmvbkbc]

у двоичной записи любого простого числа в любой степени больше 1 есть 0. При умножении такого числа на само себя никогда не избавит нас от этого 0

Это место вовсе не очевидно. Например умножение 110011 (есть нули) на 101 (есть нули) даёт 11111111 (нет нулей).

[StanSemenoff]

Тут четкое доказательство я еще не выработал, но суть в том, что при умножении числа на само себя мы от 0 не избавляемся (т.е. для квадрата числа это очевидно). Так же не избавляемся и при многократном умножении на себя (возведении в степень, это уже менее очевидно, но оно так). В вашем случае идет умножение разных чисел 51 * 5, что безусловно может избавлять от нулей.