Задача в натуральных числах: для достаточно большого фиксированного
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
найти лучшее нижнее приближение
![$\sqrt{m} \approx \sqrt{x}+\sqrt{y}\ \ (1)$ $\sqrt{m} \approx \sqrt{x}+\sqrt{y}\ \ (1)$](https://dxdy-02.korotkov.co.uk/f/9/0/5/9052a75cd2a8d25157b7023a9341ec1082.png)
. В свое время долго ломал над ней голову, но так ничего и не придумал. Вопрос немножко детский в силу простоты условия, и может быть решен перебором, но всегда ведь хочется чего-то большего. Рассмотрим три случая.
1)
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
кратно целому квадрату
![$>1.$ $>1.$](https://dxdy-04.korotkov.co.uk/f/f/3/7/f377aeb3eead2677ee5bdb4ee9e72c2d82.png)
Тогда возможно точное равенство
![$$\sqrt{a\left ( b+c \right )^2}=\sqrt{ab^2}+\sqrt{ac^2}.$$ $$\sqrt{a\left ( b+c \right )^2}=\sqrt{ab^2}+\sqrt{ac^2}.$$](https://dxdy-01.korotkov.co.uk/f/0/e/8/0e8ca8e0b48d29074597b13b372a4fec82.png)
2) Четное
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
свободно от квадратов. В этом случае решением является выражение
![$$\sqrt{4d+2} \approx \sqrt{d}+\sqrt{d+1}.$$ $$\sqrt{4d+2} \approx \sqrt{d}+\sqrt{d+1}.$$](https://dxdy-02.korotkov.co.uk/f/9/d/8/9d892a18af14c18f89a1e05074f4232d82.png)
3) Нечетное
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, свободное от квадратов. Если
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
составное, и пара
![$(x,y)$ $(x,y)$](https://dxdy-04.korotkov.co.uk/f/7/3/9/7392a8cd69b275fa1798ef94c839d2e082.png)
— решение
![$(1),$ $(1),$](https://dxdy-02.korotkov.co.uk/f/d/2/f/d2f91b812a53c2c2fa6c60f852c78dd882.png)
справедливы следующие сравнения:
![$$\left\{\begin{matrix}
(m-x)^2 \equiv 1 \mod y\\
(m-y)^2 \equiv 1 \mod x\\
(x-y)^2 \equiv 1 \mod m
\end{matrix}\right.$$ $$\left\{\begin{matrix}
(m-x)^2 \equiv 1 \mod y\\
(m-y)^2 \equiv 1 \mod x\\
(x-y)^2 \equiv 1 \mod m
\end{matrix}\right.$$](https://dxdy-01.korotkov.co.uk/f/0/4/2/04211eefa7149e105388cee38ee6ea7382.png)
В случае простого
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
выполняются похожие соотношения с той разницей, что вместо единицы в правой части сравнения оказывается некая малая величина (положительный квадратичный вычет). Для
![$m=103$ $m=103$](https://dxdy-04.korotkov.co.uk/f/f/e/6/fe67218dad8eeef5d18b032b0c1cb12a82.png)
, к примеру, имеем решение
![$\sqrt{103} \approx \sqrt{14}+\sqrt{41}$ $\sqrt{103} \approx \sqrt{14}+\sqrt{41}$](https://dxdy-01.korotkov.co.uk/f/4/b/1/4b175a5b0811dbdef87e08dcd07e651382.png)
, и выполняются сравнения
![$(103-14)^2 \equiv 8 \mod 41,\ (103-41)^2 \equiv 8 \mod 14,\ (41-14)^2 \equiv 8 \mod 103. $ $(103-14)^2 \equiv 8 \mod 41,\ (103-41)^2 \equiv 8 \mod 14,\ (41-14)^2 \equiv 8 \mod 103. $](https://dxdy-01.korotkov.co.uk/f/8/7/a/87a7121930aa07ab975036ec82840d3282.png)
Таким образом, решение предложенной задачи равносильно не только тесту на простоту, но и факторизации
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
и вряд ли предполагает простые методы. Речь скорее об алгоритмическом подходе. Что касается составного
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
— тут возможны различные методы, один из них основан на формуле сложного радикала:
пусть
![$v$ $v$](https://dxdy-03.korotkov.co.uk/f/6/c/4/6c4adbc36120d62b98deef2a20d5d30382.png)
— основание наименьшего из четных квадратов, сравнимых с единицей по
![$\mod m.$ $\mod m.$](https://dxdy-03.korotkov.co.uk/f/e/0/d/e0dd240b645a3abc3dd7f1c49b251ab782.png)
Тогда
![$x,y=\dfrac{\left ( m \pm v \right )^2-1}{4m}.$ $x,y=\dfrac{\left ( m \pm v \right )^2-1}{4m}.$](https://dxdy-04.korotkov.co.uk/f/f/d/c/fdcbc45c2df2f47ce809b292835f2ac682.png)
О другом методе поподробней. Возьмем тождество
![$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$ $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$](https://dxdy-03.korotkov.co.uk/f/6/0/6/6066ecb3f582d43784ec7fad707fa74d82.png)
и подставим вместо всех
![$4$ $4$](https://dxdy-03.korotkov.co.uk/f/e/c/f/ecf4fe2774fd9244b4fd56f7e76dc88282.png)
-х параметров соответствующие радикалы:
![$(a+b)(c+d)=\left ( \sqrt{ac}+\sqrt{bd} \right )^2+\left ( \sqrt{ad}-\sqrt{bc} \right )^2.$ $(a+b)(c+d)=\left ( \sqrt{ac}+\sqrt{bd} \right )^2+\left ( \sqrt{ad}-\sqrt{bc} \right )^2.$](https://dxdy-04.korotkov.co.uk/f/f/0/8/f08c6a39c5a60e275fa01ac1054505f982.png)
Чтобы величиной последнего квадрата можно было "пренебречь", положим
![$ad-bc=\pm1.$ $ad-bc=\pm1.$](https://dxdy-04.korotkov.co.uk/f/7/c/c/7cc30d84ac7a86336c86fc81f309ea9e82.png)
Тогда
![$\left ( \sqrt{ad}-\sqrt{bc} \right )^2=\left ( \dfrac{ad-bc}{\sqrt{ad}+\sqrt{bc}} \right )^2=\dfrac{1}{\left ( \sqrt{ad}+\sqrt{bc} \right )^2}.$ $\left ( \sqrt{ad}-\sqrt{bc} \right )^2=\left ( \dfrac{ad-bc}{\sqrt{ad}+\sqrt{bc}} \right )^2=\dfrac{1}{\left ( \sqrt{ad}+\sqrt{bc} \right )^2}.$](https://dxdy-04.korotkov.co.uk/f/b/f/6/bf667d8c3c9bae152dc0b693673218c082.png)
Откинув это в качестве погрешности, получаем
![$\sqrt{(a+b)(c+d)} \approx \sqrt{ad}+\sqrt{bc}.$ $\sqrt{(a+b)(c+d)} \approx \sqrt{ad}+\sqrt{bc}.$](https://dxdy-04.korotkov.co.uk/f/b/5/0/b50b0d005017291ab4258677b91e9d1182.png)
Такая схема действительно выражает общее решение для составного
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
и хорошо описывается в цепных дробях. Любая пара множителей
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
взаимно проста, поскольку
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
свободно от квадратов.
Возьмем
![$m=77=11 \cdot 7$ $m=77=11 \cdot 7$](https://dxdy-04.korotkov.co.uk/f/f/4/d/f4da1a8301c2753e3f70e12094f894bb82.png)
, разложим
![$\dfrac{11}{7}=1,1,1,3$ $\dfrac{11}{7}=1,1,1,3$](https://dxdy-03.korotkov.co.uk/f/e/8/1/e81b8ca6307954fdd34a63e2eec2ce1282.png)
и выпишем подходящие дроби, уменьшив последний знак на единицу:
![$1,1,1,2=\dfrac{1}{1},\dfrac{2}{1},\dfrac{3}{2},\dfrac{8}{5}.$ $1,1,1,2=\dfrac{1}{1},\dfrac{2}{1},\dfrac{3}{2},\dfrac{8}{5}.$](https://dxdy-02.korotkov.co.uk/f/1/1/0/110ae19aba6cfdb9ebeaf14dbdebc75e82.png)
Элементы двух последних дробей возвращают нужные
![$a,b,c,d$ $a,b,c,d$](https://dxdy-03.korotkov.co.uk/f/e/2/4/e2422452ef7d65e15f62276f42bcf94c82.png)
из описанной выше схемы:
![$\sqrt{3 \cdot 2}+\sqrt{8 \cdot 5}=\sqrt{(8+3)(5+2)}.$ $\sqrt{3 \cdot 2}+\sqrt{8 \cdot 5}=\sqrt{(8+3)(5+2)}.$](https://dxdy-04.korotkov.co.uk/f/7/2/d/72db8c066485a6d355b5435f0dc1a34f82.png)
Если мне память не изменяет, Диофант описывает тройки чисел
![$A,B,C$ $A,B,C$](https://dxdy-04.korotkov.co.uk/f/f/3/2/f32e22f05601a78c27bd8f654aadab1f82.png)
такие, что все три числа
![$AB,AC,BC$ $AB,AC,BC$](https://dxdy-04.korotkov.co.uk/f/b/4/b/b4bd9e888d52183091375fb3c250b54482.png)
являются числами вида
![$k(k+1).$ $k(k+1).$](https://dxdy-02.korotkov.co.uk/f/d/2/0/d2034ed9ccaa2926708a57460f0d6a1282.png)
Это и есть
![$m,x,y.$ $m,x,y.$](https://dxdy-02.korotkov.co.uk/f/5/6/f/56f61a328f1209ba4dde25b2378c9dd982.png)
О радикалах, правда, он ничего не говорит. Ну, а вопрос прежний: найти
![$x,y,$ $x,y,$](https://dxdy-02.korotkov.co.uk/f/9/5/a/95a5d265437c0cb4a7dbfcf6849d0f6282.png)
исходя из величины
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
. Как это с точки зрения теории алгоритмов — совсем безнадежное дело?