LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A tuple fixed by a cyclic rotation is determined by a shorter periodic block

Statement

Let $m \geq 1$ , let $0 \leq r < m$ , and put $d : = \gcd (m, r)$ . For an $m$ -tuple $u = (u_{0}, \dots, u_{m - 1})$ , the following are equivalent:

rotation by $r$ places fixes $u$ ;
whenever $i \equiv j (m o d d)$ , one has $u_{i} = u_{j}$ ;
there is a $d$ -tuple $(b_{0}, \dots, b_{d - 1})$ such that $u_{i} = b_{i m o d d}$ for every $i$ .

In particular a tuple fixed by rotation by $r$ places is determined by its first $d$ entries and is obtained by repeating that shorter block exactly $m / d$ times.

Facts & Assumptions

Given: Integers $m \geq 1$ and $0 \leq r < m$ , the integer $d : = \gcd (m, r)$ , and an $m$ -tuple $u = (u_{0}, \dots, u_{m - 1})$ .

[L1]

The congruence $r q \equiv t (m o d m)$ is solvable exactly when $\gcd (r, m) ∣ t$ (For $n \geq 1$ , $a x \equiv b (m o d n)$ is solvable exactly when $\gcd (a, n) ∣ b$ , and then has exactly $\gcd (a, n)$ solution classes modulo $n$ ).

Proof

technique · direct

1.1given

Assume rotation by $r$ places fixes $u$ . Then one application of the rotation gives $u_{i} = u_{i + r m o d m}$ for every index $i$ , and iterating gives $u_{i} = u_{i + q r m o d m}$ for every $q \geq 0$ .

1.2givenconstruct

If condition 2 holds, define $b_{s} : = u_{s}$ for $0 \leq s < d$ . Every index $i$ has a unique residue class modulo $d$ , and condition 2 makes $u_{i}$ depend only on that class, so $u_{i} = b_{i m o d d}$ for every $i$ . This is condition 3.

2.1step 1.1L1

If $i \equiv j (m o d d)$ , then $d ∣ (j - i)$ . Since $\gcd (r, m) = d$ , [L1] gives an integer $q$ with $r q \equiv j - i (m o d m)$ , and step 1.1 therefore gives $u_{i} = u_{j}$ . This proves 1 implies 2.

2.2step 1.2L1algebra

If condition 3 holds, then $d ∣ r$ , so $(i + r) m o d d = i m o d d$ for every $i$ . Hence $u_{i + r m o d m} = b_{(i + r) m o d d} = b_{i m o d d} = u_{i}$ , so rotation by $r$ places fixes $u$ . Thus 3 implies 1.

3.1step 2.1step 1.2step 2.2∎

Steps 2.1, 1.2, and 2.2 prove the equivalence of the three conditions and the final periodic-block description.

Depends on

Used by

Over a commutative ℚ-algebra, CYC(A) has generating function ∑_k≥ 1φ(k)/k log1/1-A(xᵏ) Theorem

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics (standard reference, not scraped)