Для доказательства данной теоремы нам потребуется следующая Лемма.

Лемма: Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа $r,\; \backslash ;s$ такие что

Доказательство Леммы: Если $p\; =\; q$, т.е. $n\; =\; p^2$, то утверждение теоремы выполнено для $r\; =\; s\; =\; 1$. Далее будем считать

Разложим $\backslash frac\; qp$ в непрерывную дробь. Мы обозначаем $\backslash frap\_jq\_j\}$ $j$-ю подходящую дробь к $\backslash fracqp$. Тогда

$p\_0\; =\; [\backslash fracqp]$, $q\_0=1$,

поскольку

Такой номер обязательно найдется, поскольку у последней подходящей дроби знаменатель

$|\backslash fracrs\; -\; \backslash fracqp|\; \backslash leqslant\; |\backslash fracrs\; -\; \backslash fracp\_m+1q\_m+1|\; =\; \backslash frac1s\; q\_m+1$

по свойствам подходящих дробей.

Рассмотрим сначала случай $\backslash fracp\_m+1q\_m+1\; \backslash leqslant\; \backslash frac\; qp$. В этом случае

$|pr\; -\; qs|\; =\; ps|\backslash fracrs\; -\; \backslash fracqp|\; \backslash leqslant\; \backslash fracpssq\_m+1\}\; =\; \backslash frac\; pq\_m+1\; =\; \backslash sqrt\{\backslash fracpq\_m+1$

\frac pq_m+1} \leqslant \sqrt\fracpq_m+1 \sqrt\fracqp_m+1 = \sqrt\fracnpm+1_m+1 < \fracn^1/2n^1/6 = n1/3/math>,

что и требовалось доказать.

Теперь рассмотрим случай $\backslash fracp\_m+1q\_m+1\; >\; \backslash fracqp$. Тогда перевернем неравенства

$\backslash fracp\_m+1q\_m+1\; >\; \backslash fracqp\; >\; \backslash frap\_mq\_m\}$, откуда

$\backslash fracq\_mp\_m\; >\; \backslash fracpq\; >\; \backslash fracq\_m+1p\_m+1$. Следовательно, по свойствам непрерывных дробей, выполнены неравенства

$\backslash frac\{1rq\backslash leqslant\; |\backslash fracsr\; -\; \backslash fracpq|\; \backslash leqslant\; |\backslash fracsr\; -\; \backslash fracq\_m+1p\_m+1|\; =\; \backslash frac1r\; p\_m+1$. Отсюда

$1\; \backslash leqslant\; |sq\; -\; pr|\; =\; rq|\backslash fracsr\; -\; \backslash fracpq|\; \backslash leqslant\; \backslash fracrqrp\_m+1\}\; =\; \backslash frac\; qp\_m+1\; =\; \backslash sqrt\{\backslash fracqp\_m+1$

\frac qp_m+1} \leqslant \sqrt\fracqp_m+1 \sqrt\fracpq_m+1 = \sqrt\fracnpm+1_m+1 < \fracn^1/2n^1/6 = n1/3/math>

Лемма доказана.

Доказательство Теоремы: Пусть $p$ и $q$ нечетные делители числа $n$. Пусть $x\; =\; pr\; +\; qs$ и $y\; =\; pr\; -\; qs$, где $r$ и $s$ удовлетворяют утверждению Леммы, тогда выполнено равенство
$x^2\; -\; y^2\; =\; (pr\; +qs)^2\; -\; (pr\; -\; qs)^2\; =\; 4rspq\; =\; 4kn$,
где $k\; =\; rs$. В силу Леммы, целое число $k$ удовлетворяет неравенству

Для доказательства второго утверждения положим $z\; =\; x\; -\; \backslash lfloor\; \backslash sqr4bn\backslash rfloor\; =\; pr\; +\; qs\; -\; \backslash lfloor\; \backslash sqr4bn\backslash rfloor$, Так как $x^2\; =\; 4kn\; +\; y^2$, то $x\; \backslash geqslant\backslash sqr4kn/math>\; и$ z\; \backslash geqslant\; 0$.\; Используя\; оценку\; сверху\; для$ y$,\; получаем$
$n2/3>\; y^2\; =\; x^2\; -\; 4kn\; =\; (pr\; +\; qs\; +\; \backslash sqr4kn(pr\; +\; qs\; -\; \backslash sqr4kn\; \backslash geqslant\; 2\backslash sqr4knpr\; +\; qs\; -\; \backslash sqr4kn\; \backslash geqslant\; 2\backslash sqr4knz\; -\; 1)$.
Откуда следует, что . Теорема доказана.

Трудоемкость

На первом шаге нам требуется произвести $\backslash lceil\; n1/3\backslash rceil$ операций деления для поиска маленьких делителей числа $n$.

Трудоемкость второго шага оценивается в операциях тестирования числа $\backslash left(\backslash left\backslash lfloor\backslash sqr4knright\backslash rfloor+d\backslash right)^2-4kn$, на то, является ли оно полным квадратом. В начале заметим, что для всех $k\; >\; \backslash fracn^1/64$ выполняется только две проверки: $D\; =\; 0$ и $D\; =\; 1$. Тогда, трудоемкость второго этапа оценивается сверху величиной

.
Таким образом трудоемкость всего есть величина $~O(n1/3$.

Пример

Разберем пример с $n\; =\; 1387$, тогда для $a\; =\; 1,\backslash ;2,\backslash ;3,\backslash ;\backslash ldots,\backslash ;\backslash lfloor\; n1/3\backslash rfloor$, где $\backslash lfloor\; n1/3\backslash rfloor\; =\; 11$,

проверяем является ли число $a$ делителем числа $n$. Не трудно убедится, что таких нет, тогда переходим к следующему пункту.

Для всех $k\; =\; 1,\backslash ;2,\backslash ;3,\backslash ;\backslash ldots,\backslash ;11$ и всех $d\; =\; 0,\backslash ;1,\backslash ;\backslash ldots,\backslash ;4$ проверяем, является ли число $\backslash left(\backslash left\backslash lfloor\backslash sqr4knright\backslash rfloor+d\backslash right)^2-4kn$ квадратом натурального числа. В нашем случае существуют такие $k\; =\; 3$ и $d\; =\; 1$, что выражение $\backslash left(\backslash left\backslash lfloor\backslash sqr4knright\backslash rfloor+d\backslash right)^2-4kn$ является полным квадратом и равно $256\; =\; 16^2$. Следовательно $A\; =\; 130$ и $B\; =\; 16$.

• = (A - B; n) = 19, удовлетворяет неравенству
  • < n и является делителем числа $n$. В итоге, мы разложили число $1387$ на два множителя: $73$ и $19$.