Euler's totient function $\varphi$ is multiplicative, and it plays important roles in number theory.

QUESTION: Is it true that for each integer $m>6$ we have $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$ for some positive integer $n$?

For every $m=7,\ldots,10^4$, I have found the smallest positive integer $n$ such that $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$ (cf. http://oeis.org/A248007). For example, for $m=10$ the least positive integer $n$ with $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$ is $14$; in fact, $$\varphi(10)\varphi(14)=4\times 6\equiv0\pmod{10+14}.$$

I formulated the above question in 2014 and conjectured that the answer should be positive. I have ever mentioned this question to some number theorists, but there is no substantial progress on the question.

I don't think that the question is very difficult. Any ideas towards its solution?

  • 1
    $\begingroup$ This is trivial if $m$ is prime: just take $n = m - 2$ (which is necessarily odd, since $m > 6$). Then $m + n = 2m-2 = 2 \phi(m)$, and $\phi(m) \phi(n)$ is an even multiple of $\phi(m)$, since $n$ is odd. I suspect a slight modification of this argument should work in general. $\endgroup$ – Stanley Yao Xiao Jun 24 '18 at 11:10
  • 1
    $\begingroup$ Indeed the same argument works whenever $\phi(m)/m > 1/2$ and $m$ is odd. The obvious generalization is quite tricky: taking $k$ to be the least positive integer such that $2^k \phi(m) > m$, in order for this argument to work one would need to show that $2^k | \phi(2^k \phi(m) - m)$. This is true whenever $2^k \phi(m) - m$ has at least $k$ distinct odd prime divisors, but this is by no means guaranteed when $k > 1$. $\endgroup$ – Stanley Yao Xiao Jun 24 '18 at 13:34
  • $\begingroup$ All that is needed is a value of $t$ large enough so that $n=t\phi(m)-m$ and $\phi(n)$ is a multiple of $t$. If $t$ in addition divides both $m$ and $\phi(m)$, you are done (or pretty close). The challenge then is when this is not the case. Gerhard "Bet Euler Could Find It" Paseman,2018.06.24. $\endgroup$ – Gerhard Paseman Jun 24 '18 at 16:13
  • 2
    $\begingroup$ It's enough to check the conjecture when $m$ is squarefree or $m \in \{8, 9, 12, 18, 25\}$. Indeed, let $m \in \mathbf N_{\ge 2}$ and suppose that $m+n \mid \varphi(m) \varphi(n)$ for some $n \in \mathbf N^+$. If $p$ is a prime divisor of $m$, then $\varphi(mp) = p \varphi(m)$. Moreover, either $p \nmid n$, and hence $\varphi(np) = (p-1) \varphi(n)$; or $p \mid n$, and hence $\varphi(np) = p \varphi(n)$. In any case, $(m+n)p \mid p \varphi(m) \varphi(n) \mid \varphi(mp) \varphi(np)$. $\endgroup$ – Salvo Tringali Jun 24 '18 at 22:21

If there are counterexamples, they are likely to be square free and very large. Here's why.

Suppose $ t^2 $ divides $ m$ and $ t$ is larger than $O( \log p ),$ with $ p$ the largest prime divisor of $m$ (it is enough that $ t$ is larger than $ m/\phi(m) )$. Then $n= t\phi(m) - m$ is a positive multiple of $t^2$, so $t$ divides $ \phi(n)$, and $n,m$ then solves the desired congruence. One can fine tune this to smaller $t$ for certain $m$, but the point now is to look at solving the problem for a given and mostly squarefree $m$.

Edit 2018.06.27 GRP

A couple more thoughts.

Let $t$ be a common factor of $m$ and $\phi(m)$. If $n=\phi(t)\phi(m) - m$ is positive, this is another solution which works.

Otherwise, $m$ and $\phi(m)$ are mostly coprime, and we seek an integer $t$ such that $n$ above is positive and so that $n$ is a multiple of $t$. (More generally, for $d$ a large divisor of $\phi(m)$ we could instead look at $n=\phi(t)d -m$ being a multiple of $t$, but I won't do that now.) By running through $t$ (and thus $\phi(t)$) being 3-smooth numbers, we may encounter an $n$ having enough prime factors of the form 6k+1 distinct from factors of $m$ and factors $\phi(m)$ that will yield a solution. As remarked by Stanley above, it is not clear how to guarantee enough of these factors of $n$ to appear.

END Edit 2018.06.27 GRP

Gerhard "Sure Euler Could Solve It" Paseman, 2018.06.24.

| cite | improve this answer | |

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.