Is a prime? I will assume that is a prime.
We will prove this for i.e. if where . Now say we can write and where is a disjoint permutation with and . This means commutes with and . Thus, and henceforth . We can write as a product of disjoint cycles and as a product of disjoint cycles. We want to show . Based on the reasoning above we can assume that each and are different. It follows that and . Since are non-identity elements it means we have expressed as a product of disjoint cycles (for are cycles - this is because is a prime!). Therefore, not only but it must be that we can rearrange them so that . Note, it is impossible that and . This means that . Now by the Cayley's theorem and finite group and be embedded in the symmetric group. Since this result applies to symmetric groups it will apply to its subgroups as well. Thus, this is true for any finite group and a prime .
What if is not a prime?
Perhaps, there is a conterexample - but I am too lazy to try to find one now.
Say has exactly one solution (trivial one) and . Then it must be that has exactly one solution for each a prime. Now if it means (by the above post). If is prime then it would be that . Otherwise let be prime divisor of and arrive at . Keep on doing this until you exhaust all the primes and arrive that .