Точно так же вместо вещественных чисел можно взять, например, поле из 7 элементов — вычеты по модулю 7.
В нём у уравнения x^2+1=0 тоже нет корней (упражнение: проверьте это!). И добавив такой корень — и всё, что добавится из-за этого — мы получим поле из 7^2=49 элементов, элементы которого это комбинации вида a+bx (где x — наш корень). Классический вопрос « для каких простых p по модулю p есть корень из (-1) » имеет столь же классический ответ « для двойки и простых вида 4k+1 ».

Так вот — мы для нашей последовательности хотим рассмотреть числа, включающие в свою запись «корень из 3», и работать с ними «по модулю M». Вспомогательная лемма, которую мы сейчас принимаем на веру: для любого M=2^p-1, где простое p>2, из 3 по модулю M корень извлечь нельзя.

Следствие. Если M простое, то мы имеем право рассмотреть не только поле вычетов по модулю M, но и поле из M^2 элементов, получающееся добавлением x=\sqrt{3}. В котором есть «сопряжение» — замена знака перед \sqrt{3}.

Второе — важное само по себе — утверждение, это что мультипликативная группа конечного поля циклична. То есть что все ненулевые его элементы есть степень некоторого одного, поэтому операция «умножить» превращается ( если его знать) в операцию «сложить степени».

А давайте посмотрим, из скольки элементов состоит эта мультипликативная группа для нашего нового поля — то есть по какому модулю будет сложение степеней?

Всех элементов в поле M^2, без нуля
M^2-1=(M-1)(M+1) = 2^p (2^p-2).
И у нас внезапно образовалась группа, порядок которой делится на очень большую степень двойки (на 2^{p+1}, если быть точным).

Давайте закончим доказательство теста Люка-Лемера. Для начала посмотрим, какое у него условие «успешного окончания». Это s_{p-1}=0 — «вещественная (точнее, не содержащая \sqrt{3}) компонента» у числа z^{2^{p-2}} равна нулю.
Если бы речь шла о косинусе, это бы значило, что 2 cos a=0, и соответствующие комплексные числа были бы i и -i; а их квадрат равнялся бы (-1).
Собственно, s_{p-1}=0 равносильно тому, что s_{p}=-2, то есть z^{2^{p-1}}=-1.

Не то, чтобы это было обязательно — но вот пример для p=5 (которое приводит к действительно простому M=31):

Жирным тут выделены значения t_j — "вещественные части", половинки от последовательности s_j.

Итак, от z=2+\sqrt{3} (соответствующего s_1=4 или t_1=2) мы за p-2=3 итерации дошли до s_{p-1}=t_{p-1}=0, а за ещё одну — до z^{2^{p-1}}=-1 (и, соответственно, s_p=-2, t_p=-1). Если бы мы ещё один раз возвели в квадрат — воткнулись бы в единицу, которая для возведения в квадрат неподвижная точка.

Давайте посмотрим, почему мы этого не сделали — и почему всё было настолько « близко », что стоит M оказаться составным, и ничего не получится. И заодно выясним много интересного, что живёт «по соседству».

Во-первых, если у нас есть поле из q элементов (где q нечётное), то есть очень симпатичная формула, позволяющая проверить, является ли его элемент квадратом (в этом поле!). А именно — малая теорема Ферма для простого q и теорема Лагранжа для q=M^k утверждают, что w^{q-1}=1 для всех элементов поля.

Возьмём какое-нибудь ненулевое w, и давайте рассмотрим половинную степень — w^{(q-1)/2}.
Утверждение. w^{(q-1)/2}=1, если w это квадрат, и w^{(q-1)/2}=-1, если не квадрат.

Доказательство. Если w=r^2, то w^{(q-1)/2}=r^{q-1}=1.
Квадратов от ненулевых элементов поля ровно половина, поэтому все возможные корни уравнения w^{(q-1)/2}=1 (столько, какова его степень) мы уже посчитали. Но половинная степень, если её возвести в квадрат, должна дать w^{q-1}=1, а корни из 1 это только 1 и (-1). Значит, все не-квадраты дают (-1).

И уже сразу видна похожесть на нашу ситуацию — мы возводим в степень (правда, не совсем в ту), и получаем (-1).

Во-вторых, как и в комплексных числах, в таком «квадратичном расширении» тоже есть понятие нормы — произведение
||w||=w*conj(w),
где conj — сопряжение, изменяющее знак у \sqrt{3}.

Это скорее аналог квадрата длины комплексного числа, но в теории Галуа правильно использовать именно такое определение. И как легко видеть, наше z=2+\sqrt{3} имеет единичную норму:
(2+\sqrt{3})(2-\sqrt{3})=4-3=1.

(А в общем случае — см.
https://kconrad.math.uconn.edu/blurbs/galoistheory/tracenorm.pdf или https://en.wikipedia.org/wiki/Field_trace )

В третьих, если у нас есть поле из M^k элементов (характеристики M), то у него есть автоморфизм
a->a^M.
Потому что, раскрыв по биному, получаем (a+b)^M=a^M+b^M (все остальные биномиальные коэффициенты делятся на M). Этот автоморфизм «именной» — он называется автоморфизмом Фробениуса.

Более того, он порождает группу автоморфизмов поля — которая оказывается циклической, и состоит из k элементов: после k его применений мы получаем возведение в степень M^k — которая есть тождественное отображение (как мы уже видели выше — в виде равенства w^{q-1}=1).

И вообще автоморфизм Фробениуса в теории Галуа это один из фундаментальных кирпичиков — такой же, как понятие предела или интеграла в анализе.