mathschallenge.net logo

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


Solution

As 1, 2, 3, ... , pminus1 are relatively prime to p, it can be seen that φ(p) = pminus1. 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 pminus1 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 p2 we can see that it will divide by 1timesp, 2timesp, ... , ptimesp, hence φ(p2) = p2minusp = p(pminus1).

With the exception of 3, for which φ(3) = 2 anyway, p congruent 1,2 mod 3, so pminus1 congruent 0,1 mod 3, and p(pminus1) congruent 0,2 mod 3. Similarly, p2 = ptimesp congruent 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 p2 congruent 1 mod 3 and φ(p2) congruent 0,2 mod 3, we prove that they can never be permutations of each other.

Prove that pk can never be a permutation of φ(pk).

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

Only Show Problem