2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Найдите все такие составные числа
Сообщение13.02.2019, 21:40 
Аватара пользователя


01/12/11

8634
Найдите все такие составные числа $n$, что для любого разложения на два натуральных сомножителя $n=xy$ сумма $x+y$ является степенью двойки с натуральным показателем.

 Профиль  
                  
 
 Re: Найдите все такие составные числа
Сообщение14.02.2019, 09:58 
Заслуженный участник
Аватара пользователя


13/08/08
14430
По необходимости это непростые числа Мерсенна. Первое подходящее $15$. Следующее $63$ уже не подходит, так как $3+21=24$. Наверное, надо копаться в разложениях бинома на множители?

 Профиль  
                  
 
 Re: Найдите все такие составные числа
Сообщение15.02.2019, 01:01 


15/03/11
137
gris в сообщении #1375945 писал(а):
По необходимости это непростые числа Мерсенна. Первое подходящее $15$. Следующее $63$ уже не подходит, так как $3+21=24$. Наверное, надо копаться в разложениях бинома на множители?


Если рассмотреть числа вида $2^{2k}-1$. Они делятся на 3. Обозначим сумму $a_{k} = \frac{2^{2k}-1}{3}+3$.
$a_{k+1} = \frac{2^{2(k+1)}-1}{3}+3=2^{2k}+\frac{2^{2k}-1}{3}+3$=2^{2k}+a_k
Так как $a_3 = 24$ не делится на 16, то и последующие $a_k$ тоже не делятся на 16 и при этом заведомо больше 16. Следовательно они никак не могут быть степенями двойки. Следовательно числа вида $2^{2k}-1$ для $k>2$ можно исключить.

 Профиль  
                  
 
 Re: Найдите все такие составные числа
Сообщение16.02.2019, 00:43 
Заслуженный участник


03/01/09
1677
москва
Пусть $p$- нечетное. $x,y$ являются решениями уравнения: $x+\dfrac {2^p-1}x=2^n$ или $x^2-2^nx+2^p-1=0.$ Решения этого уравнения: $x,y=2^{n-1}\pm \sqrt {2^{2(n-1)}-2^p+1}$ натуральные числа только если $2^{2(n-1)}-2^p+1=N^2$ ,где $N$ имеет вид :$ N=2^lq\pm 1, l\geq 1,q\geq 1$- нечетное.

$N^2-1=2^{2l}q^2\pm 2^{l+1}q$, очевидно $N^2-1$ делится на $2^{l+1}$ и не делится на бо'льшую степень двойки. Отсюда следует, что $N=2^{p-1}q\pm 1$(так как $N^2-1$ делится на $2^p$ и не делится на $2^{p+1}$).

Будем считать $x>y$, тогда из формулы для $x,y$получим: $x=2^{n-1}+2^{p-1}q\pm 1,x+y>x>2^{p-1}$ и, следовательно, $x+y=2^p$. Это возможно только если $2^p-1$ - простое, но по условию оно составное.

 Профиль  
                  
 
 Re: Найдите все такие составные числа
Сообщение17.02.2019, 13:57 


26/08/11
2057
mihiv в сообщении #1376342 писал(а):
только если $2^{2(n-1)}-2^p+1=N^2$ ,где $N$ имеет вид :$ N=2^lq\pm 1, l\geq 1,q\geq 1$-
На самом деле $2^{2a}-2^b+1$ будет квадратом только в трех случаях: $b=0,b=a+1,b=2a$

Если $b\in [1;a]$, то $(2^a-1)^2<2^{2a}-2^b+1<(2^a)^2$

Если $b\in (a+1;2a)$

$2^{2a}-2^b+1=N^2$

$(N-1)(N+1)=2^b(2^{2a-b}-1)$ Один из сомножителей левой части делится на $2^{b-1}$ (другой на 2, но не на 4). А значит

$N+1\ge 2^{b-1}$. Тогда $N-1\ge 2^{b-1}-2$ И левая часть

$N^2-1\ge 2^{2(b-1)}-2^b$, что больше $2^{2a}-2^b$

И если вернутся к задаче, можно рассмотреть два случая - $b=a+1$ и $b=2a$ - все просто получается.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group