# If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even?

If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even?

Here, $\varphi(x)$ is Euler's phi function, the number of positive integers less than or equal to $x$ that are relatively prime to $x$.

It appears that when $\varphi(x) = m$ has exactly two solutions then one of the solutions, $x$, is odd and the other solution is even, specifically $2\times x$. The first few integers $x$ such that $\varphi(x) = m$ has exactly two solutions are: $1,11,23,29,31,47,53,81,59,\dots$ where the other solution is necessarily $2\times x$. For example, $\varphi(81) = \varphi(162) = 54$ and there are no other integers $k$ such that $\varphi(k) = 54$. See the sequence $A007366$ in Sloane's OEIS. I determined that the initial terms of this sequence were all odd with a brute force Mathematica code that is accurate (and timely) for about $1000$ terms.

The emperical evidence suggests that if $\varphi(x) = m$ has exactly two solutions then exactly one of them is odd. I want to prove this statement.

It is straight forward to show that both solutions cannot be odd since if $x$ is odd then $\varphi(x) = \varphi(2\times x)$.

I am considering the case where both solutions are even, hoping for a contradiction. I have determined that if both solutions, say $x$ and $y$, are even then $x$ and $y$ are both divisible by $4$. Also, in this case, at least one of $x$ or $y$ is divisible by $3$. Now I am stuck. Is there some way to reach a contradiction here.

Is there another way to prove (or attempt to prove) the conjecture?

• If for some $p$ there is a $(q<p:\phi(2p) = \phi(2q) \wedge \forall k\not\in \{2p,2q\} \phi(k) \neq \phi(2q)$ then there is a smallest such $p$. Now, you know that $\phi(p) = \phi(q)$ since $\phi$ is multiplicative. Can you now show that a third solution $\phi(m) = \phi(q), m \not\in \{p,q\}$ allows construction of a$k\not\in \{2p,2q\} :\phi(k) = \phi(2q)$ ? – Mark Fischler Apr 21 '16 at 22:50
• perhaps you could list the first dozen such $m$ where $m+1$ is NOT prime, along with the two values of $x...$ – Will Jagy Apr 21 '16 at 23:05
• @ Mark Fischler. In your post are you assuming p and q are primes? ? If you are I do not know why? If you are not then how do I know that phi(p) = phi(q)? phi is multiplicative but it is not completely multiplicative. right? – Geoffrey Critzer Apr 21 '16 at 23:12

As I requested, here are the first twenty examples of numbers $m$ with two answers to $\phi(x)=m.$ I did not print out when $m+1$ was prime, those are the majority of the $m'$s

54 = 2 * 3^3     81 = 3^4     162 = 2 * 3^4
110 = 2 * 5 * 11     121 = 11^2     242 = 2 * 11^2
294 = 2 * 3 * 7^2     343 = 7^3     686 = 2 * 7^3
342 = 2 * 3^2 * 19     361 = 19^2     722 = 2 * 19^2
506 = 2 * 11 * 23     529 = 23^2     1058 = 2 * 23^2
580 = 2^2 * 5 * 29     649 = 11 * 59     1298 = 2 * 11 * 59
812 = 2^2 * 7 * 29     841 = 29^2     1682 = 2 * 29^2
930 = 2 * 3 * 5 * 31     961 = 31^2     1922 = 2 * 31^2
1144 = 2^3 * 11 * 13     1219 = 23 * 53     2438 = 2 * 23 * 53
1210 = 2 * 5 * 11^2     1331 = 11^3     2662 = 2 * 11^3
1456 = 2^4 * 7 * 13     1537 = 29 * 53     3074 = 2 * 29 * 53
1540 = 2^2 * 5 * 7 * 11     1633 = 23 * 71     3266 = 2 * 23 * 71
1660 = 2^2 * 5 * 83     1837 = 11 * 167     3674 = 2 * 11 * 167
1780 = 2^2 * 5 * 89     1969 = 11 * 179     3938 = 2 * 11 * 179
1804 = 2^2 * 11 * 41     1909 = 23 * 83     3818 = 2 * 23 * 83
1806 = 2 * 3 * 7 * 43     1849 = 43^2     3698 = 2 * 43^2
1936 = 2^4 * 11^2     2047 = 23 * 89     4094 = 2 * 23 * 89
2058 = 2 * 3 * 7^3     2401 = 7^4     4802 = 2 * 7^4
2162 = 2 * 23 * 47     2209 = 47^2     4418 = 2 * 47^2
2260 = 2^2 * 5 * 113     2497 = 11 * 227     4994 = 2 * 11 * 227


In the examples where the odd $x$ is squarefree, it seems that the prime factors are always $2 \pmod 3.$

• @ Will Jagy. Thank you. I agree with your above data. – Geoffrey Critzer Apr 22 '16 at 22:50

I started finding $m$ such that there were exactly two $x,$ multiples of $4,$ with $\phi(x) = m.$ The total number of solutions gets rather large. Meanwhile, the most frequent is just $x = 8p,$ $y = 12 p$ for prime $p > 5.$ So $m=4p.$ But we also get $z=5p.$

After that pattern, there are just more patterns. We can see how to get a third $x$ value in all the examples below. However, there do seem to be new patterns cropping up, so there is no finite number of patterns to make a proof.

count:  8 m: 36 = 2^2 * 3^2 X: 37 = 37 X: 57 = 3 * 19 X: 63 = 3^2 * 7 X: 74 = 2 * 37 X: 76 = 2^2 * 19 X: 108 = 2^2 * 3^3 X: 114 = 2 * 3 * 19 X: 126 = 2 * 3^2 * 7

count:  6 m: 84 = 2^2 * 3 * 7 X: 129 = 3 * 43 X: 147 = 3 * 7^2 X: 172 = 2^2 * 43 X: 196 = 2^2 * 7^2 X: 258 = 2 * 3 * 43 X: 294 = 2 * 3 * 7^2

count:  8 m: 200 = 2^3 * 5^2 X: 275 = 5^2 * 11 X: 303 = 3 * 101 X: 375 = 3 * 5^3 X: 404 = 2^2 * 101 X: 500 = 2^2 * 5^3 X: 550 = 2 * 5^2 * 11 X: 606 = 2 * 3 * 101 X: 750 = 2 * 3 * 5^3

count:  8 m: 324 = 2^2 * 3^4 X: 489 = 3 * 163 X: 513 = 3^3 * 19 X: 567 = 3^4 * 7 X: 652 = 2^2 * 163 X: 972 = 2^2 * 3^5 X: 978 = 2 * 3 * 163 X: 1026 = 2 * 3^3 * 19 X: 1134 = 2 * 3^4 * 7

count:  8 m: 920 = 2^3 * 5 * 23 X: 1175 = 5^2 * 47 X: 1383 = 3 * 461 X: 1551 = 3 * 11 * 47 X: 1844 = 2^2 * 461 X: 2068 = 2^2 * 11 * 47 X: 2350 = 2 * 5^2 * 47 X: 2766 = 2 * 3 * 461 X: 3102 = 2 * 3 * 11 * 47

count:  20 m: 936 = 2^3 * 3^2 * 13 X: 937 = 937 X: 1007 = 19 * 53 X: 1027 = 13 * 79 X: 1099 = 7 * 157 X: 1183 = 7 * 13^2 X: 1413 = 3^2 * 157 X: 1431 = 3^3 * 53 X: 1521 = 3^2 * 13^2 X: 1659 = 3 * 7 * 79 X: 1874 = 2 * 937 X: 2014 = 2 * 19 * 53 X: 2054 = 2 * 13 * 79 X: 2198 = 2 * 7 * 157 X: 2212 = 2^2 * 7 * 79 X: 2366 = 2 * 7 * 13^2 X: 2826 = 2 * 3^2 * 157 X: 2844 = 2^2 * 3^2 * 79 X: 2862 = 2 * 3^3 * 53 X: 3042 = 2 * 3^2 * 13^2 X: 3318 = 2 * 3 * 7 * 79

count:  12 m: 972 = 2^2 * 3^5 X: 1141 = 7 * 163 X: 1461 = 3 * 487 X: 1467 = 3^2 * 163 X: 1539 = 3^4 * 19 X: 1701 = 3^5 * 7 X: 1948 = 2^2 * 487 X: 2282 = 2 * 7 * 163 X: 2916 = 2^2 * 3^6 X: 2922 = 2 * 3 * 487 X: 2934 = 2 * 3^2 * 163 X: 3078 = 2 * 3^4 * 19 X: 3402 = 2 * 3^5 * 7

count:  6 m: 984 = 2^3 * 3 * 41 X: 1079 = 13 * 83 X: 1743 = 3 * 7 * 83 X: 2158 = 2 * 13 * 83 X: 2324 = 2^2 * 7 * 83 X: 2988 = 2^2 * 3^2 * 83 X: 3486 = 2 * 3 * 7 * 83

count:  12 m: 1176 = 2^3 * 3 * 7^2 X: 1247 = 29 * 43 X: 1379 = 7 * 197 X: 1421 = 7^2 * 29 X: 1715 = 5 * 7^3 X: 1773 = 3^2 * 197 X: 2494 = 2 * 29 * 43 X: 2744 = 2^3 * 7^3 X: 2758 = 2 * 7 * 197 X: 2842 = 2 * 7^2 * 29 X: 3430 = 2 * 5 * 7^3 X: 3546 = 2 * 3^2 * 197 X: 4116 = 2^2 * 3 * 7^3

count:  6 m: 1232 = 2^4 * 7 * 11 X: 1851 = 3 * 617 X: 2001 = 3 * 23 * 29 X: 2468 = 2^2 * 617 X: 2668 = 2^2 * 23 * 29 X: 3702 = 2 * 3 * 617 X: 4002 = 2 * 3 * 23 * 29

count:  6 m: 1272 = 2^3 * 3 * 53 X: 1391 = 13 * 107 X: 2247 = 3 * 7 * 107 X: 2782 = 2 * 13 * 107 X: 2996 = 2^2 * 7 * 107 X: 3852 = 2^2 * 3^2 * 107 X: 4494 = 2 * 3 * 7 * 107

count:  8 m: 1368 = 2^3 * 3^2 * 19 X: 1603 = 7 * 229 X: 1805 = 5 * 19^2 X: 2061 = 3^2 * 229 X: 2888 = 2^3 * 19^2 X: 3206 = 2 * 7 * 229 X: 3610 = 2 * 5 * 19^2 X: 4122 = 2 * 3^2 * 229 X: 4332 = 2^2 * 3 * 19^2

count:  8 m: 1400 = 2^3 * 5^2 * 7 X: 1775 = 5^2 * 71 X: 2103 = 3 * 701 X: 2343 = 3 * 11 * 71 X: 2804 = 2^2 * 701 X: 3124 = 2^2 * 11 * 71 X: 3550 = 2 * 5^2 * 71 X: 4206 = 2 * 3 * 701 X: 4686 = 2 * 3 * 11 * 71

count:  10 m: 1640 = 2^3 * 5 * 41 X: 1681 = 41^2 X: 2075 = 5^2 * 83 X: 2463 = 3 * 821 X: 2739 = 3 * 11 * 83 X: 3284 = 2^2 * 821 X: 3362 = 2 * 41^2 X: 3652 = 2^2 * 11 * 83 X: 4150 = 2 * 5^2 * 83 X: 4926 = 2 * 3 * 821 X: 5478 = 2 * 3 * 11 * 83