Найти наибольший общий делитель

[fiztech]

Найдите

$(2^{32}+1,2^{16}+1)$

[gris]

$(4294967297, 65537)$
Если Вы имели в виду gcd, то 1. Они взаимно просты.

[fiztech]

gris

имеется ввиду без калькулятора, используя формулы

[gris]

Или $(2^{32}+1.2^{16}+1)$?
Вот в таких случаях видишь, почему десятичная точка предпочтительней запятой.
Зачем тогда скобки? Поясните задание.
Кстати, обижаете. Никакого калькулятора. А Вы степени двойки до какой помните наизусть?

[fiztech]

gris

в задании больше ничего не написано кроме того, что я написал. Скобки там стоят .

[arseniiv]

Ищите соответствующий контекст выше.

[_Ivana]

(Оффтоп)

Оно?

[fiztech]

gris

Имеется ввиду решить задачу без тупого счета степеней.

[mihailm]

Без счета так: числа в скобках из неудачной гипотезы Ферма, первое вообще как известно простое, второе тоже широко известно, простой множитель у него нашел Эйлер, очевидно это не $2^{16}+1$, иначе его бы еще Ферма нашел бы. Значит скобка равна единице)

[gris]

Понятно. То есть надо найти наибольший общий делитель. Это же числа Ферма. Второе простое, а первое составное, но точно на второе не делится. А как это всё показать, я не знаю. В теории чисел слаб.

mihailm, классное доказательство

[Shadow]

Вобщем, доказать что $x^2+1 \text { и } x+1$ взаимнопросты при четном х

[Someone]

Просто разделить первое на второе как многочлены и посмотреть на остаток. Даже устно считается.

[Whitaker]

fiztech
Если Вы знаете есть такие числа, называемые числами Ферма $F_n=2^{2^n}+1$.
В Вашем случае $F_5=2^{2^5}+1=2^{32}+1$ и $F_4=2^{2^4}+1=2^{16}+1$
Есть такое полезное утверждение:
Любые два различных числа Ферма взамно просты.
Т.е. нам нужно доказать, что $\text{gcd}(F_n, F_{n+k})=1$ при $n\in \mathbb{N}$ и $k>0$
Давайте докажем от противного. Пусть $\text{gcd}(F_n, F_{n+k})=d>1$
Введем число $x=2^{2^n}$ и рассмотрим отношение:

$$\dfrac{F_{n+k}-2}{F_n}=\dfrac{x^{2^k}+1-2}{x+1}=\dfrac{x^{2^k}-1}{x+1}=x^{2^k-1}-x^{2^k-2}+\dots-1$$

Но выражение справа число целое. Значит, $F_n\mid F_{n+k}-2$, но так как $d\mid F_n$, то $d\mid F_{n+k}-2$. Кроме того, $d\mid F_{n+k}$, то отсюда $d\mid 2$. Имеем, что $d=1$ или $d=2$. Так как $d>1$, то отсюда $d=2$. Но $d\neq 2$, так как числа Ферма нечетные. Противоречие.
Значит, $\text{gcd}(F_n, F_{n+k})=1$ при $k>0$
Вам понятно?

[ИСН]

Whitaker, Вы запредельно глубоко влезаете в частности. А вообще-то тут чем более общо, тем проще - см. сообщение Shadow.

[Whitaker]

ИСН
Я всего лишь показал ТС, что различные числа Ферма вазимно просты. Хотя согласен, что утверждение Shadow более общо.