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).

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

Show Problem & Solution