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.