$2^n+3^n$ делится на $n^2$

[nnosipov]

Найдите четыре натуральных числа $n$, меньших 2000000 и таких, что $2^n+3^n$ делится на $n^2$.

С компьютером это нисколько не интересно, а вручную, по-моему, занятно. Прошу попробовать.

[paha]

nnosipov
а источник можете указать?

[nnosipov]

paha в сообщении #390348 писал(а):

nnosipov
а источник можете указать?

Это, так сказать, собственного приготовления. Свои задачи ведь сюда помещать можно?

[paha]

nnosipov в сообщении #390368 писал(а):

Свои задачи ведь сюда помещать можно?

нужно:)))

[Руст]

Первое решение $n_0=1$.
Если $n>1$ то оно нечетное и не делится на 3.
Пусть $p$ минимальный простой делитель числа $n$. Для него существует минимальное значение a(p), что $p|2^{a(p)}+3^{a(p)}$ и $a(p)|n$. Так как p минимальное, то $a(p)=1\to p=5.$
Действительно проверяется $n_1=5$ решение.
Для следующего простого делителя получаем $p|2^5+3^5=275=11*5^2$.
Следовательно следующее решение $n_2=5*11$.
Далее по индукции. Находим для предыдущего решения простой делитель
$p_{i+1}|\frac{2^{n_i}+3^{n_i}}{n_i^2}.$
Соответственно находим следующее решение $n_{i+1}=p_{i+1}n_i$.
При этом уже в шаге $p_3|\frac{2^{55}+3^{55}}{55^2}$ может появится несколько возможностей, в том числе возможно деление на куб одного из предыдущих простых. Таким образом получаются все решения.

[nnosipov]

Руст в сообщении #390394 писал(а):

Первое решение $n_0=1$.
Если $n>1$ то оно нечетное и не делится на 3.
Пусть $p$ минимальный простой делитель числа $n$. Для него существует минимальное значение a(p), что $p|2^{a(p)}+3^{a(p)}$ и $a(p)|n$. Так как p минимальное, то $a(p)=1\to p=5.$
Действительно проверяется $n_1=5$ решение.
Для следующего простого делителя получаем $p|2^5+3^5=275=11*5^2$.
Следовательно следующее решение $n_2=5*11$.
Далее по индукции. Находим для предыдущего решения простой делитель
$p_{i+1}|\frac{2^{n_i}+3^{n_i}}{n_i^2}.$
Соответственно находим следующее решение $n_{i+1}=p_{i+1}n_i$.
При этом уже в шаге $p_3|\frac{2^{55}+3^{55}}{55^2}$ может появится несколько возможностей, в том числе возможно деление на куб одного из предыдущих простых. Таким образом получаются все решения.

А как Вы думаете, сколько всего решений?

[Simba]

nnosipov в сообщении #390396 писал(а):

А как Вы думаете, сколько всего решений?

по-моему, бесконечно много (если без ограничения меньше 2000000), при $n=5^k$, доказать можно по индукции.

[nnosipov]

Simba в сообщении #391036 писал(а):

nnosipov в сообщении #390396 писал(а):

А как Вы думаете, сколько всего решений?

по-моему, бесконечно много (если без ограничения меньше 2000000), при $n=5^k$, доказать можно по индукции.

Конечно, решений бесконечно много, но я имел в виду те, которые в пределах первых двух миллионов. Однако при $n=5^k$ они не получаются, можете сами убедиться, взяв, например, $k=2,3,4,5$.

[Руст]

До 2000000 точно 4 решения $1,5,55,1971145$ так как минимальный простой делитель числа $\frac{2^{55}+3^{55}}{55^2}$ есть $35839$.
На самом деле для любого делителя d ( не обязательно простого) $\frac{2^{n_i}+3^{n_i}}{n_i^2}$ решением является так же $dn_i$.
Соответственно бесконечную серию решений можно указать по простой рекурентной формуле
$n_0=1,n_{i+1}=\frac{2^{n_i}+3^{n_i}}{n_i}.$