Диофантово уравнение для составных чисел

[Sonic86]

Докажите, что для заданного натурального $n$ уравнение $(n-x-y)^2=4xy+1$ имеет решение в натуральных числах тогда и только тогда, когда $n$ составное число.

[Руст]

Решение имеется всегда. Рассмотрим $n$-нечетное. Тогда $x+y=2m$ четное и $x=m+r,y=m-r$. Соответственно
$m=\frac{n^2+4r^2-1}{4n}.$ Это число целое, если $n|4r^2-1$, так как делимость числителя на 4 следует из нечетности $n$. Например серия решений при $n=3$ получается $x=\frac{r^2+3r+2}{3},y=\frac{r^2-3r+2}{3}$ и $r$ пробегает натуральные числа $r>1, 3\not |r$.
Аналогично в четном случае.

[Sonic86]

Да, спасибо, действительно.
А я кажется забыл условие $n-x-y>0$ . Что будет в этом случае?

[nnosipov]

Тогда при простом $n$ решений в натуральных числах не будет (это несложно). А для составных нужно подумать.

[Руст]

Для нечетного $n$ это означает, что $|r|<\frac n2$ и в случае простоты нет решения. А в случае составности есть.
Для четного это верно если исключить решения типа $n=2m,x=2m-1,y=0$ (когда выполняется ограничение, но нарушается натуральность у в русском понимании).

[nnosipov]

Для некоторых составных $n$ нет решений в русских натуральных числах $x$, $y$ с условием $x+y<n$. Описать такие $n$ --- простая ли это задача?

Если $n$ --- степень простого числа, то тоже нет решений. А иначе вроде как есть.

[Руст]

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

Для некоторых составных $n$ нет решений в русских натуральных числах $x$, $y$ с условием $x+y<n$. Описать такие $n$ --- простая ли это задача?

Если $n$ --- степень простого числа, то тоже нет решений. А иначе вроде как есть.

Описать просто. Имеется решение $x+y<n, x\ge 1, y\ge 1$ тогда и только тогда, когда $n\not =1,p^k.$

[nnosipov]

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

Описать просто.

Это я уже сделал выше. А доказать?

[Руст]

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

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

Описать просто.

Это я уже сделал выше. А доказать?

Рассмотрю только нечетное $n$, общее решение которой привел выше:

$$x=m+r,y=m-r,m=\frac{n^2+4r^2-1}{4n}.$$

Условие $n>x+y$ эквивалентно $2r<n$. Остается найти такое $2r$, что $(2r)^2=1\mod n$. Случай $2r=n-1$ приводит к $y=0$. Поэтому в нечетном случае ограничение $y=m-r>0\to n^2+4r^2-1-4nr>0\to (n-2r)^2>1$ дает $2r<n-1$. Других ограничений нет. Отсюда следует для $n=p^k,1$ для нечетных $n$.
Пусть $n=n_1n_2$ разложение на два взаимно простые нечетные множители. Тогда существует $a=1\mod n_1, a=-1\mod n_2, 1<a<n-1.$ Если $a$ четное принимаем $2r=a$, иначе $r=\frac{n-a}{2}$.
Аналогично разбирается четный случай. Количество решений в точности равен $2^{v(n)-1}-1$, где $v(n)$ количество простых делителей (это количество разбиений $v(n)$ на два непустых подмножеств).

[nnosipov]

Sonic86, откуда эта задача? Такое ощущение, что раньше её где-то видел.

[Sonic86]

Отсюда выделил: topic50511.html (и там по ссылке)

[nnosipov]

Ну что же, получилась вполне содержательная задача, хотя и несложная. В "Задачнике Кванта" вполне смотрелась бы.

[Sonic86]

(Оффтоп)

Жалко, что не получилось уравнение, задающие числа, свободные от квадратов. Для этого пришлось бы писать 2 уравнения. Ну да ладно, хоть так...