Math
Часы по модулю
Циферблат из m делений и одна стрелка. Сложение рисует звезду, замыкающуюся за m/НОД(s, m) ходов; умножение — цикл, длина которого делит φ(m). У некоторых модулей первообразных корней нет вовсе, и карточка это говорит: такова теорема, а не неудача поиска.
Что происходит
Стрелка идёт ход за ходом, и деления, которых она коснулась, загораются; те, что остались тёмными, отвечают на вопрос раньше, чем панель назовёт НОД. Шаг 8 на циферблате из 12 рисует треугольник и зажигает три деления; шаг 5 рисует звезду и зажигает все двенадцать, потому что у 5 и 12 нет общего делителя. Замкнутая фигура и есть результат, поэтому она остаётся на экране, а не стирается. Переключи на умножение — правило меняется: стрелка идёт k → k·g, длина цикла есть ПОРЯДОК g, и теорема Эйлера говорит, что этот порядок обязан ДЕЛИТЬ φ(m): на циферблате из 17 возможны только длины 1, 2, 4, 8 и 16. Шаг, порядок которого равен ровно φ(m), называется первообразным корнем, и на простом циферблате он обходит все ненулевые деления — это и есть задача карточки. Сколько таких шагов? Ровно φ(φ(m)) — два для 7, четыре для 11, десять для 23, — и панель считает их ещё и перебором, так что формула и поиск сходятся у тебя на глазах. И то, ради чего стоит задержаться: первообразные корни существуют не у всякого модуля. Только при 1, 2, 4, p^k и 2p^k, поэтому на циферблате из 8, 12, 15, 16, 20, 21 или 24 их нет ни одного. Карточка говорит это вслух, а не молча ничего не находит: «ответа нет» и «я не нашёл» — разные утверждения.
Уравнения модуля
Уравнения сложение: стрелка в положении k переходит в k + s (mod m); цикл замыкается после m / gcd(s, m) ходов и посещает КАЖДУЮ отметку ровно тогда, когда gcd(s, m) = 1 m = 12, s = 8 → 3 отметки (треугольник); m = 12, s = 5 → все 12; m = 360, s = 84 → 30 умножение: k → k·g (mod m); длина цикла есть ПОРЯДОК g, и по теореме Эйлера он делит phi(m) m = 17: phi = 16 и встречающиеся порядки 1, 2, 4, 8, 16 - других быть не может первообразный корень есть такое g, порядок которого РАВЕН phi(m); для простого m это означает цикл через все m − 1 ненулевых отметок сколько их: ровно phi(phi(m)), когда они существуют: m = 7 → 2 (наименьший 3), m = 11 → 4 (наименьший 2), m = 23 → 10 (наименьший 5) КОГДА ОНИ СУЩЕСТВУЮТ: только для m = 1, 2, 4, p^k и 2p^k. Для 8, 12, 15, 16, 20, 21, 24 первообразного корня НЕТ вообще - это теорема, а не неудачный поиск phi вычисляется здесь, а не берётся из таблицы: phi(7) = 6, phi(9) = 6, phi(12) = 4, phi(16) = 8, phi(36) = 12, phi(100) = 40, phi(1000) = 400
