Когда $p \mid q^3-1$ и $q \mid p-1$

[nnosipov]

Предлагаю подумать над следующей несложной и уже довольно старой задачей.

Пусть $p$ и $q$ --- натуральные числа, большие $1$. Известно, что $q^3-1$ делится на $p$, а $p-1$ делится на $q$. Докажите, что $p=q^{3/2}+1$ или $p=q^2+q+1$.

Различных способов доказать это утверждение довольно много, но вдруг кто-нибудь придумает что-нибудь экзотическое.

[Руст]

Упустили еще один случай $p=1$ (тоже натуральное число).

[nnosipov]

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

Упустили еще один случай $p=1$ (тоже натуральное число).

Нет, Руст, не упустил, я его исключил

[Sonic86]

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

Упустили еще один случай $p=1$ (тоже натуральное число).

И $q=1$ при любом $p$ тоже. Но это понятно...

-- Пн июл 18, 2011 17:38:18 --

Решил в лоб. Получилось как обычно с одним интересным для меня местом:
$q|p-1 \Leftrightarrow p=1+kq$. Тогда нужно найти все $k,q: \frac{q^3-1}{1+kq} \in \mathbb{Z}$
$q^3 \equiv 1 \pmod{1+kq} \Leftrightarrow$
$q^3 \equiv -kq \pmod{1+kq} \Leftrightarrow$
$q^2 \equiv -k \pmod{1+kq} \Leftrightarrow$
$q^2 \equiv -k+k(1+kq) \pmod{1+kq} \Leftrightarrow$
$q^2 \equiv k^2q \pmod{1+kq} \Leftrightarrow$
$q \equiv k^2 \pmod{1+kq}$
Исключая случай $k=0$ получаем оценку:
$\frac{q^3-1}{1+kq} \in \mathbb{Z} \Rightarrow 1 \leq k \leq q^2-1$
Из последнего сравнения имеем $\frac{q-k^2}{1+kq} \in \mathbb{Z} \Rightarrow |q-k^2| \leq 1+kq \Rightarrow k^2 \leq 1+kq+q$.
Делаем по принципу сжимающих отображений.
Используя первую оценку сверху, получаем:
$k \leq q^{3/2}+1$
Используя теперь эту оценку, получаем
$k \leq q^{5/4}+1$
И т.п. В итоге $k \leq q+1$.
Случай $k=q+1$ дает $p=q^2+q+1$. В противном случае $k \leq q$ и тогда $k^2 < 1+kq$ - модуля сравнения, откуда $q=k^2$ - сравнение удовлетворяется и получается 2-я серия решений.

[nnosipov]

Sonic86 в сообщении #469316 писал(а):

Делаем по принципу сжимающих отображений.

Вот она экзотика! Ладно, буду читать.

-- Пн июл 18, 2011 20:15:00 --

Sonic86 в сообщении #469316 писал(а):

... $\frac{q-k^2}{1+kq} \in \mathbb{Z} \Rightarrow |q-k^2| \leq 1+kq$

Вот здесь неравенство в другую сторону должно быть (числитель дроби $q-k^2$ по абсолютной величине не меньше знаменателя $1+kq$, а не наоборот).

[Sonic86]

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

Sonic86 в сообщении #469316 писал(а):

Делаем по принципу сжимающих отображений.

Вот она экзотика! Ладно, буду читать.

-- Пн июл 18, 2011 20:15:00 --

Sonic86 в сообщении #469316 писал(а):

... $\frac{q-k^2}{1+kq} \in \mathbb{Z} \Rightarrow |q-k^2| \leq 1+kq$

Вот здесь неравенство в другую сторону должно быть (числитель дроби $q-k^2$ по абсолютной величине не меньше знаменателя $1+kq$, а не наоборот).

Блин, фигню написал.
Перерешал, "экзотика" пропала, зато правильно, проверьте:

$\frac{q-k^2}{1+kq} \in \mathbb{Z} \Rightarrow |q-k^2| \geq 1+kq$
$\Rightarrow q+k^2 \geq 1+kq \Leftirghtarrow$
$q(1-k) \geq 1-k^2 \Leftirghtarrow$
$k=1 \vee q \leq k+1$
Получили то же самое. Случай $k=1$ дает одно решение.

[nnosipov]

Sonic86 в сообщении #469423 писал(а):

Получили то же самое.

Да нет, сейчас Вы получили $q \leqslant k+1$, а раньше было $k \leqslant q+1$. И что дальше делать, непонятно.

[Sonic86]

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

Sonic86 в сообщении #469423 писал(а):

Получили то же самое.

Да нет, сейчас Вы получили $q \leqslant k+1$, а раньше было $k \leqslant q+1$. И что дальше делать, непонятно.

Да, опять ошибка.
Сейчас получили $k \geqslant q-1$. Тогда при $q \geqslant 3 \Rightarrow k^2 \geqslant q$, поэтому можем раскрыть модуль в неравенстве:
$k^2-q \geqslant 1+kq \geqslant 1+(q-1)q \Leftrightarrow k^2 \geqslant q^2+1 \Rightarrow k \geqslant q+1$.
Вернемся к $q \equiv k^2 \pmod{1+kq}$:
$\Leftrightarrow q-q(1+kq) \equiv k^2 \pmod{1+kq} \Leftrightarrow$
$kq^2 + k^2 \equiv 0 \pmod{1+kq} \Leftrightarrow$
$q^2 + k \equiv 0 \pmod{1+kq} \Rightarrow$
$q^2 + k \geqslant 1+kq \vee q^2+k=0$. 2-й случай невозможен. Мы знаем, что $q^2>k$, тогда зажимаем $k$:
$2q^2 > 1+kq \Leftrightarrow 2q>k$.
Снова подставляем:
$q^2 + 2q > 1+kq \Leftrightarrow q + 2 > k$
Снова подставляем:
$q^2 + q + 2 > 1+kq \Leftrightarrow q + 1 > k \Leftrightarrow q + 2 \geqslant k$
Снова подставляем:
$q^2 + q + 2 \geqslant 1+kq \Leftrightarrow q + 1 \geqslant k$
Вот в итоге и получили: $k=q+1$

Серию $k=q^{1/2}$ я потерял при рассуждении $\frac{a}{b} \in \mathbb{Z} \Rightarrow a \geqslant b$ - на самом деле надо $\frac{a}{b} \in \mathbb{Z} \Rightarrow a \geqslant b \vee a=0$. Для дроби $\frac{k^2-q}{1+kq}$ это уже точное рассуждение и дает 2-ю серию решений.

[nnosipov]

Теперь всё окей. Несколько сумбурно, но правильно.

(Оффтоп)

Это была задача М1787, Квант, 2001, 5.

[Sonic86]

(Оффтоп)

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

Теперь всё окей. Несколько сумбурно, но правильно.

Ура-ура!

[maxal]

Просьба указывать источники задач - в данном случае http://www.artofproblemsolving.com/Foru ... 59&t=64244

[nnosipov]

maxal в сообщении #469571 писал(а):

Просьба указывать источники задач - в данном случае http://www.artofproblemsolving.com/Foru ... 59&t=64244

Конечно, нужно указывать источники, целиком поддерживаю. Выше есть, правда в оффтопе, поэтому и не заметили (Квант, 2001, 5-й номер).

[maxal]

Понятно, я написал на AOPS про этот источник. Пока там фигурировало в качестве источника MOSP 2004.