1
$\begingroup$

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$
1
  • $\begingroup$ $$\phi (n) = 20 \implies n = 25, 33, 44, 50, 66$$ $\endgroup$
    – Moo
    Oct 16 '18 at 12:00
1
$\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$
1
$\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
  • $\begingroup$ I don't see how $b,d$ are clearly, at most $1$. I'm sorry, how is that evident? $\endgroup$
    – fyb805
    Oct 17 '18 at 0:53
  • $\begingroup$ Because if $b \gt 1, \phi(n)$ will have a factor $3$ but $20$ does not. $\endgroup$ Oct 17 '18 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.