Найдите все такие составные числа

[Ktina]

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

[gris]

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

[zhekas]

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$ можно исключить.

[mihiv]

Пусть $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$ - простое, но по условию оно составное.

[Shadow]

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$ - все просто получается.