How to solve $\phi(n)=78$?

Question

How to solve $\phi(n)=78$?

One of the numbers is $79$ because the value of Euler's function for prime numbers is $\phi(n)=n-1$. It also holds for $79\cdot2=158$ because the only numbers that are not relatively prime to $158$ are even numbers and number $79$. I'm not sure if this is enough of an explanation.

Then I tried like this: I know that, if $n=\displaystyle \prod_{i=1}^k p_i^{\alpha_i} \Rightarrow \phi(n) = \displaystyle \prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$.

Factoring $78$, I get $78=2\cdot3\cdot13$ so that means is some combination of $\prod_{i=1}^k p_i^{\alpha_i-1} (p_i-1)$ but how do I find which combination?

I first tried with $13$.

• Let's say that $13|(p-1)$ with $p|n$, which means $p=13k+1$, but there are no such numbers because they are either too big for $\phi(n)=78$ to hold or they aren't prime numbers.
• Then I tried with $13|p$. Which means $(13-1)|\phi(n)$. And that isn't true.

What should I do? Do the same thing with $2$ and $3$?

Answer 1

the factors of $78 = 2*3*13$. and $\phi(n) = \prod p_i^{a_i - 1}(p_i -1)$

Now $13$ is either $p_i$ or a factor of a $p_i - 1$.

If $13$ is a $p_i$ than $13-1 =12$ would divide $\phi(n) = 78$ which it doesn't. So $13$ must be a factor of some $p_i -1$.

If $13 = p_i -1$ then $p_i =14$ which isn't prime so $13$ most be a proper factor of $p_i - 1$. But the only other factors available are $2,3$.

So $p_i - 1 = 2*13, 3*13$ or $6*13$. But $2*13+1 = 27$ and $3*13+1 = 40$ and $6*13+1 = 79$ and of those only $79$ is prime.

So we must represent $78$ as $ = 79^0(79 - 1)*\prod_{p_i|n;p_i\ne 79} p_i^{a_i -1}(p_i -1)$. That is the only way we can take the factor of $13$ into account.

But that means $\prod_{p_i|n;p_i\ne 79} p_i^{a_i -1}(p_i -1) =1$.

So either $78$ is represented and $79^0(79-1)$ and $n = 79$ or $78$ is represented as $79^0(79-1) \cdot 2^0(2-1)$ and $n = 158$.

Those are the only two options.

Answer 2

We have $\phi(n)\ge 84$ for all $n\ge 400$, see the estimates here, with $\delta=1/47$:

Is the Euler phi function bounded below?

We easily see form the list of values of $\phi(n)$ for $n\le 400$, that $n=78,158$ are the only possibilities.

A related question: For which primes $p>2$ are there more than two values $n$ such that $\phi(n)=p-1$? For example, $p=7$ has more values: $\phi(n)=6$ for $n=7,9,14,18$

Answer 3

You have shown that since $13|\phi(n)$, there must be a prime $p$ dividing $n$ such that $13 | p-1$, which in turn means $p=13k+1$.

Now if $p|n$ then $p-1 | \phi(n)$, which means that you can bound $p \leq \phi(n)+1=79$.

Putting both conditions together, the list of possible $p$ is $$ p\in \{53, 79\} $$ If $p=53$, then $p-1=2^2\cdot 13$ divides $\phi(n)$ and hence $4 | \phi(n)=78$, which is not possible. So this forces $p=79$ to divide $n$, or we cannot get factor $13$ in $\phi(n)$. In addition, due to the size of this $p$ we can also conclude that $p^2\not | n$, or else $79|\phi(n)$.

Finally, $$ \begin{align*} 78 &= \phi(n) = \phi(n/p)\phi(p)=\phi(n/p)\cdot 78\\ 1 &= \phi(n/p) \end{align*} $$ Therefore $n/p$ must be either $1$ or $2$. This shows that $n=79$ or $158$.

In short: using $13|\phi(n)$ does work as it gives you a list of $p$ to try, which in turn then reduces the problem to solving a set of small $\phi(n/p)$.