The wording is just ever so slightly different, however the problem is identical. Problem 3. Determine all functions $f: \mathbb{N} \to \mathbb{N}$ such that $n^2 + f(n)f(m)$ is a multiple of $f(n) + m$ for all natural numbers $m, n$.
Problem
Source: Indonesian MO (INAMO) 2020, Day 1, Problem 3, or APMO 2019 Problem 1
Tags: algebra, functional equation, APMO, 2020, Divisibility, Indonesia MO, Indonesian MO
13.10.2020 15:32
I claim the only function is $f(n) = n \quad \forall n \in \mathbb{N} $, this works since $f(n) + m = m+n \mid mn+n^2 = n^2 f(m)f(n) $. Let $P(m,n)$ be the assertion of $(m,n)$ into the equation, Let $p$ be a prime number, $$P(p,p) \rightarrow f(p) + p \mid p^2 + f(p)^2 \Leftrightarrow f(p) + p \mid p^2 + f(p)^2 + (p^2 - f(p)^2 ) = 2p^2 $$$$ \therefore f(p) + p \in \{ 2p, p^2 , 2p^2 \} \Leftrightarrow f(p) \in \{p , p^2 -p , 2p^2 - p\} $$This follows from the fact that $f(p) + p >0$. $$P(1,1) \rightarrow f(1) + 1 \mid f(1)^2 + 1 \Leftrightarrow f(1) + 1 \mid f(1)^2 + 1 +(1 - f(1)^2) = 2 \Leftrightarrow \boxed{f(1)=1} $$$$P(1,p) \rightarrow f(p)+1 \mid p^2 + f(p) \Leftrightarrow f(p) + 1 \mid p^2 -1 \cdots (1)$$If $f(p)=2p^2 - p $, we have $f(p)+1 = 2p^2 - p + 1 > p^2 +1 > p^2 -1 $, contradicting $(1)$, this is true since $p^2 > p \quad \forall p \in \text{prime} $. If $f(p)= p^2 - p $, we have $f(p) + 1 = p^2 -p +1 \mid p^2 -1 \Leftrightarrow p^2-p+1 \mid p-2$, thus for all $p >2$ we have $f(p) = p $, if $p=2$, we have $f(2) = 2^2 -2 =2$, thus $\boxed{f(p) = p \quad \forall p \in \text{prime}}$. We Let $S(n)$ be the set of primes not dividing $n$, since $n$ is finite, $S(n)$ must be an infinite set for any $n$, observe that for any prime $q \in S(k) $, we have $$P(k,q) \rightarrow k+q \mid q(f(k) +q) \Leftrightarrow k+q \mid q+f(k)-k-q= f(k) - k $$I claim that $f(k)-k=0$, Proof 1 :assume otherwise, then we must have finitely many divisors of $f(k)-k$, however, since all the elements in the set $S'(k)=k+S(k) $ are distinct, since for primes $q \neq r \Leftrightarrow 2k+q \neq 2k+r$, we must have infinitely many divisors, a contradiction. Proof 2 : Assume $f(k)-k \neq 0$, since $S(k)$ is an infinite set, we pick $Q \in S(k)$ large enough such that $Q > 2k^2 -3k$, we also must have $f(k)-k \geq 0 $, since if otherwise, then $ k-f(k) \geq k+Q \Leftrightarrow 0 > -f(k) \geq Q $, a contradiction. Now, we observe the following $$f(k)-k > k+ Q \Leftrightarrow f(k) \geq 2k+Q$$$$P(k,k) \rightarrow f(k)+k \mid f(k)^2+k^2 \Leftrightarrow f(k)+k \mid k^2 + f(k)^2 + k^2 -f(k)^2 =2k^2$$We get $$ 2k^2 \geq k+f(k) \geq 3k + Q \Leftrightarrow Q \leq 2k^2-3k $$A contradiction. Thus we get the only solution $\boxed{f(n)=n \quad \forall n \in \mathbb{N}}$.
13.10.2020 15:36
Can someone tell me what the "assertion" is?
13.10.2020 16:05
IMHO, the assertion of (m; n) is the same thing as when we substitute values for (m; n)
06.12.2021 23:31
$P(1,1)$ gives $f(1)=1$ Using introduction we are done. Suppose that $f(n-1)=n-1$ then $f(n)=n$ $P(n,n-1)$ gives: $f(n)+n-1|n^2+f(n)(n-1)-(n-1)[f(n)+n-1]=n^2-(n-1)^2=2n-1$ So $f(n)=n$
29.04.2022 15:45
https://artofproblemsolving.com/community/c6h1854148p12519631
08.08.2023 07:13
A slightly different approach using induction, Base Case.$\quad n=1,2$ Let $P(m,n)$ be the assertion, $P(1,1)$ gives us $$f(1)+1|f(1)^2+1 \Rightarrow f(1)+1|2$$Because $f:\mathbb{N}\rightarrow \mathbb{N}$, we must have $f(1)=1$. $P(1,2)$ and $P(2,2)$ gives us $$P(1,2) \Rightarrow 3|1+f(2)$$$$P(2,2) \Rightarrow f(2)+2|f(2)^2+4 \Rightarrow f(2)+2|8$$Therefore we must have $f(2)=2$, the base case is now completed. Induction Hypotesis.$\quad f(n)=n \quad \forall n\in\mathbb{N}$ is the only solution. Inductive Step.$\quad$ It suffices to prove that if $f(n)=n$ for some arbitrary $n\in\mathbb{N}$, then $f(n+1)=n+1$ is the only possible value. Assume $f(n)=n$ for some arbitrary $n\in\mathbb{N}$, $P(n,n+1)$ gives us $$f(n+1)+n|(n+1)^2+n\cdot f(n+1) \Rightarrow f(n+1)+n|2n+1 \Rightarrow f(n+1)\le n+1$$Furthermore, notice that $P(n+1,n)$ gives us $$2n+1|n^2 + n\cdot f(n+1) \Rightarrow 2n+1|2n^2+2n\cdot f(n+1) \Rightarrow 2n+1|2n\cdot f(n+1)-n$$Since $gcd(2n+1,n)=1$, therefore $$2n+1|2\cdot f(n+1)-1 \Rightarrow n+1\le f(n+1)$$$Q.E.D$
08.08.2023 09:00
Only answer is $\boxed {f(n)=n}$ Let $P(m,n)$ be the assertion of $f(n)+m | n^2 + f(n)f(m)$ $P(1,1) \rightarrow f(1)=1$ For primes $p$ $P(p,p) \rightarrow f(p) \in ({p,p^2-p,2p^2-p})$ From $P(m,1) \rightarrow m+1 | f(m) +1$ and $P(1,m) \rightarrow f(n)+1 | n^2-1$ from these two divisibility we see that $f(p)=p$ for all primes $p $ $P(p,n)$ we get $p+f(n)| f^2(n) - n^2$ so $f(n)=n$ for all $n\in N$ $\square$
01.12.2024 17:32
Put $m=n=1$ to get $f(1)=1$. Put $m=f(n)$ to get $f(n) | n^2$ which gives us that if $n$ is prime, then $f(n)=n$.[Easy to get a contradiction in the other two cases.] Put $n=p$ where $p$ is a "large" prime to get $m+p | p^2+pf(m)$ so $m+p | p+f(m) \implies m+p | f(m)-m$ but $f(m) \leq m^2$ so the divisibility can only hold for all large primes $p$ when $f(m)=m$ hence we are done.