WikiSort.ru - Не сортированное

n = 61

Случай n = 61 (поиск решения уравнения ${\displaystyle a^{2}-61b^{2}=1}$ ), которое было вызовом Ферма много веков позже, Бхаскара дал как пример^[10].

Мы начинаем с решения ${\displaystyle a^{2}-61b^{2}=k}$ для любого k, найденного произвольным способом. Мы можем взять b равным 1 и, поскольку ${\displaystyle 8^{2}-61\cdot 1^{2}=3}$ , мы получим тройку ${\displaystyle (a,b,k)=(8,1,3)}$ . Скомбинируем её с тройкой ${\displaystyle (m,1,m^{2}-61)}$ , что даст ${\displaystyle (8m+61,8+m,3(m^{2}-61))}$ , а после понижения (по лемме Бхаскара^[en])

${\displaystyle \left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).}$

Чтобы 3 делило ${\displaystyle 8+m}$ , а ${\displaystyle |m^{2}-61|}$ было минимальным, выбираем ${\displaystyle m=7}$ , так что получим тройку ${\displaystyle (39,5,-4)}$ . Теперь имеем k = −4 и мы можем воспользоваться идеей Брахмагупты — тройка может быть сведена к рациональному решению ${\displaystyle (39/2,5/2,-1)\,}$ , которое затем комбинируется с собой три раза с ${\displaystyle m={7,11,9}}$ соответственно, пока k не станет квадратом и мы не сможем произвести понижение. Это даёт ${\displaystyle (1523/2,195/2,1)}$ . Такая процедура может быть повторена, пока не получим решение (требуется 9 дополнительных комбинаций и 4 дополнительных квадратичных понижений) ${\displaystyle (1766319049,\,226153980,\,1)}$ . Это минимальное целое решение.

n = 67

Пусть нужно решить уравнение ${\displaystyle x^{2}-67y^{2}=1}$ ^[11]

Начинаем с решения уравнения ${\displaystyle a^{2}-67b^{2}=k}$ для k, найденного любым способом. Мы можем взять b равным 1, что даёт ${\displaystyle 8^{2}-67\cdot 1^{2}=-3}$ . На каждой итерации ми находим m > 0, такое, что k делит a + bm и |m² − 67| минимально. Затем мы обновляем a, b и k на ${\displaystyle {\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}}$ .

Первая итерация

Мы имеем ${\displaystyle (a,b,k)=(8,1,-3)}$ . Нам нужно положительное целое m, такое что k делит a + bm, то есть 3 делит 8 + m. Нам нужно также, чтобы при этом значение |m² − 67| было минимальным. Из первого условия следует, что m имеет вид 3t + 1 (то есть m = 1, 4, 7, 10,… и т.д.), а среди таких значений m, минимальное значение получается при m = 7. Заменяя (a, b, k) на ${\displaystyle \left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}\right)}$ , получим новые значения ${\displaystyle a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6}$ . То есть, мы имеем новое решение

${\displaystyle 41^{2}-67\cdot (5)^{2}=6.}$

Вторая итерация

Повторяем процесс. Мы имеем ${\displaystyle (a,b,k)=(41,5,6)}$ . Нам нужно m > 0, такое, что k делит a + bm, то есть 6 делит 41 + 5m. Нам при этом нужно, чтобы |m² − 67| было минимальным. Из первого условия следует, что m имеет вид 6t + 5 (то есть m = 5, 11, 17,… и т.д.), а среди таких чисел m минимум |m² − 67| достигается на m = 5. Это приводит нас к новому решению a = (41⋅5 + 67⋅5)/6, и т.д.:

${\displaystyle 90^{2}-67\cdot 11^{2}=-7.}$

Третья итерация

Для того, чтобы 7 делило 90 + 11m, m должно иметь вид m = 2 + 7t (то есть, 2, 9, 16,… и т.д.). Среди таких m выбираем m = 9.

${\displaystyle 221^{2}-67\cdot 27^{2}=-2.}$

Конечное решение

Мы можем продолжать итерации (и закончим после семи итераций), но поскольку правая часть находится среди чисел ±1, ±2, ±4, мы можем использовать напрямую наблюдение Брахмагупты. Скомбинируем тройку (221, 27, −2) с собой, мы получим

${\displaystyle \left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,}$

То есть мы имеем целое решение:

${\displaystyle 48842^{2}-67\cdot 5967^{2}=1.}$

Это решение является приближением ${\displaystyle {\sqrt {67}}}$ в виде ${\displaystyle {\frac {48842}{5967}}}$ , в котором ошибка находится в пределах ${\displaystyle 10^{-9}}$ .