# On $\varphi(m)\varphi(n)\equiv0\pmod{m+n}$

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?

• 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. – Stanley Yao Xiao Jun 24 '18 at 11:10
• 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$. – Stanley Yao Xiao Jun 24 '18 at 13:34
• 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. – Gerhard Paseman Jun 24 '18 at 16:13
• 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)$. – 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.