Math
Годинник за модулем
Циферблат із m поділок і одна стрілка. Додавання малює зірку, що замикається за m/НСД(s, m) ходів; множення — цикл, довжина якого ділить φ(m). У деяких модулів первісних коренів немає зовсім, і картка це каже: така теорема, а не невдача пошуку.
Що відбувається
Стрілка йде хід за ходом, і поділки, яких вона торкнулася, загоряються; ті, що лишились темними, відповідають раніше, ніж панель назве НСД. Крок 8 на дванадцяти поділках малює трикутник; крок 5 — зірку по всіх дванадцяти, бо 5 і 12 не мають спільного дільника. При множенні правило інше: k → k·g, довжина циклу є ПОРЯДКОМ g, і за теоремою Ейлера цей порядок ДІЛИТЬ φ(m) — на сімнадцяти поділках можливі лише 1, 2, 4, 8 і 16. Первісний корінь — це g, порядок якого дорівнює саме φ(m); на простому циферблаті він обходить усі поділки, крім нуля. Скільки їх? Рівно φ(φ(m)), і панель рахує їх ще й перебором. І головне: первісні корені існують не для всякого модуля, а лише для 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
