7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jun 24, 2018 at 11:10
  • 2
    $\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
    Commented Jun 24, 2018 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
    Commented Jun 24, 2018 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
    Commented Jun 24, 2018 at 22:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .