Так вот: давайте посмотрим не на всю группу ненулевых элементов поля, а на её подгруппу, состоящую из элементов нормы 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

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

(Чуть более формально — материальная точка движется внутри треугольника, отражаясь по закону "угол падения равен углу отражения"; траектории, в какой-то момент попадающие в вершины, мы не рассматриваем.)

Для остроугольного треугольника траекторию можно предъявить явно — простой и красивый геометрический факт состоит в том, что можно взять траекторию через три основания высот.

(Фото с лестницы МЦНМО — спасибо Г. Мерзону!)

А это фото с сегодняшней лекции А. Глуцюка (вводный рассказ о бильярдах) — и на правой половине левой доски видно как раз доказательство (школьное :) )

Так вот — в прямоугольном треугольнике это всё ещё упражнение. А вот в тупоугольных — большой открытый вопрос. (Нет, в любом конкретном, конечно, можно найти; и даже знают, что если все углы соизмеримы с π, то есть; но общий случай открыт.)

Кстати, про прямоугольный треугольник — есть прекрасная задача про столкновения масс на прямой, превращающаяся в задачу о бильярде и в итоге (spoilers!) приводящая к появлению π в ответе.
Вот тут есть ролик 3blue1brown об этом —
https://www.youtube.com/watch?v=HEfHFsfGXjs —
а я узнал об этом, если не ошибаюсь, в ЛШСМ-2004 от самого Гальперина, статью которого "Playing pool with π (the number π from a billiard point of view)" (https://www.maths.tcd.ie/~lebed/Galperin.%20Playing%20pool%20with%20pi.pdf ) 3blue1brown цитирует:

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

А бывают ли такие "фокусирующие" бильярды (уже просто с гладкой границей, но вовсе не с многоугольной), у которых есть _открытое_ множество периодических траекторий? То есть если поставить шарик примерно в правильное место и ударить под примерно правильным углом — то траектория обязательно замкнётся?