Fermat & Euler — Cycle of Powers and the Totient

a = m = step 0

Power cycle of a mod m

residue 1 (target) current a^k visited

Facts & totient

Residues 1..m — coprime to m are counted by φ(m):

Power sequence a^k mod m:

Press Step to begin. We multiply by a each step, watching a^k mod m walk around until it returns to 1 — that return happens at k = ord(a), a divisor of φ(m).

What to try

a = 3, m = 7 (default): prime modulus, a is a primitive root — the cycle visits all 6 nonzero residues before returning to 1 (Fermat: 3⁶ ≡ 1).
a = 2, m = 7: order 3 — a shorter cycle 2 → 4 → 1, and 3 divides φ(7) = 6.
a = 3, m = 10: composite modulus; φ(10) = 4, ord(3) = 4 — a primitive root mod 10 (Euler: 3⁴ ≡ 1).
a = 2, m = 10: not coprime (gcd = 2) — the powers never reach 1, no inverse exists. The panel flags this in red.
a = 6, m = 12: another non-coprime case; watch the facts panel report that Euler's theorem does not apply.

The yellow tiles are the residues coprime to m; their count is φ(m). The cycle length (ord of a) always divides that count whenever a is coprime to m — this is exactly why a^φ(m) ≡ 1.

How the theorems show up

Fermat's little theorem appears when m is prime: then φ(m) = m − 1, and the facts panel shows a^m-1 ≡ 1 plus the inverse a^m-2.
Euler's theorem is the general statement a^φ(m) ≡ 1 for any coprime base — visible whenever the green "1" node is reached at step k = ord(a), a divisor of φ(m).
The order ord(a) is the number of Steps to return to 1 — the length of the blue arrow path around the circle.
Exponent reduction is the practical payoff: to compute a^e mod m you only need e mod ord(a) (or e mod φ(m)) — your position within the cycle shown here.

Self-contained visualization. Fermat's little theorem is the case m = prime (then φ(m) = m−1); Euler's theorem a^φ(m) ≡ 1 holds for every a coprime to m because ord(a) divides φ(m). See junior.md and professional.md for the proofs. When gcd(a, m) > 1 the powers never reach 1 (no cycle through 1) — the animation flags this.