Помогите разобраться с доказательством утверждения

[ragnarek]

На ютубе вышел перевод двухсерийного выпуска Numberphile о задаче № 6 из математической олимпиады 1988 года. Условие гласит, что если выражение $ab+1$ делит выражение $a^2+b^2 без остатка при целых и не отрицательных $a$ и $b$, то результатом деления будет квадратное число.
Первая часть
Вторая часть

В приведенных видео якобы приводится доказательство. Однако на мой взгляд доказательства тут нет. Приводится только способ найти закономерности для пар чисел.
В связи с чем вопрос - есть ли тут доказательство? И если нет, то не мог бы кто привести его в корректной форме?

Также вдогонку следующие вопросы:
1) о каком скрытом измерении графика функции идет речь? Где об этом можно почитать и зачем об этом вообще упоминалось в видео?
2) зачем нужны прыжки Виета, если в приведенном построении графика для случая 4 график при положительных значениях является прямой линией, и такой результат как 8 и 30 и последующие можно увидеть и без прыжков?
3) как школьники могли построить этот график? Откуда они знали как он выглядит?

[mihaild]

Нет, доказательства нет (и, видимо, не планировалось).
Доказательство есть, например, в википедии.

[ragnarek]

mihaild
Это доказательство я видел, но хотелось бы ответов по теме.

[ragnarek]

Друзья, неужели никто не поможет?

[wrest]

ragnarek в сообщении #1354263 писал(а):

Друзья, неужели никто не поможет?

Прыжки Виета, как я понимаю, тут вот при чем.

Пусть мы нашли какое-то решение $x$ уравнения $(x^2+b^2)/(xb+1)=4$ В видео находится решение сначала $x=0$, затем $x=2$.
Переписываем уравнение в виде $x^2-4bx+(b^2-4)=0$, и мы нашли один корень, допустим $x_1=2$.
По формулам (теореме) Виета, произведение корней квадратного уравнения равно свободному члену, то есть $x_1x_2=(b^2-4)$ то есть $x_2=\dfrac{b^2-4}{x_1}$ Также, по теореме Виета сумма корней равна коэффициенту при первой степени неизвестного, взятому с обратным знаком, то есть $x_1+x_2=4b$ и соответственно $x_2=4b-x_1$
Подставляем одно в другое и получаем $\dfrac{b^2-4}{x_1}=4b-x_1$ Подставляя туда $x_1=2$ и решая относительно $b$ получаем $b=8$, и поступая так всё время, найдём всю серию решений $0,2,8,30...$ -- тут два соседних члена это решение $(a,b)$ при котором $(a^2+b^2)/(ab+1)=4$ Вот тут видимо и имеется в виду "скрытое квадратное уравнение", не знаю...

Так же, можем поискать серии решений для $(a^2+b^2)/(ab+1)=4,9,16...$

Но это не решение задачи, конечно. В задаче требуется доказать что всегда получается квадрат, а в видосе находят бесконечную серию решений для четверки, а также бесконечные серии решений для соотношений $a$ и $b$ таких как $(a=0, b=n)$; $(a=n, b=n^3)$; $(a=n^3,b=n^5-n)$ (а, не, этого в видосе нет, ну пусть будет бонус вам ) и так далее.

ragnarek в сообщении #1353829 писал(а):

если в приведенном построении графика для случая 4 график при положительных значениях является прямой линией, и такой результат как 8 и 30 и последующие можно увидеть и без прыжков?

Неа, он совсем не прямой. Это гипербола

ragnarek в сообщении #1353829 писал(а):

как школьники могли построить этот график? Откуда они знали как он выглядит?

Ну именно этот график строится легко. Мы же предполагаем что $(a^2+b^2)/(ab+1)=4$ то есть $a^2+b^2-4ab-4=0$ -- это уравнение гиперболы. Не знаю почему для этого потребовалось озарение...

P.S. Доказательство таки см. в Вики, ссылку дал ув. mihaild

[Lia]

ragnarek
Замечание за отсутствие описания видео и немотивированный подъем темы бессодержательным сообщением.

[wrest]

Кстати, вот, кажись, и все решения:

$\{0,n,n^3,n^5-n,n^7-2n^3,n^9-3n^5+n,n^{11}-4n^7+3n^3,n^{13}-5n^9+6n^5-n,...\}$
Туда подставляем $n=1,2,...$ и получаем все бесконечные серии решений (решениями являются соседние члены последовательности).
Сама последовательность строится так $a_1=0,a_2=n,a_k=n^2a_{k-1}-a_{k-2}$
Для $k=2$ выходит известная нам $0,2,8,30,112...$ и решения $(a,b)=(0,2);(2,8);(8,30);...$ и т.п.
Для $k=3$ выходит $0,3,27,240,2133,...$
Для $k=4$ выходит $0,4,64,1020,16256,...$
И так далее.

[ragnarek]

wrest
То есть получается, всё что делали участники олимпиады (если верить герою видео) - приравнивали искомое отношение к квадратному числу и, используя известные на то время уравнения Виета, находили бесконечный ряд решений? Или же они, наоборот, открыли этот способ решения на этой олимпиаде? Мне совершенно непонятно, на чем основан метод решения прыжками Виета В чем, к примеру, разница, если мы начнем решение с предположения, что искомое отношение является полным квадратом (если в условии задачи было бы написано "доказать, что это отношение не является полным квадратом").

[wrest]

ragnarek в сообщении #1354346 писал(а):

если верить герою видео)

Если верить. Я бы не верил

-- 15.11.2018, 23:38 --

ragnarek в сообщении #1354346 писал(а):

Мне совершенно непонятно, на чем основан метод решения прыжками Виета

В Википедии очень ясно написано. Что там непонятного, спросите конкретней.

[mihaild]

Метод прыжков Виета - это частный случай метода бесконечного спуска, при котором спуск осуществляется взятием второго корня какого-то квадратного уравнения, одним из корней которого является решение.

[ragnarek]

wrest в сообщении #1354354 писал(а):

В Википедии очень ясно написано. Что там непонятного, спросите конкретней.

Я и спросил. Что если бы задача звучала наоборот - "доказать, что это отношение не является полным квадратом". И тогда решение методом прыжков Виета начиналась бы с "предположим, что искомое отношение является полным квадратом". В чем ошибка? Вы уж извините, не очень хорошо подкован в математике, а разобраться хочется.

[mihaild]

ragnarek в сообщении #1354359 писал(а):

И тогда решение методом прыжков Виета начиналась бы с "предположим, что искомое отношение является полным квадратом".

Это общая схема решения методом бесконечного спуска. И собственно в статье в википедии она выписана: предполагаем, что существуют решения, не удовлетворяющее нужному свойству (т.е в вашем варианте - предположим, что отношение может оказаться полным квадратом). Тогда возьмем минимальное (в каком-то смысле) решение, не удовлетворяющие этому свойству. Если из него получится изготовить меньшее - то наше исходное предположение было неверно, и все решения нужному свойству удовлетворяют.

Доказать, что это отношение не является полным квадратом, таким (а равно любым другим) методом не получится - для решения $(0, 0)$ найти меньшее точно не получится.

[wrest]

ragnarek в сообщении #1354346 писал(а):

В чем, к примеру, разница, если мы начнем решение с предположения, что искомое отношение является полным квадратом (если в условии задачи было бы написано "доказать, что это отношение не является полным квадратом").

Такое предположение (что отношение является или не является полным квадратом) в доказательстве вообще-то не делается. Делается другое: допустим что какое-то целочисленное решение $k$ существует. Далее делается предположение, что сумма $a+b$ -- минимальная для этого $k$. Понятно, что такая минимальная сумма существует. Далее выясняется, что если (без потери общности) $a>0$, и сумма $a+b$ минимальная из возможных, то с необходимостью $b=0$ и тогда $k=\dfrac{a^2+0^2}{a\cdot 0 +1}=a^2$ то есть $k$ - полный квадрат. Фишка в том, что для минимальности суммы при $a>0$ необходимо чтобы $b=0$ а доказывается это как раз прыжками Виета: если $b \ne 0$ то находится новая минимальная сумма $a+b$ (делается т.н. "бесконечный спуск") и в итоге $b$ должно стать нулём.

Как это "работает" на примере.

Допустим, что мы нашли какое-то решение например $a=30, b=8$ и $\dfrac{30^2+8^2}{30 \cdot 8 +1}=k$
Записываем квадратное уравнение относительно $a$
$\dfrac{a^2+8^2}{a\cdot 8 +1}=k$, переписываем как $a^2-k\cdot 8 \cdot a +8^2 - k=0$
Посмотрим какие могут быть решения у него: одно решение, $a_1=30$ мы уже знаем.
Теперь формулы Виета.

Обозначим второе решение как $a_2$
Тогда, $a_1a_2=8^2-k$ и $a_1+a_2=8\cdot k$ (это как раз и есть формулы Виета), и из второго получаем, что $a_2=8 \cdot k -30$, таким образом $a_2$ - целое число. А из первого, $a_1a_2=8^2-k$ получаем что $a_1a_2<8^2$ и поскольку $a_1>8$, то следовательно $a_2<8$, то есть второй корень меньше $8$ и существует решение $\dfrac{a^2+8^2}{a\cdot 8 +1}=k$ где $a<8$ Здесь,заметьте, мы ничего не говорили о том что $k$ - полный квадрат, а только о том что $k$ - целое. Далее мы находим новое решение, оно оказывается равно $a=8,b=2$, применяем те же шаги пока $b$ не станет равно нулю (то есть пока не дойдем до пары $a=2,b=0$), а тогда $a^2=k$ и $k$ - полный квадрат. Ну это общая канва, по ходу дела надо следить за знаками, за выполнимостью делений (чтобы не было деления на ноль) и т.п.
Точно так же мы можем бесконечно "подниматься": от решения $a=30,b=8$ мы можем "подняться" к решению $b=30,a=112$ и так далее: вот об этом в видосе говорится как о "скрытой связи по параболе в третьем измерении" - это даёт нам бесконечные серии решений.
Поскольку "подниматься" мы можем начинать с любой пары $a=2,3,4...;b=0$ то так мы можем получить вообще все решения. Ну конечно, надо еще рассмотреть варианты:
$\dfrac{a^2+b^2}{ab+1}=1$ - тут решений, очевидно, два: $a=1,b=0$ затем "поднимаемся" до $a=1,b=1$ и дальше подняться не можем (все время будет $a=b=1$)
$\dfrac{a^2+b^2}{ab+1}=0$ - тут решение одно $a=0,b=0$ и "подниматься" уже некуда, т.к. $a=b$

[ragnarek]

wrest
Большое Вам спасибо за объяснения. По поводу спуска теперь я понял - постепенно приходя к паре значений $a$ и $b$, при которой $b = 0$, мы получаем значение искомого отношения однозначно равное квадратному числу.

wrest в сообщении #1354422 писал(а):

Поскольку "подниматься" мы можем начинать с любой пары $a=2,3,4...;b=0$ то так мы можем получить вообще все решения.

Вот тут вообще круто. Теперь понятно почему это является доказательством. А вот по поводу подъема не понятно, как это делается Тут нам надо теперь подставить большее число вместо меньшего? В этом фишка?

[Otta]

wrest в сообщении #1354422 писал(а):

Такое предположение (что отношение является или не является полным квадратом) в доказательстве вообще-то не делается. Делается другое: допустим что какое-то целочисленное решение $k$ существует.

$k$ - это не решение. Решать в исходной постановке задачи особо нечего, это Вы поставили себе другую. $k$ это в точности значение отношения, и целое оно по условию, так что при доказательстве ни его целочисленность, ни существование еще раз, дополнительно не требуется. Оно есть, и это в точности эта дробь, про которую известно, что у нее целое значение. А предположение о том, что $k$ не является полным квадратом, естественно, делается: противоречие получается именно с этим предположением.

wrest
Вы вводите человека в заблуждение: к исходному доказательству Ваш текст не имеет отношения. Вы, на самом деле, пытаетесь построить все серии, на которых отношение будет целым (ну и, как следствие, квадратом).

-- 16.11.2018, 20:37 --

ragnarek
В Википедии доказательство занимает один абзац. Можно прочитать и спросить, что непонятно. Кажется, Вам предлагали.