mathschallenge.net

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$² will not be a permuation of φ($p$²).

Solution

As 1, 2, 3, ... , $p$1 are relatively prime to $p$, it can be seen that φ($p$) = $p$1. Except for $p$ = 2, for which φ(2) = 1 anyway, all other primes are odd, which means the final digit will be 1, 3, 5, 7, or 9. As $p$1 will only change the final digit (tens and above will be unaffected), and will change it to 0, 2, 4, 6, or 8, respectively, we can see that φ($p$) cannot be a permutation of $p$.

For $p$² we can see that it will divide by 1$p$, 2$p$, ... , $p$$p$, hence φ($p$²) = $p$²$p$ = $p$($p$1).

With the exception of 3, for which φ(3) = 2 anyway, $p$ 1,2 mod 3, so $p$1 0,1 mod 3, and $p$($p$1) 0,2 mod 3. Similarly, $p$² = $p$$p$ 1 mod 3.

It is well known that a number and the sum of its digits are congruent mod 3, which means that two numbers that are permutations of one another will be congruent mod 3. As we have shown that $p$² 1 mod 3 and φ($p$²) 0,2 mod 3, we prove that they can never be permutations of each other.

Prove that $p$^$k$ can never be a permutation of φ($p$^$k$).