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$?

  • $\begingroup$ There are none with two odd prime factoirs, because if $p,q$ are distinct odd primes, then $\phi(p^aq^b\dots)$ is divisible by $4$. $\endgroup$ – Thomas Andrews Feb 1 '18 at 16:07
  • $\begingroup$ And since $78$ is square-free, this means either $n=p, n=p^2,n=2p,n=2p^2$ for some odd prime $p$. (Technically, we have to eliminate the powers of $2$, but that's easy.) $\endgroup$ – Thomas Andrews Feb 1 '18 at 16:14
  • $\begingroup$ Did you read the question? @Moo "One of the numbers is 7979 .... It also holds for 79⋅2=158" $\endgroup$ – Thomas Andrews Feb 1 '18 at 16:15
  • $\begingroup$ "What should I do? " Well, you've just determined there's no other way to interpret $13$ being a factor of $78$. So, that means no other way to do this. You are done. No need to check 2 or 3 because whatever you find they won't be able to make use of the $13$. $\endgroup$ – fleablood Feb 2 '18 at 8:02

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.


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$


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)$.


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.