Доказательство. Если 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).

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

Но в нашем случае мы уже знаем единственный нетривиальный автоморфизм поля из M^2 элементов: это изменение знака у корня из 3. Значит, conj(w)=w^M, откуда
||w||=w*conj(w)=w^{M+1}.

И паззл начинает склеиваться — M+1=2^p. А у нас было возведение в половинную степень: нам нужно проверить, что
z^{2^{p-1}}=-1.

Так вот: давайте посмотрим не на всю группу ненулевых элементов поля, а на её подгруппу, состоящую из элементов нормы 1 — из корней уравнения w^{M+1}=1.

Эта группа состоит, как несложно видеть, из M+1 элемента, и это циклическая группа. Например, как подгруппа циклической, хотя приятнее тут сослаться на вообще общее утверждение: конечная подгруппа мультипликативной группы любого поля циклична.

(Его доказательство — отдельное красивое упражнение, но речь сейчас не об этом :) ).

Так вот — у нас есть подгруппа элементов нормы 1, состоящая из N=M+1 элемента. Повторяя рассуждения выше, несложно увидеть, что её элемент w является квадратом внутри этой подгруппы тогда и только тогда, когда половинная степень w^{N/2} равна 1 — а иначе получаем (-1).

Поэтому всё, что нам нужно проверить, чтобы знать, что мы действительно получаем z^{2^{p-1}}=-1 (и поэтому s_{p}=-2, s_{p-1}=0) — это что z=2+\sqrt{3} не является квадратом элемента нормы 1!

А этому более-менее соответствует то, что "шаг назад" от s_1 мы сделать не сможем: не будет такого s_0, для которого s_0^2 - 2 = 4 = s_1 (mod M).
И не будет его потому, что это означало бы извлечение корня из 6 по модулю M. Но из 3 корня по модулю M нет (с этой декларации мы и начали рассказ, и это следует из квадратичного закон взаимности), а из 2, напротив, всегда есть: ведь 2^{p+1}=2 mod M, а значит, корнем будет 2^{(p+1)/2}. Из 2 корень есть, из 3 нет — значит, нет и из их произведения 6=2*3.

Если говорить совсем аккуратно — то если
w=(t+r \sqrt{3})^2 = (2+\sqrt{3})
и w нормы 1, то t^2-3r^2=1, а при раскрытии скобок по «вещественной» части получается
t^2+3r^2 = 2t^2- (t^2-3r^2)=2t^2-1,
и уравнение
2 t^2-1=2
это то же самое уравнение
s^2-2=4,
переписанное в терминах t=s/2.

Вот. Давайте я подытожу — мы пока сделали проход в одну сторону, что если M=2^p-1 простое, то s_{p-1}=0. Но мы возводили в столь большую степень двойки — что в объяснение "ну, если M разложится на множители, то мы по модулю хотя бы одного из сомножителей в (-1) не попадём" кажется как минимум правдоподобным.

И вот так этот "чёрный ящик" теста и работает!

В качестве постскриптума — совсем другой рассказ о том же:
А.Н.Рудаков, Числа Фибоначчи и простота числа 2^{127}-1 — см. https://www.mccme.ru/free-books/matpros5.html

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