How to solve $\phi(n)=78$? 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$?
 A: 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$
A: 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.
A: 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)$.
