## Relatively Prime Permutations

#### Problem

Euler's Totient function, φ(`n`), is used to determine the number of numbers less than `n` that are relatively prime to `n`. For example, φ(6) = 2, because only 1 and 5 are relatively prime with 6.

Interestingly, φ(63) = 36, and this is the first example of a number which produces a permutation of the value of its Totient function.

Given that `p` is prime, prove that `p` will not be a permutation of φ(`p`), and prove that `p`^{2} will not be a permuation of φ(`p`^{2}).

Problem ID: 240 (10 Aug 2005) Difficulty: 3 Star