# rigorous proof of simple phenomenon

Suppose we want to prove the following simple statement rigorously -

If the number of beads in a necklace is $$n$$ then there exists a colored (suppose we have infinitely many colors at our disposal) necklace of minimal period $$k$$ (rotations) iff $$k|n$$.

Intuitively this seems obvious, but how do you make a rigorous proof?

EDIT : I think i figured this one : given that for some string of length $$n$$, $$k$$ is the minimal period, use the euclidean algorithm to get $$n=qk+r$$, $$0\leq r. Then it is easy to see that the string is also $$r$$-periodic (because it is $$n$$-periodic & $$qk$$-periodic). So $$r=0$$ because $$k$$ is minimal. The other direction of the proof is quite easy - just break up the string into chunks of $$k$$ beads, color every bead differently and repeat for all chunks.

• Make a period with $k-1$ red and $1$ blue, what's the problem ?
– user65203
Jun 29 '20 at 20:31
• @YvesDaoust The other direction of the double-implication. Jun 29 '20 at 20:37
• How do you define the period if $k\not|n$ ?
– user65203
Jun 29 '20 at 21:18
• @YvesDaoust $\forall i$ Color(Bead$_{i}$) = Color(Bead$_{i+k}$) Jun 29 '20 at 21:24

If $$k\not|n$$ and the period is $$k$$, then take every other $$k^{th}$$ beads. After several turns, you will get $$\dfrac n{\gcd(k,n)}$$ different positions, spaced by $$\dfrac{k}{\gcd(k,n)}$$, holding beads of the same color. Hence the period is $$\gcd(k,n), a contradiction.
E.g. $$k=6,n=15\to\gcd(k,n)=3$$.
The beads $$0,6,12,3,9$$ ($$5$$ of them) have the same color; also $$1,7,13,4,10$$ and $$2,8,14,5,11$$. Hence $$0,1,2$$ is a period !?