Согласно формулам сложения имеем ${\displaystyle X_{-1}=-x-x^{p}+{\frac {(1+(x^{3}+ax+b)^{(p-1)/2})^{2}(x^{3}+ax+b)}{(x-x^{p})^{2}}}}$ , далее заметим что степень числителя больше степени знаменателя на 1, так как ${\displaystyle X_{-1}={\frac {x^{2p+1}+R(x)}{(x-x^{p})^{2}}}}$ , где R(x) - многочлен степени, не превосходящей 2p. Вычислим знаменатель дроби по проведении необходимых сокращений. С одной стороны ${\displaystyle (x-x^{p})^{2}=(x(x-1)...(x-p+1))^{2}}$ , с другой, как известно,

${\displaystyle (x^{3}+ax+b)^{(p-1)/2}=\left({\frac {x^{3}+ax+b}{p}}\right)}$

потому при сокращении из знаменателя выпадут лишь множители вида ${\displaystyle (x-k)^{2}}$ с ${\displaystyle {\frac {k^{3}+ak+b}{p}}=-1}$ , и множители вида ${\displaystyle (x-l)}$ с ${\displaystyle l^{3}+al+b=0}$ . Пусть ${\displaystyle m}$ -количество множителей первого рода, а ${\displaystyle n}$ - второго. Тогда ${\displaystyle d_{-1}=2p-2m-n+1}$ , и учитывая, что ${\displaystyle d_{0}=p}$ , получаем ${\displaystyle d_{-1}-d_{0}-1=p-2m-n}$ . Число ${\displaystyle N}$ же равно ${\displaystyle 2(p-m)-n}$ , так как каждому классу вычетов ${\displaystyle k}$ соответствует два решения, а классу вычетов ${\displaystyle l}$ - одно. Это доказывает требуемое.

По основной лемме ${\displaystyle d_{n+2}=2d_{n+1}-d_{n}+2}$ . Очевидно, что для ${\displaystyle n=-1}$ и ${\displaystyle n=0}$ лемма верна: пусть она верна и для индексов ${\displaystyle n}$ и ${\displaystyle n+1}$ , ${\displaystyle n\geqslant 0}$ . Тогда

${\displaystyle d_{n+2}=2d_{n+1}-d_{n}+2=2((n+1)^{2}-(d_{-1}-d_{0}-1)(n+1)+d_{0})-n^{2}+(d_{-1}-d_{0}-1)n-d_{0}+2=(n+2)^{2}-(d_{-1}-d_{0}-1)(n+2)+d_{0})}$

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

Мы докажем это неравенство, формально найдя значение функции ${\displaystyle X_{n}}$ при ${\displaystyle x=\infty }$ . Пусть ${\displaystyle m}$ есть нуль или первый номер после очередного пробела ^{[ уточнить ]} , ${\displaystyle m\geqslant 0}$ . По построению ${\displaystyle X|_{\infty }=\infty }$ , а ${\displaystyle Y|_{\infty }}$ ≠0. Допустим обратное. Ввиду того, что дробь ${\displaystyle {\frac {X_{n+1}^{3}+aX_{n+1}+b}{x^{3}+ax+b}}}$ , должна быть квадратом, разность степеней числителя и знаменателя функции ${\displaystyle X_{n+1}}$ должна быть числом нечетным, то вместе с ${\displaystyle Y_{n+1}|_{\infty }=0}$ даёт ${\displaystyle X_{n+1}|_{\infty }=0}$ . Для арифметической прогрессии следует

${\displaystyle Y_{n+1}={\frac {1-Y_{n}}{X-X_{n}}}(x-X_{n+1})-1}$

Отсюда находим

${\displaystyle {\frac {1-Y_{n}}{x-X_{n}}}(x-X_{n})|_{\infty }=1}$ или ${\displaystyle {\frac {1-Y_{n}}{1-{\frac {X_{n}}{x}}}}|_{\infty }=1}$

то есть

${\displaystyle {\frac {Y_{n}x}{X_{n}}}|_{\infty }=1}$ , ${\displaystyle {\frac {Y_{n}^{2}x^{2}}{X_{n}^{2}}}|_{\infty }={\frac {(X_{n}^{3}+aX_{n}+b)x^{2}}{(x^{3}+ax+b)X_{n}^{2}}}|_{\infty }=1}$

Поскольку ${\displaystyle X_{n}|_{\infty }=x|_{\infty }=\infty }$ , отсюда следует, что ${\displaystyle {\frac {X_{n}}{x}}|_{\infty }=1}$ . С другой стороны

${\displaystyle X_{n+1}=-x-X_{n}+{\frac {(1-Y_{n}^{2})^{2}}{(x-X_{n})^{2}}}(x^{3}+ax+b)}$

Отсюда находим

${\displaystyle {\frac {X_{n}}{x}}=-1-{\frac {X_{n}}{x}}+{\frac {(1-Y_{n}^{2})^{2}}{(1-{\frac {X_{n}}{x}})^{2}}}(1+{\frac {a}{x^{2}}}+{\frac {b}{x^{3}}})}$

так что

${\displaystyle {\frac {X_{n+1}}{x}}|_{\infty }=-1}$

Но из этого равенства следует, что ${\displaystyle Y_{n+1}^{2}|_{\infty }}$ , что противоречит сделанному предположению ${\displaystyle Y_{n+1}^{2}|_{\infty }=0}$ . Лемма доказана.

Основные трудности в доказательстве теоремы сконцентрированы на основной лемме. Приступим к её доказательству. для любого многочлена P символом ст. Р будем обозначать степень этого многочлена.

Приводя к общему знаменателю и собирая подобные члены в формуле сложения решений, находим

${\displaystyle X_{n-1}={\frac {-(xQ_{n}+P_{n})(xQ_{n}-P_{n})^{2}+(1+Y_{n})^{2}(x^{3}+ax+b)Q_{n}}{(xQ_{n}-P_{n})^{2}}}={\frac {(xQ_{n}+P_{n})(xP_{n}+aQ_{n})+2bQ_{n}^{2}+2Y_{n}(x^{3}+ax+b)Q_{n}^{2}}{(xQ_{n}-P_{n})^{2}}}={\frac {S}{(xQ_{n}-P_{n})^{2}}}}$

Перемножая почленно две полученные выше формулы и проведя сокращения, получим

${\displaystyle X_{n-1}X_{n+1}={\frac {P_{n-1)P_{n+1}}}{Q_{n-1}Q_{n+1}}}={\frac {(xP_{n}-aQ_{n})^{2}-2b(xQ_{n}+P_{n})}{(xQ_{n}-P_{n})^{2}}}}$

Цель следующих рассуждений - показать, что ${\displaystyle Q_{n-1}*Q_{n+1}=(xP_{n}-aQ_{n})^{2}}$ . Из этого равенства напрямую получится основная лемма, в самом деле, тогда следует что

${\displaystyle P_{n-1}*P_{n+1}=(xP_{n}-aQ_{n})^{2}-4bQ_{n}(xQ_{n}+P_{n})}$ ,

значит ${\displaystyle d_{n-1}+d_{n+1}=}$ ст. ${\displaystyle (P_{n-1}P_{n+1})}$ =ст. ${\displaystyle (x^{2}P_{n}^{2})=2d_{n}+2}$ , потому что в силу леммы 3 старший член многочлена ${\displaystyle P_{n-1}P_{n+1}}$ совпадает со старшим членом многочлена ${\displaystyle x^{2}P_{n}^{2}}$ . Теперь докажем нужное равенство.

Напомним, что в области многочленов существует однозначное разложение на неприводимые множители. Пусть ${\displaystyle E}$ - неприводимый многочлен, а ${\displaystyle e}$ - любое целое положительное число. Мы будем говорить, что многочлен ${\displaystyle E^{e}}$ строго делит некоторую несократимую рациональную функцию, если её числитель делится на ${\displaystyle E^{e}}$ , но не делится на ${\displaystyle E^{e+1}}$ . Для доказательства нужного равенства нужно установить что если многочлен ${\displaystyle E^{e}}$ строго делит ${\displaystyle (xQ_{n}-P_{n})^{2}}$ , то он строго делит также ${\displaystyle Q_{n-1}Q_{n+1}}$ . В самом деле, тогда частное ${\displaystyle {\frac {Q_{n-1}Q_{n+1}}{(xQ_{n}-P_{n})^{2}}}}$ представляет собой многочлен, который взаимно прост с многочленом (xQ_n-P_n)^2. Но поскольку из приведённого уравнения следует, что функция ${\displaystyle Y_{n}(x^{3}+ax+b)Q_{n}^{2}}$ является многочленом, то из предыдущих равенств для <X_{n-1}> и <X_{n+1}>без труда получается, что знаменатели ${\displaystyle Q_{n-1}}$ , ${\displaystyle Q_{n+1}}$ делят многочлен ${\displaystyle (xQ_{n}-P_{n})^{4}}$ . Тем самым частное ${\displaystyle {\frac {Q_{n-1}Q_{n+1}}{(xQ_{n}-P_{n})^{2}}}}$ может быть только константой, и эта константа равна единице в силу принятой нормировки старших членов числителей ${\displaystyle P_{n}}$ .

Разобьем все неприводимые делители ${\displaystyle E}$ многочлена ${\displaystyle (xQ_{n}-P_{n})^{2}}$ на три группы. К первой группе отнесем те многочлены, которые делят R, но не делят S. Из этого сразу же вытекает, что если многочлен ${\displaystyle E^{e}}$ строго делит ${\displaystyle (xQ_{n}-P_{n})^{2}}$ , то он строго делит знаменатель ${\displaystyle Q_{n+1}}$ и взаимно просто со знаменателем ${\displaystyle Q_{n-1}}$ . Ко второй группе отнесем те многочлены ${\displaystyle >E}$ , которые делят S, но не делят R. Точно так же получается, что если многочлен ${\displaystyle E^{e}}$ строго делит ${\displaystyle (xQ_{n}-P_{n})^{2}}$ , то он строго делит знаменатель ${\displaystyle Q_{n-1}}$ и взаимно просто со знаменателем ${\displaystyle Q_{n+1}}$ . Наконец к третьей группе отнесем те многочлены ${\displaystyle E}$ , которые делят и R, и S. Поскольку

${\displaystyle P_{n}=xQ_{n}(modE)}$ ,

следует что

${\displaystyle R=2Q_{n}(1-Y_{n})(x^{3}+ax+b)(modE)}$ ,

${\displaystyle S=2Q_{n}(1+Y_{n})(x^{3}+ax+b)(modE)}$ .

Многочлен ${\displaystyle E}$ , деля многочлен ${\displaystyle (xQ_{n}-P_{n})^{2}}$ , не может делить ${\displaystyle Q_{n}}$ , поскольку ${\displaystyle P_{n}}$ и ${\displaystyle Q_{n}}$ взаимно просты. Отсюда и из последних формул вытекает, что ${\displaystyle S+R=4Q_{n}^{2}(x^{3}+ax+b)modE}$ , так что если ${\displaystyle E}$ делит ${\displaystyle R}$ и ${\displaystyle S}$ , то ${\displaystyle E}$ строго делит многочлен ${\displaystyle x^{3}+ax+b}$ (по предположению этот многочлен не имеет кратных корней).

Итак, пусть ${\displaystyle E}$ - неприводимый делитель многочлена ${\displaystyle x^{3}+ax+b}$ . Предположим сначала, что ${\displaystyle Y_{n}}$ ≠±1 ${\displaystyle (modE)}$ (эта запись по определению означает, что числитель несократимого представления функции ${\displaystyle Y_{n}}$ ±1 не делится на ${\displaystyle E}$ ). Тогда следует, что ${\displaystyle E}$ строго делит ${\displaystyle R}$ , потому что многочлен ${\displaystyle (xQ_{n}-P_{n})^{2}}$ делится по крайней мере на ${\displaystyle E^{2}}$ . Подобным образом получается, что ${\displaystyle E}$ делит ${\displaystyle S}$ , но тогда вытекает, что ${\displaystyle E^{2}}$ строго делит ${\displaystyle (xQ_{n}-P_{n})^{2}}$ .

Таким образом, остается проверить случай ${\displaystyle Y_{n}+}$ =±1 ${\displaystyle (modE)}$ . Пусть, например, ${\displaystyle Y_{n}=-1(modE)}$ (вторая разбирается аналогично). Тогда ${\displaystyle E}$ строго делит ${\displaystyle S}$ . Пусть ${\displaystyle E^{2}}$ строго делит ${\displaystyle (xQ_{n}-P_{n})^{2}}$ , а ${\displaystyle E^{2f+1}}$ строго делит ${\displaystyle (1+Y_{n})(X^{3}+ax+b)Q_{n}^{2}}$ . Очевидно ${\displaystyle E^{2f}}$ строго делит также функцию ${\displaystyle (1+Y_{n})^{2}(1-Y_{n})^{2}=(1-Y_{n}^{2})^{2}}$ . Но

${\displaystyle (1-Y_{n}^{2})^{2}={\frac {(x^{3}+ax-X_{n}^{2}-aX_{n}^{2})^{2}}{(x^{3}+ax+b)^{2}}}={\frac {(x-X_{n})^{2}(x^{2}+xX_{n}+X_{n}^{2}+a)^{2}}{(x^{3}+ax+b)^{2}}}}$ .

Кроме того, ${\displaystyle x=X_{n}(modE)}$ , ${\displaystyle x^{2}+xX_{n}+X_{n}^{2}=3x^{2}+a}$ ≠0 ${\displaystyle (modE)}$ , так что ${\displaystyle 2f=2e-2}$ и, следовательно, число ${\displaystyle 2f+1=2e-1}$ меньше степени, в которой ${\displaystyle E}$ строго делит ${\displaystyle (xQ_{n}+P_{n})(xQ_{n}-P_{n})^{2}}$ . Поэтому ${\displaystyle E^{2e}}$ строго делит ${\displaystyle RS}$ . Откуда вытекает, что ${\displaystyle E^{2e}}$ строго делит ${\displaystyle Q_{n-1}Q_{n+1}}$ . Что и требовалось доказать.

Лемма 1. Для эллиптической кривой ${\displaystyle E(\mathbb {F} _{q})}$ над полем ${\displaystyle \mathbb {F} _{q}}$ и точек ${\displaystyle (x,y)\in E({\overline {\mathbb {F} _{q}}})}$ выполняется:

1) ${\displaystyle \phi _{q}(x,y)\in E({\overline {\mathbb {F} _{q}}})}$ ,

2) ${\displaystyle (x,y)\in E(\mathbb {{F}_{q}} )}$ тогда и только тогда, когда ${\displaystyle \phi _{q}(x,y)=(x,y)}$ .

Лемма 2. Для эллиптической кривой ${\displaystyle E(\mathbb {F} _{q})}$ отображение ${\displaystyle \phi _{q}}$ является эндоморфизмом кривой ${\displaystyle E}$ степени ${\displaystyle q}$ , и ${\displaystyle \phi _{q}}$ не разделяемый.

Лемма 3. Пусть определена эллиптическая кривая ${\displaystyle E(\mathbb {F} _{q})}$ и ${\displaystyle n\geqslant 1}$ . Тогда

1) ${\displaystyle \ker(\phi _{q}-1)=E(\mathbb {F} _{q^{n}})}$ ,

2) ${\displaystyle \phi _{q}^{n}-1}$ — разделяемый эндоморфизм, и поэтому ${\displaystyle |E(\mathbb {F} _{q^{n}})|=\deg(\phi _{q}^{n}-1)}$ .

Лемма 4. Обозначим ${\displaystyle a=q+1-|E(\mathbb {F} _{q})|=q+1-\deg(\phi _{q}-1)}$ . Пусть ${\displaystyle r,s}$ — целые числа и ${\displaystyle \gcd(s,q)=1}$ . Тогда ${\displaystyle \deg(r\phi _{q}-s)=r^{2}q+s^{2}-rsa}$ .