Делимость

[nnosipov]

Найдите все пары $(x,z)$ целых чисел, для которых число $2(z+1)^3$ делится на число $xz-1$.

[nnosipov]

Здесь есть по крайней мере два разных подхода к решению, каждый из которых приводит к разбору конечного числа случаев. Было бы интересно выписать сам ответ. Насколько он окажется громоздким?

[maxal]

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

Найдите все пары $(x,z)$ целых чисел, для которых число $2(z+1)^3$ делится на число $xz-1$.

Случай, когда $xz-1$ делит $(z+1)^3$, похож на эту задачу: topic47908.html

Пусть $t=xz-1$. Тогда $\gcd(t,z)=1$ и $tz\mid ((z+1)^3+t)$. Положим $f(t,z)=\tfrac{(z+1)^3+t}{tz}$.
Нетрудно видеть, что если $(t,z)$ решение, то $(t',z')$ - тоже решение, где $z'=f(t,z)$ и $t'= \frac{(z'+1)^3}{zz'-1}$.
Более того, $(t'',z'')=(t,z)$.

Решения $(t,z)$ и $(t',z')$ совпадают только, когда $f(t,z)=z$, что дает $(x,z)=(5,2), (3,3), (2,5)$.
Все остальные решения разбиваются на пары, где без потери общности будем считать, что $z'>z$. Это неравенство равносильно $z=1$ или $z>1$ и $t < \tfrac{(z+1)^2}{z-1}$. Отсюда получаем ограничения: $x=1$ или $x>1$ и $z\leq 5$. Перебором находим решения:
$x=1$, $z=2,3,5,9$ и соответствующие им парные решения: (9,14), (5,11), (3,11), (2,14);
$z=1$, $x=2,3,5,9$ и соответствующие им парные решения: (14,9), (11,5), (11,3), (14,2);
и парные (2,2) с (5,5).

Что делать, когда присутствует множитель 2 перед $(z+1)^3$, пока не придумал.

[maxal]

С 2-кой можно поступить так. Заметим, что $xz-1$ также делит $2(x+1)^3$. Обозначим $d=\gcd(x+1,z+1)$ и положим $x+1=du$ и $z+1=dv$. Тогда $xz-1=d^2uv - du - dv$ делит $2\gcd((x+1)^3,(z+1)^3)=2d^3$. Следовательно, $duv - u - v$ делит $2d^2$, а значит и $2d^2uv = 2d(duv - u - v) + 2d(u+v)$. Поэтому $duv - u - v$ делит $2d(u+v)$.

В частности, имеем $duv - u - v \leq 2d(u+v)$ или $duv \leq (2d+1)(u+v)$. Отсюда получаем $uv \leq 3(u+v)$ или $(u-3)(v-3)\leq 9$. Без потери общности можно считать, что $u\leq v$ (причем равенство возможно только для $u=v=1$) и поэтому $u\leq 5$. Получаем конечный перебор, для которого сначала заметим, что делимость $duv - u - v\mid 2d(u+v)$ влечет делимость $duv - u - v\mid 2du^2 + 2(u+v)$, откуда $(du-3)v \leq (2du+3)u$.

Перебор распадается на два базовых случая:

1) $du\leq 3$
В этом случае $x=1$ или $x=2$
Для $x=1$, получаем $z=2,3,5,9,17$
Для $x=2$, получаем $z=1,2,5,14$

2) $du\geq 4$, что влечет $v \leq 11 u$
Здесь просто перебраем $u$ и $v$, и находим подходящие $d$ из условия $duv-u-v$ делит $2(u+v)^2$.
Небольшая программка дает все пары $(x,z)$ с условием $x\leq z$:

? for(u=1,5, for(v=u,11*u, if(gcd(u,v)>1,next); fordiv(2*(u+v)^2,t, if((t+u+v)%(u*v)==0, d = (t+u+v)/(u*v); print([d*u-1,d*v-1])) )))
[2, 2]
[3, 3]
[5, 5]
[9, 9]
[1, 3]
[2, 5]
[5, 11]
[1, 5]
[3, 11]
[11, 35]
[1, 9]
[2, 14]
[5, 29]
[1, 17]
[3, 43]
[1, 2]
[9, 14]
[29, 69]

[nnosipov]

maxal, большое спасибо, надо будет осмыслить Ваш текст.

В более общей постановке задача выглядит так: для данных $f(y)=ay^3+by^2+cy+d$ и $g(x,y)=Axy+Bx+Cy+D$ найти все пары $(x,y)$ целых чисел, для которых $f(y)$ делится на $g(x,y)$. Алгоритм решения этой задачи у меня есть, но интересны различные его версии. Скорее всего, Ваши рассуждения будут пригодны и в общем случае.