oh, i think it is IMOSL-04 ANSWER: f(n)=n i think this pro is easy because very cleary to prove that f(p-1)=p-1 for all prime p @pipfly: why are you post this pro in here and who are you?

How to do it after getting $f(p-1)=p-1$ for all primes $p$?

pigfly, can you please clear up the notation for me: What is \mathbb{N}^*, is it the set of positive integers? And, what is f^2(n)? Is it a composition of f on f or it's (f(n))^2?

$\mathbb{N^{*}}$ is set of positive integers, $f^{2}(n)=(f(n))^{2}$.

Ok, let's solve it : We know that $f^2(1)+f(1)$ divides $4$ and is greater than $1$, so that it is $2$ or $4$. Solving the quadratic equations in $f(1)$ we easily find that $f(1)=1.$ It follows that for each prime $p$ the number $1+f(p-1)$ divides $p^2$ and is greater than $1$ so that it is $p$ or $p^2$. Suppose that for some prime $p$ we have $f(p-1)+1 = p^2.$ Then $p^4-2p^2+2 = (p^2-1)^2 + 1 = f^2(p-1)+f(1)$ divides $((p-1)^2+1)^2 = p^4-4p^3 + 8p^2 - 8p +4$. But it is easy to verify that for $p \geq 2$ we have $p^4-4p^3 + 8p^2 - 8p +4 <2(p^4-2p^2+2)$, from which we deduce that we must have $p^4-4p^3 + 8p^2 - 8p +4 = p^4 - 2p^2 + 2$, that is $2p^3-5p^2+4p-1=0$. Thus $p$ divides $1$ which is absurd. Then, for all prime $p$, we have $f(p-1)+1=p$ that is $f(p-1)=p-1.$ Now, for all positive integer $n$ and all prime $p$, we deduce that $f(n)+(p-1)^2$ divides $((p-1)^2+n)^2 = ((p-1)^2+f(n))((p-1)^2 + 2n - f(n)) + (f(n) - n)^2$. Thus $\frac {(f(n)-n)^2} {f(n) + (p-1)^2}$ is an integer. Note that this integer is clearly non-negative. Choosing $p$ sufficientely large, the corresponding integer is less than $1$, so that it is $0$. Thus $f(n) = n$. Conversely, $f(n)=n$ is clearly a solution of the problem. Pierre.

Yes,it is Number Theory 3 from the IMO Shortlisted 2004.The solution from the jury is as similar as Pierre'solution.Nice solution!Sorry for posting this problem here @nguyenquockhanh:Pigfly not pipfly,grrrr....You asked me:"who are you?" but I don't know exactly!Who am I?By the way,I am the friend of you

pigfly wrote: Yes,it is Number Theory 3 from the IMO Shortlisted 2004. Wow! I solved an IMO-SL one Quote: The solution from the jury is as similar as Pierre'solution. I could be part of it Pierre.

Hmm... Btw, where did you find the IMO-SL 2004? Pierre.

pbornsztein wrote: Hmm... Btw, where did you find the IMO-SL 2004? Pierre. I have known some problems from IMO-SL 2004(not all) but I think I don't post them here because: orl wrote: Some countries use them to select team members for the next IMO thus it should not get known before the team has to be announced to the IMO host. Otherwise it would be unfair to those students who did not know the problems in advance. When I posted this problem,I didn't know it from IMO-SL 2004.Sorry again for posting this problem here!

This problem I known since excercise of Dang Hung Thang and my solution above.

K09 wrote: This problem I known since excercise of Dang Hung Thang and my solution above. Really ?Maybe Mr Dang Hung Thang had the IMO-SL 2004( he was leader of VietNam team in IMO2004).I'm sure this problem from IMO-SL2004 . @K09:the HaiDuong team is very strong,isn't it?

pbornsztein wrote: pigfly wrote: Yes,it is Number Theory 3 from the IMO Shortlisted 2004. Wow! I solved an IMO-SL one Quote: The solution from the jury is as similar as Pierre'solution. I could be part of it Pierre. We are just waiting until you become the new France (deputy) IMO delegation leader finally. The time will come. You and Moubinool would form a cool team.

orl wrote: The time will come. Maybe, but not in this life Pierre.

pbornsztein wrote: orl wrote: The time will come. Maybe, but not in this life Pierre. I am sure it will be in this life.

orl wrote: pbornsztein wrote: orl wrote: The time will come. Maybe, but not in this life Pierre. I am sure it will be in this life. Me too Anyway it seems that no Romanian payed attention to this problem. It was used in our selection TSTs ...

Valentin Vornicu wrote: Me too Anyway it seems that no Romanian payed attention to this problem. It was used in our selection TSTs ... I think the German group benefits from ML. Darij, Peter etc. can confirm it.

Incidentally, a rewording of the problem was used as problem 1 in the 3rd independent study of the 3rd TST of Taiwan 2005. The problem we have is as follows: Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for all positive integers $m$ and $n$, $(f(m))^2 + f(n)$ divides $(m^2+n)$.

I don't see what the rewording is It's exactly the same problem ...

My mistake. I got a modified version of the shortlist...

Let $P(x,y)$ denote the given assertion. Claim: $f(p-1)=p-1$ for all primes $p.$ Proof. Note $P(1,1)$ yields $$(f(1)+1)f(1)=f(1)^2+f(1)\mid (1^2+1)^2=4$$so $f(1)=1.$ Also, $P(1,p-1)$ gives us $1+f(p-1)\mid p^2$ so $1+f(p-1)$ is equal to $p$ or $p^2.$ Suppose FTSOC the latter. Then, $P(p-1,1)$ yields $(p^2-1)^2+1\mid ((p-1)^2+1)^2.$ On the other hand, $$(p^2-1)^2+1>(p^2-1)^2>(p^2-2p+2)=((p-1)^2+1)^2,$$a contradiction. $\blacksquare$ From $P(p-1,n)$ we have $(p-1)^2+f(n)\mid ((p-1)^2+n)^2.$ Notice if $a\mid b^2,$ then $a\mid a^2-2ab+b^2=(a-b)^2.$ Thus, $$(p-1)^2+f(n)\mid ((p-1)^2+f(n)-(p-1)^2-n)^2=(f(n)-n)^2.$$Varying $p,$ we see $(f(n)-n)^2$ has an unlimited amount of divisors so $f(n)=n,$ which works. $\square$

Note that $f(1)=1,$ trivial. Lemma: $f(p-1)=p-1~\forall$ primes $p.$ Proof. We have that $1+f(p-1)\mid p^2.$ Thus $f(p-1)\in \{p-1,p^2-1\}.$ It is not hard to get a contradiction from the latter. $\blacksquare$ $m\mapsto p-1\implies f(n)+(p-1)^2\mid (n+(p-1)^2)^2 \implies f(n)+(p-1)^2\mid (n-f(n))^2.$ Now for large $n,$ the identity satisfies.

Solved with hints from megarnie Let $P(m,n)$ be the assertion. $P(1,1) \rightarrow f(1)^2+f(1) \mid 4 \rightarrow f(1) = 1$ Let $p$ be a prime number. $P(1,p-1) \rightarrow f(p-1)+1 \mid p^2 \rightarrow f(p-1)=p-1 \text{ or } f(p-1)=p^2$ Assume $f(p-1)=p^2-1$. $P(p-1, 1) \rightarrow \text{ contradiction }$, since $p \neq 1$ ($1$ isn't prime!). Thus, $f(p-1)=p-1$. $$P(n, p-1) \rightarrow (p-1)^2+f(n) \mid ((p-1)^2+n)^2 \rightarrow (p-1)^2+f(n) \mid (f(n)-n)^2,$$which implies the only solution is $f(n)=n$. $\blacksquare$

Let $P(m,n)$ denote the assertion. We have \begin{align*} (a)~~P(1,1)&: f(1)^2+f(1) \mid 4 \implies f(1)=1 \\ (b)~~P(m,1)&: f(m)^2+1\mid (m^2+1)^2\\ (c)~~P(1,m)&: 1+f(m) \mid (1+m)^2 \end{align*}Doing $m\to p-1$ for $(c)$ gives $1+f(p-1)\mid p^2$, so $f(p-1)$ is $p-1$ or $p^2-1$. If it is $p^2-1$, then putting in $b$ gives $p^4-2p^2+2\mid p^4-4p^3+8p^2-8p+4$, which implies that \[4p^3-10p^2+8p-2\mid p^4-4p^3+8p^2-8p+4.\]Note that $p\ge 2$. Let $f(p)=4p^3-10p^2+8p-2$, then $f'(p)=4(2p-1)(p-2)>0$. Since $f(2)=6$, $f(p)>0$ for all $p$. Let \[g(p)=(p^4-4p^3+8p^2-8p+4)-(4p^3-10p^2+8p-2)=p^4-8p^3+18p^2-16p+6\]then $g'(p)=4(p-1)^2(p-4)$. Since $g(5)=1$, $g(p)>0$ for all $p\ge 5$. It is easy to check that the divisibility does not hold for $p=2$ or $3$, so that is a contradiction. Thus, $f(p-1)=p-1$ for all primes $p$. In particular, there are infinitely many values of $n$ such that $f(n)=n$. Let $y$ be one such value. Note that $P(y,m)$ gives $y^2+m\mid (y^2+f(m))^2.$ We have $(y^2+f(m))^2\equiv (f(m)-m)^2\pmod y^2+m$, so picking large $y$ lets us conclude that $f(m)=m$. This function is our only solution, and it works because $m^2+n\mid (m^2+n)^2$.

It felt nice doing doing math after a long time, and especially struggling on a problem and still persisting and completing it is something i had not done in a while so this was really nice... I will write out all the claims that i found in the order i found them, even though i could shorten this solution by a lot, i don't see a reason to Let $P(m,n)$ denote the assertion that $f(m)^2+f(n) \mid (m^2+n)^2$

First plugging in $m = n = 1$ yields $$f(1)^2+f(1) \mid 4$$but since $f(1)$ is a positive integer we must have $f(1) = 1$. Now plug in $m=1$ to get $1+f(n) \mid (1+n)^2$ for all positive integers $n$. Plugging in $n = p-1$ here yields $1+f(p-1) \mid p^2$ which implies that $f(p)$ is either equal to $p-1$ or $p^2-1$. We now prove that we must actually have $f(p) = p-1$. Plug in $m = n = p-1$ for a prime $p$ to get $$f(p-1)(1+f(p-1)) \mid p^2(p-1)^2$$ If $f(p-1) = p^2-1$ then this means $$(p^2-1)p^2 \mid p^2(p-1)^2$$which implies $p^2-1 \mid (p-1)^2$ which implies $p^2-1 \mid 2-2p$ which is clearly false by size reasons. It follows that $f(p-1) = p-1$ as desired. Now, plug in $m = p-1$ to get $$(p-1)^2+f(n) \mid ((p-1)^2+n)^2$$which is equivalent to $$((p-1)^2+n)^2 \equiv 0 \pmod {(p-1)^2+f(n)}$$This is also equivalent to $$(n-f(n))^2 \equiv 0 \pmod {(p-1)^2+f(n)}$$and taking a large enough $p$ gives us $(n-f(n))^2 = 0$ or $f(n) = n$ for all positive integers $n$.

f(1)^2+f(1)|4 means f(1)=1 since the other values don't work; we're motivated to use primes p because dividing p^2 only gives three choices, so substitute (p-1,1) and (1,p-1) to get f(p-1)={p-1,p^2-1}, and f(p-1)^2+1|((p-1)^2+1)^2; the latter in the set doesn't work by plugging in (p^4-2p^2+2|p^4-4p^3+8p^2-8p+4, or p^4-2p^2+2|-4p^3+10p^2+2, contradiction for p\ne 2 since LHS>RHS\ne 0, and for p=2 we already know f(1)=1), so f(p-1)=p-1. The problem is now evident, because (p-1)^2+f(n)|((p-1)^2+n)^2\implies (p-1)^2+n|(n-f(n))^2; taking p large enough s.t. LHS>RHS, we must have RHS=0; in particular, n=f(n) for all n.

Denote the assertion with $P(m, n)$. Then by $P(1, 1)$ it follows that $f(1)^2 + f(1) \mid 4$, so $f(1) = 1$ must hold. Claim: $f(p-1) = p-1$ for primes $p$. Proof. By $P(1, p-1)$ it follows that \[ 1 + f(p-1) \mid p^2. \]so $f(p-1)$ is either $p-1$ or $p^2-1$. Then, by $P(p-1, 1)$ it follows that \[ f(p-1)^2 + 1 \mid ((p-1)^2 + 1)^2 \]which implies $f(p-1) = p-1$. $\blacksquare$ By taking a sufficiently large prime $p$, it follows by $P(p-1, n)$ that \[ (p-1)^2 + f(n) \mid ((p-1)^2 + n)^2 \]This simplifies as \[ (p-1)^2 + f(n) \mid (n - f(n))^2 \]which forces $n = f(n)$.

The idea is to just get $f(n)$ for $n=p-1$ for sufficiently large $p$. This is doable because $f(1)^2+f(1) \mid 4$, hence $f(1) = 1$, so in particular $$f(p-1) + 1 = f(1)^2 + f(p-1) \mid p^2.$$This narrows down $f(p-1) \in \{p-1, p^2-1\}$, and furthermore $$f(p-1)^2 + 1 \mid (p^2-2p+2)^2$$ensures $f(p-1) = p-1$. Now just writing $$f(n) + (p-1)^2 \mid (n+(p-1)^2)^2$$for fixed $n$ and sufficiently large $p$ forces $f(n) = n$.

Claim 1 : $f(1) =1$. proof: $P(1,1) \implies f(1)(f(1)+1) | 4$ $ \blacksquare$ Claim 2: $p$ is prime $\implies f(p-1)= p-1$ . proof: $P( 1,p-1) \implies 1+f(p-1) | p^2 $ $P(p-1,p-1) \implies f(p-1)(f(p-1)+1) | (p-1)^2 p^2 $. $ \blacksquare$ Claim 3 : $f(n)=n$ . proof: Let $p$ big enough. $P(p-1,n) \implies (p-1)^2 +1 | (f(n)-n)(2(p-1)^2 +f(n)+n) \implies (p-1)^2 +1 | (f(n)-n)^2$ $ \blacksquare$

The only function is $f(n) = n$ for all $n \in \mathbb{N^{*}},$ which works. We will now show it is the only solution. Let $P(m, n)$ denote the given assertion. From $P(1, 1)$ we have $f(1)^2 + f(1) \mid 4$, so $f(1) = 1$ since $f(1) \in \mathbb{N^{*}}$. Now, we will show that for all primes $p$, $f(p - 1) = p - 1$. From $P(1, p - 1)$, we get $$1 + f(p - 1) \mid p^2,$$so $f(p - 1) \in \{p - 1, p^2 - 1\}$. But from $P(p - 1, p - 1),$ we have $$f(p - 1)^2 + 1 \mid ((p - 1)^2 + 1)^2,$$which is impossible if $f(p - 1) = p^2 - 1$ since $(p^2 - 1)^2 > (p^2 - 2p + 2)^2 = ((p - 1)^2 + 1)^2.$ So, we can now fix $n \in N$ and take $P(p - 1, n)$ for some prime $p$, which gives $$(p - 1)^2 + f(n) \mid ((p - 1)^2 + n)^2.$$Since $((p - 1)^2 + n)^2 - (n - f(n))^2 = ((p - 1)^2 + 2n - f(n))((p - 1)^2 + f(n)),$ this implies that $(p - 1)^2 + f(n) \mid (n - f(n))^2.$ Taking $p$ large enough, we get $f(n) = n$, as desired.

Pretty clearly, $f(x) = x$, and we'd like to prove this is the only such function. We'll start with some basic substitutions. $P(1, 1)$ gives $f(1)^2 + f(1) \mid 4 \implies f(1) = 1$. To narrow down the function, we can substitute in something related to primes, which we can do by $P(1, p - 1)$, which gives: $$1 + f(p - 1) \mid p^2 \implies f(p - 1) = p - 1, p^2 - 1$$since the only divisors of $p^2$ are $1, p, p^2$ and $f(p - 1) > 0$. Say, for the sake of contradiction, $f(p - 1) = p^2 - 1$. $P(p - 1, p - 1)$ gives: $$(p^2 - 1)^2 + p^2 - 1 \mid p^2(p - 3)^2$$$$\implies p^2(p^2 - 1) \mid p^2(p - 3)^2$$$$\implies p^2 - 1 \mid p^2 - 6p + 9$$which is impossible as $p^2 - 1 > p^2 - 6p + 9$. So, we must have $f(p - 1) = p - 1$. To prove $f(n) = n$ for all $n$, we can substitute $P(n, p - 1)$. $$f(n)^2 + f(p - 1) \mid (n^2 + (p - 1))^2 = n^4 + 2n^2(p - 1) + (p - 1)^2$$$$\implies f(n)^2 + p - 1 \mid n^4 + 2n^2(p - 1) + (p - 1)^2 - 2n^2(f(n)^2 + p - 1)$$$$\implies f(n)^2 + (p - 1) \mid n^4 - 2n^2f(n)^2 + (p - 1)^2$$This also means$f(n)^2 + (p - 1) \mid n^4 - 2n^2f(n)^2 + (p - 1)^2 - (p - 1)(f(n)^2 + (p - 1))$. $$\implies f(n)^2 + (p - 1) \mid n^4 - 2n^2f(n)^2 - (p - 1)f(n)^2$$This implies $f(n)^2 + (p - 1) \mid n^4 - 2n^2 f(n)^2 - (p - 1)f(n)^2 + f(n)^2(f(n)^2 + (p - 1)) = n^2 - 2n^2f(n)^2 + f(n)^4 = (n^2 - f(n))^2$ For sufficiently large $p$, we must have $(n^2 - f(n))^2 = 0 \implies f(n) = n$. credits to my blog

storage

We have $f(1)^2+f(1)\mid 4$ which forces $f(1)=1$. Suppose we have shown $f(k)=k$ for all $k<a$. Taking $(a,b)$ to be $(a,a-1)$ and $(a,a-2)$ we get $$f(a)^2+a-1 \mid (a^2-f(a)^2)^2, \quad f(a)^2+a-2 \mid (a^2-f(a)^2)^2.$$Since $\gcd(f(a)^2+a-1, f(a)^2+a-2)=1$, it follows that $$(f(a)^2+a-1)(f(a)^2+a-2) \mid (a^2-f(a)^2)^2 \implies f(a) \leq a.$$Taking $(a,b)=(a-1,a)$ we get $$f(a)+(a-1)^2\mid ((a-1)^2+a)^2 \implies f(a)+(a-1)^2 \mid (a-f(a))^2$$which implies $f(a)=a$ since $f(a)+(a-1)^2>(a-1)^2\geq (a-f(a))^2$ (as $f(a)\leq a$). By induction, $f(x)=x$ for all $x$, which works.