Given a necklace with $d$ beads and $p$ thieves where $p$ is a prime, we can fairly divide the necklace among the people using at most $(p-1)d$ cuts. I know this is true even if $p$ is a composite but I'm not sure how to prove it.
I assume it somehow uses the fact that a composite number can be factored into primes.
This follows from a repeated application of the theorem for primes.
Say that there $k = pq$ people. Group them into $q$ groups of of $p$ people, and think of each group as a person. We can split the necklace between these $q$ groups (in $\leq d(q-1)$ cuts) so that each group receives $\frac{1}{q}$ of the total beads.
In each group of $p$ people, however, we can further divide the necklace pieces (in $\leq d(p-1)$ cuts) so that each person receives $\frac{1}{p}\cdot \frac{1}{q}$ of the total number of beads. In total, we used at most $d(q-1) + qd(p-1) = d(pq-1)$ cuts, and each person received $\frac{1}{pq}$ of the total beads.