Solving $\phi(n)=84$

Ok, I really need some help understanding this because either my brain isn’t working at the moment or I’m breaking math and I have a striking suspicion that one of those is more likely.

Anyways, here’s my process. WolframAlpha tells me there are 12 integer solutions, they are all $^+_-n$ so let’s say there are 6 of them. They are as follows: $129, 147, 172, 196, 258, 294$

Ok, so here’s how I attempted to solve it. $n$ looks like this ${\prod_{i=1}^kp_i^{\alpha_i}}$. And $\phi(n)=n\prod_{p\vert n}(1-\frac{1}{p})$. So I plug $n$ in and get an equation like this:

$\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=84$

Now, solving for $n$ SHOULD be equivalent to solving for $p_i, \alpha_i$, right?

So, I started going through possible values of $k$ and I’m interested in the case of $k=2$.

This means that $n$ has two prime factors, so it looks like $p_1^{\alpha_1}p_2^{\alpha_2}$, and the equation is:

$p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)=84$

Ok. Here’s my issue. Factoring $84$, we get $2\times2\times3\times7$

So I try to see a pattern. The first solution I came up with is $p_1=7, \alpha_1=2, p_2=2, \alpha_2=2$. Then I followed the same logic that led me to that solution but didn’t find any more so I concluded that the other solutions must be as higher values of $k$. But then I factored $172$ and saw that it also had only two primes. It also fits the pattern. So I realized that I could get ones in that product as a result of $p^0$ and following that pattern, filling in the remaining factors, I found the $129$ solution.

No more, the next one must be at $k=3$. NOPE. $147$ also factors into only 2 primes. So now I’m really at a miss. Is there a more effective way to iterate over all of these combinations?

Solutions Collecting From Web of "Solving $\phi(n)=84$"

Look at 7. Two possibilities:

  • $7|(p-1)$ with $p|n$:
    hence $p = 14k+1 \in \{ 29, 43\}$ (the others are too big).
  • If $p=29$, $\phi(n) = 28\times 3 = (29-1)(3)$. 3 has to be some $(p-1)p^{a-1}$ but $p=4$ is not prime.
  • If $p=43$, you have the solution $\phi(n) = 42\times 2\implies n = 43\times 3$ or
    $n = 43\times 2^2$.
  • Otherwise: $7|n$. $\phi(n) = 6\times 7\times 2\implies n= 7^2\times 3$ or $n= 7^2\times 2^2$.

I have used that $\phi(n) = 2\implies n\in\{3,4\}$.

  84         129 = 3 * 43
  84         147 = 3 * 7^2
  84         172 = 2^2 * 43
  84         196 = 2^2 * 7^2
  84         258 = 2 * 3 * 43
  84         294 = 2 * 3 * 7^2

I see, you had those.

I suppose what I would emphasize is this: $\phi$ is multiplicative. So it is determined by its behavior on prime powers. Next, $\phi (p^k)$ is always divisible by $p-1.$ So, we are required to have $(p-1) | 84,$ so out of that list of numbers with $\phi(n) | 84,$

   1           2 = 2
   2           3 = 3
   2           4 = 2^2
   4           5 = 5
   2           6 = 2 * 3
   6           7 = 7
   4           8 = 2^3
   6           9 = 3^2
   4          10 = 2 * 5
   4          12 = 2^2 * 3
  12          13 = 13
   6          14 = 2 * 7
   6          18 = 2 * 3^2
  12          21 = 3 * 7
  12          26 = 2 * 13
  12          28 = 2^2 * 7
  28          29 = 29
  12          36 = 2^2 * 3^2
  12          42 = 2 * 3 * 7
  42          43 = 43
  42          49 = 7^2
  28          58 = 2 * 29
  42          86 = 2 * 43
  42          98 = 2 * 7^2
  84         129 = 3 * 43
  84         147 = 3 * 7^2
  84         172 = 2^2 * 43
  84         196 = 2^2 * 7^2
  84         258 = 2 * 3 * 43
  84         294 = 2 * 3 * 7^2

the primes allowed are 2,3,5,7,13,29,43, I guess that’s it. Some evident prime powers that need to be considered as alternatives to just primes. Oh, 13 does not get used, because then you need $\phi(something) = 21,$ and $\phi$ is never odd unless it is exactly $1.$ Again, 9 does not get used, i don’t think there is any number with $\phi = 14,$ don’t remember why, but people ask that here fairly often so you can find an answer on MSE.. The bit about odd is fairly easy, if there is any odd prime factor $p,$ then $(p-1)$ is even. So all that is left is powers of $2.$