Представление чисел в виде (2^a-1)(2^b-1)/((2^c-1)(2^d-1))

[Руст]

Докажите, что для любого нечётного натурального числа n существуют натуральные числа a,b,c,d, что имеет место представление:

$$n=\frac{2^a-1}{2^b-1}\frac{2^c-1}{2^d-1}.$$

[juna]

Много не думал, но... Можно увидеть подобное представление, например, для числа 11 или 31. Для $n=11$ $a=10k, k=1,2,...$. Ясно, что речь идет о представлении числа композицией четырех сумм геометрических прогрессий, но сокращения должны быть какими-то хитрыми.

[Руст]

Какие суммы геометрических прогрессий? Попробуйте разъяснить на примере: $13=\frac{2^{12}-1}{2^6-1}\frac{2^2-1}{2^4-1}.$

[juna]

$2^{12}-1=3^3*5*7*13$ - и сводится к представлению предыдущих.
Случай, который я просил рассмотреть $n=11$, в минимальном представлении $2^{10}-1=1023=3*11*31$, $2^{31}-1$ - вообще простое число - не сводится к представлению предыдущих, или можно доказать, что когда-то сведется?

[Руст]

Простые числа Мерсена легче всего представить: $\frac{2^p-1}{2^1-1}\frac{2^k-1}{2^k-1}.$

[juna]

А почему Вы не отвечаете на вопрос: $11=\frac{2^a-1}{2^b-1}\frac{2^c-1}{2^d-1}$, найти $(a,b,c,d)$. Я не вижу возможности такого представления.
Или это проливает свет на идею самого доказательства?

[Руст]

$$11=\frac{2^{10}-1}{2^5-1}\frac{2^1-1}{2^2-1}.$$

[Sasha2]

Руст писал(а):

$$11=\frac{2^{10}-1}{2^5-1}\frac{2^1-1}{2^2-1}.$$

Ну Вы, уважаемый Руст, хоть наводку дайте типа хватит ли тут знаний элементарной математики, чтобы решить эту задачу или не стоит даже приниматься?

[juna]

Да просто здесь все должно быть, это я торможу. Если $n$ - нечетно, то по теореме Ферма $n|2^{n-1}-1$. С другой стороны $2^{n-1}-1=(2^{\frac{n-1}{2}}-1)(2^{\frac{n-1}{2}}+1)$. Это помогает сокращать множители содержащиеся в $2^{\frac{n-1}{2}}-1$.

[Руст]

Вообще эта задача из mathlinc. И мне его прислал один китаец. У меня возникли подозрения, что это неверно. Когда выставил в форум, я ещё не знал решения. Сейчас могу доказать, что не любое нечётное число можно так представить. Но пока не нашёл, какое минимальное число не представимое в таком виде. Возможно таким числом является 19.

[juna]

Опа! А я был уверен в чистоте формулировки. Посмотрел на http://www.mathlinks.ro/Forum/viewtopic.php?t=64527
Прикольно, один участник тоже грешил на 11, хотя тривиально 31 на единицу отстоит от степени двойки.
Для 19 имеем в числителе $2^{18}-1=3^3*7*19*73$ и представлению в указанной форме мешает $3^3$, которое само в такой форме представимо $3^3=\frac{2^2-1}{2^3-1}\frac{2^6-1}{2^1-1}$, поэтому нужно сделать что-то типа такого $19=\frac{2^{18}-1}{2^9-1}\frac{2^3-1}{2^2-1}\frac{2^1-1}{2^6-1}$. Вообще было бы интересно найти форму чисел не представимых указанной формой.

[maxal]

Рассмотрим простое число Мерсенна $2^{17}-1=131071$.
По его модулю существует $17$ различных чисел вида $2^a - 1$. Количество различных чисел вида $(2^a-1)(2^b-1)$ не превосходит $\frac{17(17+1)}{2}=153$. А количество чисел вида $\frac{(2^a-1)(2^b-1)}{(2^c-1)(2^d-1)}$ не превосходит соответственно $153^2=23409$. Но среди первых $131070$ натуральных чисел имеется $65535$ нечетных чисел, поэтому не все они могут быть представлены в указанном виде.

На компе получилось, что 19 по модулю 131071 не представимо в таком виде, что доказывает гипотезу Рустема.

[juna]

Это, пожалуй, доказывает, что для представления $\prod\limits_{i=1}^{K}\frac{2^{a_i}-1}{2^{b_i}-1}$ при ограниченном $K$ всегда существуют числа не представимые этой формой.

[Руст]

В начале я тоже был уверен, что задача корректная. Этот китаец выбрал задачи обычно из предложенных в нацилнальных олимпиадах. После безуспешной попытки доказать это появилось сомнение в справедливости. Как только закралась мысль о несправедливости утверждения, нашёл доводы, аналогичные, предложенному maxal ом (количество представимых должна расти медленно). Проще всего доказать не представимость $2^{11}-1=23*89$ , когда требуется отделить собственный делитель числа вида $2^p-1$, не являющегося простым числом Мерсена. Очевидно, что их нельзя разделить, так как одно из чисел (например а) в числителе должна делиться на р. Далее, если другие не делятся простые сомножители не разделяются. Они не разделяются и в случае, когда и другие числа (b,c,d) делятся на р. Таким образом, когда $2^p-1$ не простое, то ни один из собственных делителей не представим в таком виде. После начал искать минимальное не представимое таким образом число (меньше 23). Таким числом оказалось 19, только доказать сложнее.
Это доказывает и гипотезу Артамонова Ю.Н. Указанного вида числа нельзя разделить никаким конечным набором отношений.
Хотя числа вида 19 можно $19=\frac{2^{18}-1}{2^9-1}\frac{2^3-1}{2^6-1}\frac{2^1-1}{2^2-1}.$

[juna]

19 представимо формой при $K=3$, а какое минимальное непредставимое для $K=3, 4, 5, ...$
Было бы интересно получить эту цепочку, может так закономерности есть. Сейчас, к сожалению, нет времени.