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?
$\endgroup$ 12 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ 2
