A necklaces has N beads and A different colors for each bead. Two necklaces are considered the same if one can be rotated to make the other.

Observations

Consider a necklace with 4 beads and 2 different colors of beads. The total number of lines of beads would be 2^4. Now subtract of all of thes lines that can rotate to become itself in less than 4 rotations.

Think about splitting 4 into 2 and 2. Setting the first 2 and the second 2 to be the same string would lead to a rotation by 2 creating the same string. For example if they are both 10...

original first rotation second rotation third rotation 1010 ----> 0101 ----> 1010 ----> 0101

If we subtract of all the possible ways to make the 2 beads (2^2) is the total number of lines that can be rotated into themselves, If we subtract of 4 from our original number, we get there to be 12 total lines that can be created without the lines repeating themselves with less than 4 rotations.

Since we know that 12 lines never repeat themselves with less than 4 rotations, we realize that this number has to be divisible by 4, since for each string, all 3 of its rotations are also part of the 12.

1000, 0100, 0010, 0001 are all part of the 12 strings and are rotations of each other 1100, 0110, 0011, 1001 are all part of the 12 strings and are rotations of each other 1110, 0111, 1011, 1101 are all part of the 12 strings and are rotations of each other

This means that this value after subtracting of all the ways to rotate and repeat early has to be divisible by the total number of beads. Although, it will not always be as simple as subtracting of one case because of over-counting (explained later).

Prime length Necklaces

In the case with the number of beads as 4, it was able to be split into multiple 2s (a factor of 4). Since prime length necklaces don't have any factors other than 1 and itself, it has to be split into all 1s.

Consider a necklace with 7 beads and 2 different colors of beads. There are 2^7 different lines of beads, and the only 2 cases that repeat themselves are all one color or all the other color.

Subtracting off these two cases gives 2^7-2, and as previously shown this value has to be divisible by 7, because all thats left are strings that have all 6 of there rotations part of the 2^7-2. Therefore 2^7 is congruent to 2 mod 7, or 2^6 is congruent to 1 mod 7.

Lets generalize this: consider a necklace with N beads and K different colors of beads. There are K^N different lines of beads, and only case where they repeat themselves are all the same color (K different colors). This means that K^N-K is congruent to 0 mod N, or K^N-1 congruent to 1 mod N. Fermat's little theorem is proved

Composite length Necklaces

With a composite length necklace, look through all the divisors and choose to either add, subtract them, or don't do anything. Think about it like this, all the factors should be removed from the total eventually, and if a factor is removed, and factor of the factor is also removed, turning into somewhat of an inclusion-exclusion problem.

look at the case for N as 12 and 2 different bead colors. The answer is 2^12 (split into 1, 2, 3, 4, 6, 12 groups) — 2^6 (1, 4) — 2^4 (-1, 2 (2 is subtracted)) + 2^2 (1). To find out which factors are added, subtracted, and neither though is the really cool part. Write each term as 2^(12/k) for k as divisors of 12.

2^(12/k) counts all multiples of k. If you add all ks with an even amount of prime factors and subtract all ks with an odd amount of prime factors everything works perfectly. First add 2^(12/1) (1 has 0 (even) prime factors) adding all multiples of 1. Then subtract 2^(12/2) and 2^(12/3) (2 and 3 have 1 (odd) prime factors). Now add back 2^(12/6) (6 has 2 (even) prime factors). This cancels everything. Here is the proof:

For a k with odd prime factors the times it has already been added is: N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... + N choose N-1 (k multiple of N-1 (even) primes). Due to the fact that odd chooses and even chooses are equal, it cancels out to be counted just 1 time (the last N choose N hasn't been subtracted). This proves that we have to subtract the odd powers.

For a k with even prime factors the times it has already been added is: N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... — N choose N-1 (k multiple of N-1 (odd) primes). Due to the fact that odd chooses and even chooses are equal, it cancels out to be counted just -1 times (the last N choose N hasn't been added). This proves that we have to add the odd powers.

Finally or a number k that is a multiple of a perfect square, it completes the bionomial. N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... + or minus N choose N (because the final is just the product of the prime divisors without any powers) Since all the rest of the multiples of perfect squares are also 0, all other divisors of a multiple of a perfect square contributes to 0. The entire binomial cancels out with 0 for all multiples of perfect squares.

There is a special function that gives 1 if the number has even number of prime divisors, -1 if it has odd prime number of divisors, and 0 if it is a multiple of a perfect square regardless of prime divisors. Idk how to get mu so I'll just call it m(a).

[sum for all d as a divisor of p] m[d]*a^(p/d) is congruent to 0 mod p - Gauss's Necklace Formula