Solving functional equation $f(xy)=f(x+y)$ and Diophantine equations

Question

It is well known that the only solution is $f$ a constant function. However, by putting some restrictions on the functional equation, we might get other solutions, with potential implications to solving Diophantine equations or factoring an integer.

The restrictions are as follows: $f(xy)=f(x+y)$ if $x,y\geq 3$ are positive integers and $\gcd(x,y)=1$. Now my question is whether or not there is a non-constant function satisfying these requirements. I consider that $f(u)$ is defined for integers $u\geq 7$.

Let $f$ be a solution. I use the following notation: $u\sim v\bmod{f}$ if and only if $f(u)=f(v)$. This defines equivalence classes, just like modulo operators define residue classes. Various functional equations similar to the one discussed here, produce various sets of equivalence classes, in the same way that various moduli produce various sets of residue classes.

Link to Diophantine equations and factoring

This is just a trivial example to illustrate the concept. Using various non-constant $f$ solutions of various related functional equations, we can replace the equation $x^2 + y^2 = z^2$ by $(xy)^2 \sim z^2 \bmod{f}$ if we could come up with a large class of $f$'s that make the two equations equivalent. In short, we reduce an additive equation with $k$ variables (here $k=3$) to one having $k-1$ variables.

Likewise, factoring $z$ consists of finding $x,y$ such that $xy=z$. It is equivalent to solving the additive equation $x+y \sim z$ for various $f$'s, hopefully easier to handle once turned from a multiplicative into an additive problem.

But do non-constant solutions $f$ really exist?

That is my question. A corollary, assuming such functions exist, is how difficult they are to handle, and even whether finding such a function could be an unsolved problem for years to come.

If such non-constant functions exist and are rather simple, then Fermat's theorem would have been proved long ago. This makes me think that either they don't exist, or if they exist, they are a tough nut to crack.

Possible approach to finding a non-constant $f$

I define $f(u)$ as the smallest integer $v\geq 7$ such that $u\sim v \bmod{f}$. Again, see the analogy with residue classes.

Now let's start with $u=7$. We have $7=3+4$, thus $7\sim 12$. We have $12=5+7$, thus $7\sim 12\sim 35$. Apply the principle recursively, and you will get an infinite equivalence class for $7$. Does it cover all integers $\geq 7$? If yes the only solution for $f$ is $f(u)=7$ (a constant function).

Now let's start with $u=11$. We also end up with an infinite class, seemingly larger than the previous one, and apparently containing all prime numbers $>7$ and many non-primes. In particular

$$11 \sim 13 \sim 17\sim 19 \sim 23 \sim 24\sim 25 \sim 28 \sim 29 \sim 30\sim 31 \sim 36 \sim 37 \sim 40\sim 41$$

How many equivalence classes do we end up with? One? (then $f$ is constant.) Two? Three? More than three? Note that finding the equivalence classes consists of finding all the connected components of an undirected (infinite) graph.

If you prove that $7\sim 11$, that won't answer my question, but it will be a big blow, big enough that I may stop doing research on this topic. And I would accept the answer. Likewise, if you prove that $7$ and $11$ are not equivalent ($\bmod{f}$) it will show that a non-constant $f$ exists, and this would be a big encouragement.

Update

See solutions provided by readers. The possibility of the existence of a non-constant function $f$ was "too good to be true". That said, the functional equation discussed here is a particular case of $a f(xy)= b f(x+y) +c$ with $a,b,c$ integers. Or something more general like (say) $f(xy)=f(g(x+y))$ for some function $g$. Maybe a non-constant solution can be found in this setting. In the end, the goal is to transform an additive problem into a multiplicative one, or the other way around. And to do it in such a way that it leads to simplifications.

Answer 1

Too long for a comment. My guess is that for $x\geq 7$ we that that $f(x)=c$ by strong induction. We need to check the cases $7\leq x\leq 20$ by hand .

Let us now suppose we have $y\geq 20$ and integer. If it can be factored as $a\cdot b$ with $a,b\geq 3$ coprime then obviously $6\leq a+b<ab=y$ and we are done. Thus the only cases left are primes $p^k$ and $2p^k$ both being bigger than $20$.

For $2p^k$ we have two cases $p^k\equiv 1\pmod{3}$ and $p^k\equiv 2\pmod{3}$. For $p^k\equiv 1 \pmod{3}$ note that $$f(2p^k)=f(2p^k-5+5)=f(5(2p^k-5))=f(5\cdot 3^{a} (2p^k-5)/3^a)=f(5\cdot 3^a+(2p^k-5)/3^a)$$ where $a=v_3(2p^k-5)$. We are done unless $2p^k-5=3^a$. Of course we can now switch and do $f(2p^k-11+11)$ and similarly we will get that $2p^k-11$ is a power of $3$. It is easy to see that the only only solution to $3^a+6$ being also a power of $3$ is $a=1$ but this $3^2$.

The above argument violates the coprime condition when $p=5$ and $5^k\equiv 1\pmod{3}$ and $p=11$ and $11^k\equiv 1\pmod 3$. But for the first option this leads to $2\cdot 5^k-11$ being a power of $3$, and the second leads to $2\cdot 11^k-5$ being a power of $3$. But we can further write $2\cdot 5^k=2\cdot 5^k-17+17$ and same for $2\cdot 11^k$ and we get a contradiction.

For $p^k\equiv 2\pmod{3}$ we do the same trick $f(2p^k)=f(2p^k-7+7)$ and again unless $2p^k-7$ is a power of $3$ we win. Swiching with $13$ we obtain than also $2p^k-13$ is a power of $3$ and like above $p^k=8$ but this is not in the range.

For $p^k$ we have $f(p^k)=f(p^k-3+3)=f(3(p^k-3))$. Note that $3$ does not divide $p^k-3$. If $p\equiv 1\pmod{4}$ then $f(3(p^k-3))=f(6(p-3)/2)=f(6+(p^k-3)/2)$ and we have $6+(p^k-3)/2<p^k$. If $p^k\equiv 3\pmod{4}$ then $f(p^k-5+5)=f(5(p^k-5))=f(10 (p^k-5)/2)=f(10+(p^k-5)/2)$ and we are done.

We miss again the coprimality when $p=3$. We have $f(3^k)=f(3^k−5+5)=f(5(3^k−5))=f(5⋅2^a⋅(3^k−5)/2^a)$ so we are done unless $3^k−5$ is a power of 2. We can iterate the argument with 7 and we get $3^k−7$ is a power of 2 and this forces $k=2$.

Answer 2

• $7 \sim 12$ via $3, 4$
• $12 \sim 35$ via $5, 7$
• $35 \sim 264$ via $11, 24$
• $264 \sim 41$ via $8, 33$
• $41 \sim 420$ via $20, 21$
• $420 \sim 43$ via $15, 28$
• $43 \sim 156$ via $4, 39$
• $156 \sim 25$ via $12, 13$
• $25 \sim 66$ via $3, 22$
• $66 \sim 17$ via $6, 11$
• $17 \sim 52$ via $4, 13$
• $52 \sim 315$ via $7, 45$
• $315 \sim 44$ via $9, 35$
• $44 \sim 195$ via $5, 39$
• $195 \sim 28$ via $13, 15$
• $28 \sim 11$ via $4, 7$

A graph connecting all the integers from 7 to 20 (to cover the base cases for Vlad Matei's induction):