Euler Phi Function - finding all solutions

**Paperwings** · November 2nd 2008, 05:20 AM

I have a question about finding all positive integers n such that

$\phi (n) = m$ where m is given.

For example $\phi (n) = 12$
===========================================

For this problem or any problem, how do you know that the possible number of solutions are finite and you are not missing any.

Regarding, to $\phi (n) = 12$ , here is how I approached it.

If p | n, then (p-1) | 12. So, the possible p - 1 =1, 2, 3, 4, 6, 12 since they are factors of 12.

As a result, the possible values of p = 2, 3, 4, 5, 7, 13 but since p is a prime that leaves only p = 2, 3, 5, 7, 13.

From here, how would I continue?

I know that $n = p_{1}^{a_{1}} .... p_{k}^{a_{k}}$ , then
$\phi (n) = \phi(p_{1}^{a_{1}})...\phi(p_{k}^{a_{k}})$ , so would I have to check every 1,2,...,k for each single p's?

Thank you for reading. Any help is greatly appreciated.

**Opalg** · November 2nd 2008, 11:28 AM

For smallish values of m, like m=12, it is possible to enumerate all the integers n with $\phi(n)=m$ , if you go about it systematically.

Remember that if $n=\prod p^\alpha$ is the factorisation of n into prime powers, then $\phi(n) = \prod p^{\alpha-1}(p-1)$ . So if you want to find the possible values of n with $\phi(n)=m$ , you should start by looking for all the factors of m of the form $p^{\alpha-1}(p-1)$ .

Let's take the example m=12. The factors of 12 that are of that form are

$1 = 2^0(2-1)\quad($ so $1 = \phi(2))$ ,
$2 = 3^0(3-1) = 2^1(2-1)\quad($ so $2 = \phi(3) = \phi(4))$ ,
$4 = 5^0(5-1)\quad($ so $4 = \phi(5))$ ,
$6 = 7^0(7-1) = 3^1(3-1)\quad($ so $6 = \phi(7) = \phi(9))$ ,
$12 = 13^0(13-1)\quad($ so $12 = \phi(13))$ .

The only ways that we can make 12 as a product of these numbers are $12=12 = \phi(13)$ , $12=1\times12 = \phi(2)\phi(13)$ , $12=2\times6 = \phi(3)\phi(7) = \phi(3)\phi(9) = \phi(4)\phi(7) = \phi(4)\phi(9)$ , and $12=1\times2\times6 = \phi(2)\phi(3)\phi(7) = \phi(2)\phi(3)\phi(9)$ .

Notice that there is no way to write 3 in the form $p^{\alpha-1}(p-1)$ , so we cannot make use of the factorisation $12=3\times4$ . On the other hand, there are two ways to write each of the numbers 2 and 6 in that form, which gives us four ways to make use of the factorisation $12=2\times6$ . Also, we can slip in a factor $1=\phi(2)$ to any factorisation that does not already include a term arising from a power of 2, such as $2=\phi(4)$ (but we can have, for example $12=1\times2\times6 = \phi(2)\phi(3)\phi(7)$ , where the 2 arises from $\phi(3)$ rather than $\phi(4)$ ).

Thus there are eight numbers n with $\phi(n)=12$ , namely 13, 21, 26, 27, 28, 36, 42 and 54.

Thread: Euler Phi Function - finding all solutions

LinkBack

Thread Tools

Display

Euler Phi Function - finding all solutions

Similar Math Help Forum Discussions

Error Bounds for Euler's Method, finding M and L

Euler's theorem question finding the remainder...

Euler Function phi(n)

Euler's Phi Function

Euler's Function

Search Tags