Math
Die modulare Uhr
Ein Zifferblatt mit m Marken und ein Zeiger. Addieren zeichnet einen Stern, der nach m/ggT(s, m) Zügen schließt; Multiplizieren einen Zyklus, dessen Länge phi(m) teilt. Manche Moduln haben gar keine Primitivwurzel - das sagt die Karte, denn es ist ein Satz und kein gescheitertes Suchen.
Was passiert
Der Zeiger geht Zug für Zug, und die berührten Marken leuchten auf; die dunklen beantworten die Frage, bevor die Tafel den ggT nennt. Schritt 8 auf zwölf Marken zeichnet ein Dreieck, Schritt 5 einen Stern über alle zwölf, weil 5 und 12 teilerfremd sind. Beim Multiplizieren gilt k → k·g: die Zykluslänge ist die ORDNUNG von g, und nach Euler teilt sie phi(m) - auf siebzehn Marken sind nur 1, 2, 4, 8 und 16 möglich. Eine Primitivwurzel ist ein g mit Ordnung genau phi(m); auf einem Primzahl-Zifferblatt läuft sie über alle Marken außer der Null. Wie viele gibt es? Genau phi(phi(m)), und die Tafel zählt sie zusätzlich durch Probieren. Und dann das Wesentliche: Primitivwurzeln existieren nicht für jeden Modul, sondern nur für 1, 2, 4, p^k und 2p^k. Für 8, 12, 15, 16, 20, 21 oder 24 gibt es keine - und die Karte sagt das laut, statt still nichts zu finden.
Gleichungen des Moduls
Gleichungen Addieren: der Zeiger auf Position k springt auf k + s (mod m); der Zyklus schließt sich nach m / gcd(s, m) Schritten und besucht JEDE Markierung genau dann, wenn gcd(s, m) = 1 m = 12, s = 8 → 3 Markierungen (ein Dreieck); m = 12, s = 5 → alle 12; m = 360, s = 84 → 30 Multiplizieren: k → k·g (mod m); die Zykluslänge ist die ORDNUNG von g, und nach dem Satz von Euler teilt sie phi(m) m = 17: phi = 16 und die vorkommenden Ordnungen sind 1, 2, 4, 8, 16 - etwas anderes kann nicht auftreten eine Primitivwurzel ist ein g, dessen Ordnung phi(m) IST; für eine Primzahl m bedeutet das einen Zyklus durch alle m − 1 Markierungen ungleich null wie viele: genau phi(phi(m)), wenn sie existieren - m = 7 → 2 (kleinste 3), m = 11 → 4 (kleinste 2), m = 23 → 10 (kleinste 5) WANN SIE EXISTIEREN: nur für m = 1, 2, 4, p^k und 2p^k. Für 8, 12, 15, 16, 20, 21, 24 gibt es überhaupt KEINE Primitivwurzel - ein Satz, keine gescheiterte Suche phi wird hier berechnet, nicht tabelliert: phi(7) = 6, phi(9) = 6, phi(12) = 4, phi(16) = 8, phi(36) = 12, phi(100) = 40, phi(1000) = 400
