11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$ ? $\endgroup$ – Mark Fischler Apr 21 '16 at 22:50
  • $\begingroup$ perhaps you could list the first dozen such $m$ where $m+1$ is NOT prime, along with the two values of $x...$ $\endgroup$ – Will Jagy Apr 21 '16 at 23:05
  • $\begingroup$ @ 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? $\endgroup$ – Geoffrey Critzer Apr 21 '16 at 23:12
1
$\begingroup$

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

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

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
$\endgroup$

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.