MathDB

With pearls of different colours form necklaces, it is said that a necklace is prime if it cannot be decomposed into strings of pearls of the same length, and equal to each other. Let

n

and

q

be positive integers. Prove that the number of prime necklaces with

n

beads, each of which has one of the

q^n

possible colours, is equal to

n

times the number of prime necklaces with

n^2

pearls, each of which has one of

q

possible colours.
Note: two necklaces are considered equal if they have the same number of pearls and you can get the same colour on both necklaces, rotating one of them to match it to the other.

Problem Statement