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<k$. 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.

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)<k$, 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 !?
