!!§!! Вспомогательная страница к разделу ((:numtheory#факторизация НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ)) ---- ==Извлечение корней из целых чисел== **Задача.** Для заданного натурального числа $ B_{} $ установить является ли оно полным квадратом и в этом случае определить $ \sqrt{B} $. !!Т!! **Теорема** ((#источники [1])). //Пусть// $ B_0 $ --- //произвольное целое такое, что// $ B_0^2>B $. //Последовательность// $$ B_j = \begin{array}{c} \left\lfloor \begin{array}{c} B_{j-1}+ \left\lfloor \displaystyle \frac{B}{B_{j-1}} \right\rfloor_{} \\ \hline 2 \end{array} \right\rfloor \\ \end{array} \quad npu \ \ j\in \{1,2,\dots \ \} \ , $$ //монотонно убывая, сойдется за конечное число шагов к значению// $ \left\lfloor\sqrt{B} \right\rfloor $, //если только число// $ B+1 $ //не является полным квадратом. Здесь// $ \lfloor \ \ \ \rfloor $ //означает ((:algebra2:notations#целая_часть_числа целую часть числа))//. В качестве стартового значения можно брать $ B_0=\lfloor B/3 \rfloor +1 $. !!П!! **Пример.** Вычислить $ \left\lfloor\sqrt{611524} \right\rfloor $. **Решение.** $ B_0=203842 $. Далее последовательность из теоремы: $$ B_1= 101922 \, ,\ B_2=50963 \, ,\ B_3=25487 \, , \ B_4=12755 \, \ , B_5=6401 \, ,$$ $$ \ B_6=3248\, , \ B_7=1718 \, ,\ B_8=1036 \, ,\ B_9=813\, , \ B_{10}=782\, , B_{11}=782\, , \dots $$ выходит на стационарное значение. Здесь $ 782^2=611524 $, т.е. исходное число --- полный квадрат. !!П!! **Пример.** Вычислить $ \left\lfloor\sqrt{10414} \right\rfloor $. **Решение.** Возьмем $ B_0=\lfloor B/3 \rfloor +1 =3472 $. $$ B_1=1737,\ B_2=871,\ B_3=441,\ B_4=232,\ B_5=138,\ B_6=106,\ B_7=102,\ B_8=102,\dots $$ Здесь $ 102^2=10404 $ и $ 102= \left\lfloor\sqrt{10414}\right\rfloor $. !!П!! **Пример.** Вычислить $ \left\lfloor\sqrt{80} \right\rfloor $. **Решение.** $$ B_0=27\, ,\ B_1=14 \, ,\ B_2=9\, ,\ B_3=8 \, ,\ B_4=9\, ,\ B_5=8\, , \dots $$ Видим, что если число $ B+1 $ является полным квадратом, то последовательность $ \{ B_j \} $ из теоремы, начиная с какого-то места, становится циклической --- она "прыгает" между числами $ \left\lfloor\sqrt{B} \right\rfloor $ и $ \left\lfloor\sqrt{B} \right\rfloor+1 $. !!?!! ((#источники [2])). Написано число $ 49 $. Между цифрами $ 4 $ и $ 9 $ вставили $ 48 $, в полученное число $ 4489 $ между цифрами $ 4 $ и $ 8 $ опять вписали $ 48 $ и т.д. Доказать, что все полученные таким образом числа будут точными квадратами. Идейной основой алгоритма, изложенного в теореме, является ((:polynomial:newton метод Ньютона)) решения нелинейного уравнения $ f_{}(x)=0 $. При некоторых условиях на функцию $ f_{}(x) $ и стартовое значение $ x_{0} $ итерационная последовательность $$ \left\{x_j = x_{j-1} - \frac{f(x_{j-1})}{f^{\prime}(x_{j-1})} \right\}_{j=1}^{\infty} $$ будет монотонно сходиться к корню уравнения. Легко проверить, что последовательность из теоремы является просто "округлением до целого" последовательности метода Ньютона, составленной для решения уравнения $ x^2-B=0 $. Почти всегда такое усечение происходит безнаказанно; однако иногда все же приводит к цикличности итерационной последовательности. Разумеется, идею метода Ньютона можно использовать и для решения более сложных задач, например, для вычисления $ \left\lfloor\sqrt[n]{B}\right\rfloor $ при $ n>2 $. Приведем соответствующий результат для случая $ n_{}=3 $. !!Т!! **Теорема.** //Пусть// $ B_{0} $ --- //произвольное целое такое, что// $ B_0^3>B>1 $. //Последовательность// $$ B_j = \left\{\left\lfloor \frac{2}{3}B_{j-1} + \frac{B}{3B_{j-1}^2} \right\rfloor \right\}_{j=1}^{\infty} \, , $$ //монотонно убывая, сойдется за конечное число шагов к значению// $ \left\lfloor\sqrt[3]{B} \right\rfloor $. == Источники== [1]. **Нодден П., Китте К.** //Алгебраическая алгоритмика.// М.Мир. 1999. [2]. **Шмулевич П.К.** //Сборникъ задачъ, предлагавшихся на конкурсныхъ экзаменахъ при поступленiи въ спецiaльныя высшiя учебныя заведенiя. Часть II. Алгебра.// Изданiе VIII. С.-Петербург. 1915. (Другие задачи из этого источника см. ☞ ((:schoolmath#задачи_дореволюционных_вступительных_экзаменов_в_институты_c.-петербурга ЗДЕСЬ)) ).