Q6 Matemática  (CentroAmerican 2004)

Com pérolas de cores diferentes formam colares, diz-se que um colar é primoroso se não puder ser decomposto em colares de pérolas do mesmo comprimento e iguais entre si. Sejam $n$ e $q$ inteiros positivos. Prove que o número de colares primos com $n$ contas, cada um com uma das $q^n$ cores possíveis, é igual a $n$ vezes o número de colares primos com $n^2$ pérolas, cada um deles que tem uma das cores $q$ possíveis. Nota: dois colares são considerados iguais se tiverem o mesmo número de pérolas e você pode obter a mesma cor em ambos os colares, girando um deles para combinar com o outro.