2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Найти наибольший общий делитель
Сообщение31.10.2012, 21:50 
Аватара пользователя
Найдите

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

 
 
 
 Re: Найти число
Сообщение31.10.2012, 21:55 
Аватара пользователя
$(4294967297, 65537)$
Если Вы имели в виду gcd, то 1. Они взаимно просты.

 
 
 
 Re: Найти число
Сообщение31.10.2012, 21:58 
Аватара пользователя
gris

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

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

 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:04 
Аватара пользователя
gris

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

 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:06 
Ищите соответствующий контекст выше.

 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:07 

(Оффтоп)


 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:11 
Аватара пользователя
gris

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

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

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

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

 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:41 
Вобщем, доказать что $x^2+1 \text { и } x+1$ взаимнопросты при четном х

 
 
 
 Re: Найти число
Сообщение31.10.2012, 22:42 
Аватара пользователя
Просто разделить первое на второе как многочлены и посмотреть на остаток. Даже устно считается.

 
 
 
 Re: Найти число
Сообщение01.11.2012, 00:20 
Аватара пользователя
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$
Вам понятно?

 
 
 
 Re: Найти число
Сообщение01.11.2012, 09:44 
Аватара пользователя
Whitaker, Вы запредельно глубоко влезаете в частности. А вообще-то тут чем более общо, тем проще - см. сообщение Shadow.

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group