# Find all numbers $n$ such that $\phi (n) = 20$

I'm trying to find all values of $$n$$ that satisfy euler's phi function in the title.

I start by knowing $$n$$ cannot be a power of $$2$$ since $$\phi (n)$$ is not. Then, $$n$$ is divisible by an odd prime.

I try to find odd primes satisfying $$(p-1)|20$$ and so my list is $$3,5,11$$. Then, $$n=2^a3^b5^c11^d$$. I'm stuck here, since I don't know how to bound my exponents or what values to use.

I think $$a\leq 2$$ because $$2^2|\phi(n)$$. So far I have generated:

$$n=2^2\cdot 11, 2\cdot 3\cdot 11, 3\cdot 11$$, or $$44,66,33$$. This was done through trial and error i.e. sampling values for exponents and checking if they satisfy the phi function. Is there an algebraic way to determine the exponents / check if there are other solutions?

• $$\phi (n) = 20 \implies n = 25, 33, 44, 50, 66$$
– Moo
Oct 16 '18 at 12:00

## 2 Answers

I start by knowing $$n$$ cannot be a power of $$2$$ since $$\phi (n)$$ is not. Then, $$n$$ is divisible by an odd prime.

I try to find odd primes satisfying $$(p-1)|20$$ and so my list is $$3,5,11$$. Then, $$n=2^a3^b5^c11^d$$. I'm stuck here, since I don't know how to bound my exponents or what values to use.

This is good work so far. To continue, show that if $$p$$ is prime and $$p^x$$ divides $$n$$, then $$p^{x-1}$$ divides $$\phi(n)$$. Of the primes in your list ($$2, 3, 5, 11$$), which ones can have $$p^{x-1}$$ divides $$n$$, assuming $$x \ge 2$$?

What about if $$x \ge 3$$? In this case, $$p^2$$ would have to divide $$20$$.

This should let you narrow down to a finite (fairly small) number of possibilities for $$a$$, $$b$$, $$c$$, and $$d$$ in $$n = 2^a 3^b 5^c 11^d$$.

Use the fact that $$\phi$$ is multiplicative and the formula that for prime $$p\ \phi(p^n)=(p-1)p^{n-1}$$. That means that $$\phi(2^a3^b5^c11^d)=(2-1)2^{a-1}(3-1)3^{b-1}(5-1)5^{c-1}(11-1)11^{d-1}$$ where you delete the terms where the exponent is $$0$$. Clearly $$b, d$$ are at most $$1$$. There are not so many cases to check. You need to get exactly one factor of $$5$$ and there are not many ways to do that.

• I don't see how $b,d$ are clearly, at most $1$. I'm sorry, how is that evident? Oct 17 '18 at 0:53
• Because if $b \gt 1, \phi(n)$ will have a factor $3$ but $20$ does not. Oct 17 '18 at 4:46