пара простых p,q с условием: p | (1+q^2) и q | (1+p^2)

[maxal]

Пусть простые $p<q$ таковы, что $p|(1+q^2)$ и $q|(1+p^2)$.

Докажите или опровергните, что оба они являются числами Фибоначчи: $p=F_r$ и $q=F_{r+2}$ для некоторого $r$ (причем $r$ и $r+2$ - это простые близнецы).

[Руст]

Условие $m|1+n^2,n|1+m^2$ эквивалентно условию $mn|1+m^2+n^2$ или $m^2-kmn+n^2=-1,k>2$. Случай $k=3$ приводит к корням чисел Фибоначчи. Но ведь есть и другие значения k. Поэтому скорее всего это не верно.

[maxal]

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

Случай $k=3$ приводит к корням чисел Фибоначчи. Но ведь есть и другие значения k.

Какие, например?

[Руст]

Решим уравнение $m^2-kmn+n^2=-1$.
$(2m-kn)^2-An^2=-4, \ A=k^2-4$. Отсюда получаем, что -1 квадрат по модулю А. Так как квадрат не равен $3\mod 4$, число $k$ нечётно и все простые делители числа $A=(k-2)(k+2)$ имеют вид $1\mod 4$. Если $k$ не делится на 3, то число $A$ делится на 3 - что недопустимо. Поэтому $k=3(2l+1)$. л=9 не годится, так как А=7*11 имеет разложение на простые 3\mod 4.
k=15 даёт $A=13*17$ годится. Соответственно найдутся решения уравнения Пелля. Только насчёт простых решений заранее трудно сказать.

[maxal]

Нет, Рустем, ты ошибаешься. Предлагаю доказать, что:

во-первых, $k=15$ не работает, то есть, что уравнение $m^2-15mn+n^2=-1$ неразрешимо в целых числах;

и

во-вторых, уравнение $m^2-kmn+n^2=-1$ неразрешимо в целых числах вообще ни для какого целого $k>3$.

[Sonic86]

Уравнение $p^2-kpq+q^2=-1$ аналогично уравнению Пелля.
Осмелюсь утверждать, что решается оно аналогично.
То есть если $x_1 , y_1$ - наименьшие по абсолютной величине числа такие, что
$(x_1- \sqrt{k}y_1)(x_1+ \sqrt{k}y_1)=-1$, то все его решения $x_n , y_n$ находятся из
$(x_1+ \sqrt{k}y_1)^n = x_n+ \sqrt{k}y_n$. При это $n$ нечетно, чтобы $(-1)^n=-1$.
Выражая $x_n , y_n$ через $x_1 , y_1$ получаем, что $x_n$ делится на $x_1$, а
$y_n$ делится на $y_1$. Если потребовать, чтобы $x_n , y_n$ были простыми,
то необходимо, чтобы $x_1 = y_1 = 1$, откуда $k=-3$, а $x_n , y_n$ - числа Фибоначчи.

А уравнение вроде разрешимо

[maxal]

Sonic86 писал(а):

Уравнение $p^2-kpq+q^2=-1$ аналогично уравнению Пелля.
Осмелюсь утверждать, что решается оно аналогично.
То есть если $x_1 , y_1$ - наименьшие по абсолютной величине числа такие, что
$(x_1- \sqrt{k}y_1)(x_1+ \sqrt{k}y_1)=-1$,

Прежде всего, если такие $x_1, y_1$ существуют (а ведь могут и не существовать).
Кроме того, вы решаете другое уравнение: $x^2 - k' y^2 = -1,$ которое получается из исходного только при четном $k$. Причем $k' = (k/2)^2 - 1,$ $x=p-(k/2)q$ и $y=q.$

Sonic86 писал(а):

то все его решения $x_n , y_n$ находятся из
$(x_1+ \sqrt{k}y_1)^n = x_n+ \sqrt{k}y_n$. При это $n$ нечетно, чтобы $(-1)^n=-1$.
Выражая $x_n , y_n$ через $x_1 , y_1$ получаем, что $x_n$ делится на $x_1$, а
$y_n$ делится на $y_1$. Если потребовать, чтобы $x_n , y_n$ были простыми,
то необходимо, чтобы $x_1 = y_1 = 1$, откуда $k=-3$, а $x_n , y_n$ - числа Фибоначчи.

Значение $x_n$ не является в точности значением $p$ или $q$ в исходном уравнении, а поэтому вывод о том, что $x_1=1$ неверен.
Кроме того, даже если бы это было так, то получается $k'=2$ (а не $k'=-3$), но это значение не соответствует никакому исходному $k$.

Sonic86 писал(а):

А уравнение вроде разрешимо

Погадаем на кофейной гуще?
"Вроде" - не аргумент.

[Руст]

Да не проверял по архимедовой норме.
Так как кольцом целых чисел $Q[\sqrt A]$ является $Z[\frac{1+\sqrt A}{2}]$, то найдём в этом кольце образующую группы единиц. Легко доказать, что образующая $\epsilon=\frac{k+\sqrt A}{2}$.
Искомое равенство эквивалентно нахождению в этом кольце элемента с нормой -1. Если имеется такой элемент а, то $a^2=\epsilon ^k$. Умножая элемент на $\epsilon^{-(k-1)/2}a=b$ получаем $b^2=\epsilon$. Если $b=\frac{r+s\sqrt A}{2}$ (r,s - целые одинаковой чётности), то получаем $rs=1\to k=\frac{r^2+As^2}{2}=\frac{1+A}{2}\to k^2-3=2k\to k=3.$

[maxal]

Вот задачка посложнее: найдите такие пары простых чисел $p,q$, что $p|(1+q^3)$ и $q|(1+p^3).$

[Руст]

Задача аналогичная и сводится к $pq|(1+p+q)(1-p-q+p^2+q^2)$. Только зачем ограничиваться простыми числами. Это необходимо разве чтобы количество решений было конечно. Но только доказать конечность совсем не просто, как и в первом случае.

[maxal]

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

Задача аналогичная и сводится к $pq|(1+p+q)(1-p-q+p^2+q^2)$. Только зачем ограничиваться простыми числами.

Для простых чисел все немного проще Задача сводится к делимости $pq|(1-p-q+p^2+q^2).$

[Руст]

maxal писал(а):

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

Задача аналогичная и сводится к $pq|(1+p+q)(1-p-q+p^2+q^2)$. Только зачем ограничиваться простыми числами.

Для простых чисел все немного проще Задача сводится к делимости $pq|(1-p-q+p^2+q^2).$

Однако $2*3\not |1-2-3+2^2+3^2=9$. То, что единственное исключение для простых знал и раньше.

[maxal]

Ну да, это единственное исключение. Кроме того, я написал "сводится", а не "эквивалентна" - сведение здесь, в частности, подразумевает и отбрасывание указанного тривиального случая.

Добавлено спустя 2 минуты 24 секунды:

Кстати, далее $1-p-q+p^2+q^2=kpq$ можно привести к почти однородной форме:

$$kxy - x^2 - y^2 = (k-2)(k-1)$$

или

$$(k-2)xy - (x-y)^2 = (k-2)(k-1),$$

где $x=(k-2)p+1$ и $y=(k-2)q+1.$

Если такие простые $p,q$ существуют, оба они должны быть больше $10^9$.

[maxal]

maxal писал(а):

Задача сводится к делимости $pq|(1-p-q+p^2+q^2).$

Если кому-то интересно, решение этой задачи (и ее обобщений) представлено в статье:

W. H. Mills "A system of quadratic Diophantine equations." Pacific J. Math. Volume 3, Number 1 (1953), 209-220.

Статья не выходит за рамки элементарной математики (доступной для понимания школьникам), но результаты получаются очень красивые. Я прочитал с удовольствием.

[maxal]

Нашел у себя некий черновой текст датированный июлем 2007 года, в котором я решал похожую задачу (возможно, для форума Mathlinks, так как текст на английском). Какую именно задачу я решал и почему этот текст так и остался недописанным - уже не помню (может, в нем ошибка?), но чтобы добро не пропадало, помещаю его тут:

Цитата:

Our goal is to find all solutions to the following system of divisibilities:
$x|(y^2+y+1)$
$y|(x^2+x+1)$

First, notice that if $x|(y^2+y+1)$ and $y|(x^2+x+1)$, then for $z=(x^2+x+1)/y$ we have $x|(z^2+z+1)$ and trivially $z|(x^2+x+1)$. Indeed,

$$0 \equiv 0\cdot z^2 \equiv (y^2+y+1)\cdot z^2 \equiv (((x^2+x+1)/z)^2+(x^2+x+1)/z+1)\cdot z^2 \equiv (x^2+x+1)^2+(x^2+x+1)\cdot z+z^2 \equiv 1+z+z^2 \pmod x.$$

Therefore, if we have a solution $(x,y)$, then $((y^2+y+1)/x,y)$ and $(x,(x^2+x+1)/y)$ are solutions as well. Call a solution "minimal" if $x\leq (y^2+y+1)/x$ and $y\leq (x^2+x+1)/y$. Any solution can be obtained from a minimal solution with a finite series of operations

$$(x,y)\quad\longrightarrow\quad ((y^2+y+1)/x,y)$$

$$(x,y)\quad\longrightarrow\quad (x,(x^2+x+1)/y)$$

Let us focus on finding all minimal solutions.

$(1,1)$ is obviously a minimal solution. Moreover, it is the only solution with $x=y$.
It is easy to check that there are no other minimal solutions with $x\leq 2$.

Let $(x,y)$ be a minimal solution with $2<x<y$. Then $y\leq \sqrt{x^2+x+1}$ and

$$x^2+3x+3 = (x+1)^2+(x+1)+1 \leq y^2+y+1 \leq (x^2+x+1)+\sqrt{x^2+x+1}+1 < (x^2+x+1)+(x+1)+1 = x^2+2x+3.$$

This inequality is impossible meaning that there are no other minimal solutions.
...

Как видим, идея решения очень похожа на описанную в статье Миллса. Еще немного и я бы переоткрыл его результат.