canada wrote: Find all functions $g:\mathbb{N}\rightarrow\mathbb{N}$ such that \[ \left(g(m)+n\right)\left(g(n)+m\right)\] is perfect square for all $m,n\in\mathbb{N}.$ Canada,thank you for posting $IMO-2010$ problems.here is my solution,I am not sure( hope it will be correct). First let $g(m)=m+k_1$$,g(n)=k_2+n$ where $k_1,k_2$ depends on $g(m),g(n)$ respectively.As $(g(m)+n)(g(n)+m)$ is a perfect square,we can let this equal to $(m+n+c)^2$ for some $c.$Now collecting terms and equating coefficients we get $k_1=k_2=c$ implies $k_1,k_2$ does not depend on $g(m),g(n)$ or we can choose a constant $k$.Then $g(x)=x+k$ for all integer $x$ and all constant $k$

mathmdmb wrote: canada wrote: Find all functions $g:\mathbb{N}\rightarrow\mathbb{N}$ such that \[ \left(g(m)+n\right)\left(g(n)+m\right)\] is perfect square for all $m,n\in\mathbb{N}.$ Canada,thank you for posting $IMO-2010$ problems.here is my solution,I am not sure( hope it will be correct). First let $g(m)=m+k_1$$,g(n)=k_2+n$ where $k_1,k_2$ depends on $g(m),g(n)$ respectively.As $(g(m)+n)(g(n)+m)$ is a perfect square,we can let this equal to $(m+n+c)^2$ for some $c.$Now collecting terms and equating coefficients we get $k_1=k_2=c$ implies $k_1,k_2$ does not depend on $g(m),g(n)$ or we can choose a constant $k$.Then $g(x)=x+k$ for all integer $x$ and all constant $k$ I think this is wrong. $c$ maybe independent of $m$ and $n$, and maybe not.

but so what,we choose $k$ constant

What wangsacl means is that, for example, when $m=1$ and $n=2$, we could have $k_1=3$, $k_2=22$, $c=7$ so $g(1)=1+1=2$ and $g(2)=2+22=24$ so \[(g(1)+2)(g(2)+1)=(4)(25)=10^2=(1+2+7)^2=(m+n+c)^2.\]

It seems to be surprisingly simple for problem 3. Lemma 1. $g(n)\ne g(n+1)$, $g(n)\ne g(n+2)$. Proof. Obvious, assume the contrary and substitute $n$, $n+1$ or $n$, $n+2$. Lemma 2. $|g(n)-g(n+1)|\leq 1$. Again, assume the contrary, then numbers $g(n)$ and $g(n+1)$ have equal residue modulo some prime $p$, but are not equal. Take $m$ such that $m+g(n)$ and $m+g(n+1)$ are both divisible by $p$, but order of $p$ in their factorization is odd. It is always possible: if $g(n)-g(n+1)=p^rq$ with odd $r$ and $q$, not divisible by $p$, then take $m+g(n)$ equal to large odd power of $p$. If $r$ is even, then $r\geq 2$ and take $m+g(n)$ equal to (large power of $p$ plus $p$). Next, one of numbers $g(m)+n$ and $g(m)+n+1$ is not divisible by $p$, and corresponding product will not be a perfect square. From lemmas 1,2 it follows that $g(n+1)=g(n)\pm 1$ and that the sign is always the same. So, $g(n)=\pm n+%Error. "const" is a bad command. $, clealy only sign $+$ is ok.

@all posts other than the one above me: Just because (a+b+r)(a+b+s) is a square doesn't imply that r=s. Take a+b=3 (if you really care which is which, a=2, b=1, say, but it doesn't matter.), r=1, s=35. You used k1 and k2 instead, but your mathematical logic is faulty. Also, an IMO 3 is not that easy.

yugrey wrote: @all posts other than the one above me: Just because (a+b+r)(a+b+s) is a square doesn't imply that r=s. Take a+b=3 (if you really care which is which, a=2, b=1, say, but it doesn't matter.), r=1, s=35. You used k1 and k2 instead, but your mathematical logic is faulty. Also, an IMO 3 is not that easy. But what if (a+b+r)(a+b+s) is a square no matter what a and b are? Also, this problem is rather trivial for a problem 3 (though it's still probably harder than last year's number 3). The following two lemmas kill the problem: 1. If an odd prime p divides g(a)-g(b), then p divides a-b. Proof: Since p >= 3, it is clear that we can choose a positive integer n such that the p-adic valuation of n+g(a) and n+g(b) is 1. Plug in m = a, n = what we just chose it to be, then we get (g(a)+n)(a+g(n)) is a perfect square. p divides g(a)+n, so p^2 divides (g(a)+n)(a+g(n)), and p^2 doesn't divide g(a)+n, so p divides a+g(n). Similarly, p divides b+g(n), so it divides their difference, which is a-b. 2. If 4 divides g(a)-g(b), then 2 divides a-b. Proof: There exists a positive integer n such that 2 divides n+g(a), but 4 doesn't, and now we just proceed as in Lemma 1. Now, the first lemma implies that the absolute value of g(a+1)-g(a) is a power of 2. The second lemma implies that g(a+1)-g(a) is -2, -1,1, or 2. After a bit of casework, we get that g(a+1)-g(a) is always 1, so g(x) = x+c for some c, and this indeed works.

I don't think that is a perferct solution pythag...

northofnorth01 wrote: I don't think that is a perferct solution pythag... What's wrong with it?

: Why we all assume that g(x)=ax+b??? Why can't it be ax^2+bx+c or else??? Hehehe...

How about finding all functions $g$ from $\mathbb{N}$ to $\mathbb{N}$ such that $(g(a)+b+c)(a+g(b)+c)(a+b+g(c))$ is a perfect cube for all positive integers $a,b,c$? Or even, more generally, find all functions $g$ from $\mathbb{N}$ to $\mathbb{N}$ such that $(g(a_1)+a_2+\cdots +a_n)(a_1+g(a_2)+\cdots+a_n)(a_1+a_2+\cdots +g(a_n))$ is a $n$-th power for all positive integers $a_1,a_2,\dots,a_n$? Sincerely, Achilleas

Achilleas Sinefakopoulos wrote: How about finding all functions $g$ from $\mathbb{N}$ to $\mathbb{N}$ such that $(g(a)+b+c)(a+g(b)+c)(a+b+g(c))$ is a perfect cube for all positive integers $a,b,c$? Or even, more generally, find all functions $g$ from $\mathbb{N}$ to $\mathbb{N}$ such that $(g(a_1)+a_2+\cdots +a_n)(a_1+g(a_2)+\cdots+a_n)(a_1+a_2+\cdots +g(a_n))$ is a $n$-th power for all positive integers $a_1,a_2,\dots,a_n$? Sincerely, Achilleas Your problem is even much more difficult. Cuz' $(g(n))$has a lot of forms...

pythag011 wrote: yugrey wrote: @all posts other than the one above me: Just because (a+b+r)(a+b+s) is a square doesn't imply that r=s. Take a+b=3 (if you really care which is which, a=2, b=1, say, but it doesn't matter.), r=1, s=35. You used k1 and k2 instead, but your mathematical logic is faulty. Also, an IMO 3 is not that easy. But what if (a+b+r)(a+b+s) is a square no matter what a and b are? Also, this problem is rather trivial for a problem 3 (though it's still probably harder than last year's number 3). The following two lemmas kill the problem: 1. If an odd prime p divides g(a)-g(b), then p divides a-b. Proof: Since p >= 3, it is clear that we can choose a positive integer n such that the p-adic valuation of n+g(a) and n+g(b) is 1. Plug in m = a, n = what we just chose it to be, then we get (g(a)+n)(a+g(n)) is a perfect square. p divides g(a)+n, so p^2 divides (g(a)+n)(a+g(n)), and p^2 doesn't divide g(a)+n, so p divides a+g(n). Similarly, p divides b+g(n), so it divides their difference, which is a-b. 2. If 4 divides g(a)-g(b), then 2 divides a-b. Proof: There exists a positive integer n such that 2 divides n+g(a), but 4 doesn't, and now we just proceed as in Lemma 1. Now, the first lemma implies that the absolute value of g(a+1)-g(a) is a power of 2. The second lemma implies that g(a+1)-g(a) is -2, -1,1, or 2. After a bit of casework, we get that g(a+1)-g(a) is always 1, so g(x) = x+c for some c, and this indeed works. pythag011 wrote: northofnorth01 wrote: I don't think that is a perferct solution pythag... What's wrong with it? g(x) may not be a polynomial so you can't get "If an odd prime p divides g(a)-g(b), then p divides a-b."

Fedor Petrov wrote: It seems to be surprisingly simple for problem 3. ................................................ Take $m$ such that $m+g(n)$ and $m+g(n+1)$ are both divisible by $p$, but order of $p$ in their factorization is odd. It is always possible: if $g(n)-g(n+1)=p^rq$ with odd $r$ and $q$, not divisible by $p$, then take $m+g(n)$ equal to large odd power of $p$. If $r$ is even, then $r\geq 2$ and take $m+g(n)$ equal to (large power of $p$ plus $p$). ................................................. Can you explain this part clearer? I'm a little confused.

Well,li tong yang I think this part is not quite clear. In my opinion,(s)he is wrong...

Denote $C=g(n)-g(n+1)$. Then $m+g(n)$ and $m+g(n+1)$ may be arbitrary (sufficiently large) numbers with difference $C$. If $C$ is divisible by $p^2$, then take $m+g(n)=p+p^N$ for large $N$, then both $m+g(n)$ and $m+g(n+1)$ are equal to $p$ modulo $p^2$. If $C$ is divisible by $p$, but not by $p^2$, take $m+g(n)=p^N$ for large odd $N$, then $m+g(n+1)$ is divisible by $p$, but not by $p^2$.

Fedor Petrov wrote: It seems to be surprisingly simple for problem 3. Lemma 1. $g(n)\ne g(n+1)$, $g(n)\ne g(n+2)$. Proof. Obvious, assume the contrary and substitute $n$, $n+1$ or $n$, $n+2$. Lemma 2. $|g(n)-g(n+1)|\leq 1$. Again, assume the contrary, then numbers $g(n)$ and $g(n+1)$ have equal residue modulo some prime $p$, but are not equal. Take $m$ such that $m+g(n)$ and $m+g(n+1)$ are both divisible by $p$, but order of $p$ in their factorization is odd. It is always possible: if $g(n)-g(n+1)=p^rq$ with odd $r$ and $q$, not divisible by $p$, then take $m+g(n)$ equal to large odd power of $p$. If $r$ is even, then $r\geq 2$ and take $m+g(n)$ equal to (large power of $p$ plus $p$). Next, one of numbers $g(m)+n$ and $g(m)+n+1$ is not divisible by $p$, and corresponding product will not be a perfect square. From lemmas 1,2 it follows that $g(n+1)=g(n)\pm 1$ and that the sign is always the same. So, $g(n)=\pm n+%Error. "const" is a bad command. $, clealy only sign $+$ is ok. Dear Feder:Do you want to say $g(n)=+n$,I could not understand. math154 wrote: What wangsacl means is that, for example, when $m=1$ and $n=2$, we could have $k_1=3$, $k_2=22$, $c=7$ so $g(1)=1+1=2$ and $g(2)=2+22=24$ so \[(g(1)+2)(g(2)+1)=(4)(25)=10^2=(1+2+7)^2=(m+n+c)^2.\] math154:If $m=1,k_1=3$ then according to my assumption,$g(m)=1+3=4$,not $1+1=2$

Sorry, I mean $g(n)=\pm n\pm$ const.

If $p$ is a prime, $p^\alpha || b$ means that $p^\alpha|b$ but $p^{\alpha+1}$ doesn't. Let $p$ be an odd prime such that $p|g(m)-g(n)$. It is not hard to see that there exists $k$ such that $p||g(m)+k$ and $p||g(n)+k$. Now, as $\left(g(k)+n\right)\left(g(n)+k\right)$ is a perfect square, we have $p|g(k) + n$. Similarly, $p|g(k)+m$, thus $p|n-m$. Now, suppose $2|g(m)-g(n)$. There are two cases: If $4|g(m)-g(n)$ we can pick $k$ such that $2||g(m)+k$ and $2||g(n)+k$. As before, that implies $2|g(k)+n$ and $2|g(k)+m$ thus $2|n-m$ If $2 ||g(m)-g(n)$, pick $k$ such that $2^3||g(m)+k$. It follows that $2||g(n)+k$, and then $2$ must divide $g(k)+n$ and $g(k)+m$. Then for any prime $p$, if $p|g(n)-g(m)$, then $p|n-m$. In particular, $|g(n+1)-g(n)| = 1$ for all $n$. But if, for some $n$, $g(n+1)-g(n) = -1$, as the function is positive, there must be a $N$ such that $g(N+1)-g(n) = -1$ and $g(N+2)-g(N+1) = 1$, thus $g(N+2) -g(N) = 0$, and in particular, divisible by all primes, absurd. Then for all $n$, we must have $g(n+1) - g(n) = 1$, and that gives $g(n) = n+C$, with constant $C>=0$.

The answer is $g(n)=n+c$ for some $c\in\mathbb N$, which obviously works. Now we show that they are the only ones. Lemma. Let $p$ be a prime. Suppose $x\equiv y\pmod p$ then there exists $k\in\mathbb N$. Such that $v_p(x+k)\equiv v_p(y+k)\equiv 1\pmod 2$. Proof. WLOG assume $x\equiv y\equiv 0\pmod p$. This is just simple case work. WLOG assume $v_p(x)\leq v_p(y)$ CASE I:$v_p(x)\geq 2$. If we take $k=p$ then $v_p(x+k)=v_p(y+k)=1$. CASE II: $v_p(x)=1$ 1. If $v_p(y)\geq 4$ we can take $k=p^3$, then $v_p(a+k)=1$ while $v_p(b+k)=3$. 2. If $v_p(y)=3$ we can take $k=p^5$. Then $v_p(a+k)=1$ while $v_p(b+k)=3$. 3. If $v_p(y)=2$ we can take $k=cp^3-y$, where $c$ is a sufficently large integer such that $k>0$ and $(c,p)=1$. Then we have $v_p(b+k)=3$ while $v_p(a+k)=1$. 4. If $v_p(y)=1$ we can take $k=p^3$ then $v_p(a+k)=v_p(b+k)=1$. $\blacksquare$ Corollary 1. For all prime $p$,if $p|g(m_1)-g(m_2)$ then $p|m_1-m_2$ Proof. Suppose $p|g(m_1)-g(m_2)$. Then from the lemma there exists an integer $k$ such that $v_p((g(m_1)+k))$ and $v_p(g(m_2)+k)$ are both odd. From the condition, $$(g(m_1)+k)(g(k)+m_1)$$and $$(g(m_2)+k)(g(k)+m_2)$$are both prefect squares, therefore we $v_p(g(k)+m_1)$ and $v_p(g(k)+m_2)$ are both odd, in particular we have $p|g(k)+m_1$ and $p|g(k)+m_2$. Hence $m_1\equiv-g(k)\equiv m_2\pmod p$. $\blacksquare$ Corollary 2. For integers $n$, $f(n+1)-f(n)=1$. Proof. From corollary 1 we have that if $p$ is a prime factor of $f(n+1)-f(n)$ then $p|1$ which is impossible. Hence $f(n+1)-f(n)$ is either $1$ or $-1$. Suppose on the contrary that $f(n+1)-f(n)=-1$. Then from the condition $$(g(n)+n+1)(g(n+1)+n)=(g(n)+n+1)(g(n)+n-1)=(g(n)+n)^2-1$$is a perfect square. Hence $g(n)+n=1$, which is clearly impossible. Hence $f(n+1)-f(n)=1$. Now we can easily shows that $f(n)=n+f(1)-1$ by induction, this completes the proof.

1000th Post Yayyy

IMO 2010 P3 wrote: Find all functions $g:\mathbb{N}\rightarrow\mathbb{N}$ such that \[\left(g(m)+n\right)\left(g(n)+m\right)\]is a perfect square for all $m,n\in\mathbb{N}.$ Proposed by Gabriel Carroll, USA We start with a Lemma: Lemma: Let $A,B$ be positive integers such that $|A-B| \geq 2$. Then there exists a prime $p$ and $k \in \mathbb{N}$ such that $v_p(A+k)=v_p(B+k)=1$. Proof: Since $|A-B| \geq 2$ there exists a prime $p$ such that $p \mid |A-B|$. Let $A-B=p\ell$, with $\ell \in \mathbb{Z}$. Take a large enough $m \in \mathbb{N}$ such that $m \not\equiv \ell \pmod p$ and $m \not\equiv 0 \pmod p$, and let $k=pm-A$. We claim that these $p$ and $k$ work. Indeed, $v_p(A+k)=v_p(pm)=1$ and $v_p(B+k)=v_p(pm-p\ell)=v_p(p(m-\ell))=1$ $\blacksquare$. To the problem, suppose there existed an $s$ such that $|f(s+1)-f(s)| \geq 2$. By the Lemma above, we can pick a prime $p$ and a positive integer $k$ such that $v_p(f(s)+k)=v_p(f(s+1)+k)=1$. By the problem's condition though, we have that $$(f(s+1)+k)(f(k)+s+1)$$and $$(f(s)+k)(f(k)+s)$$are perfect squares. Since $\gcd (f(k)+s,f(k)+s+1)=1$, at least one of the two is not divisible by $p$. Suppose that $p \nmid f(k)+s$. Then, $v_p((f(s)+k)(f(k)+s))=1$, contradiction. Therefore, $|f(x+1)-f(x)| \in \{0, 1 \}$ for all $x$. If for some $x$, $f(x+1)=f(x)$, then $$(f(x)+x+1)(f(x+1)+x)=(T+1)T$$is a perfect square (with $T=f(x)+x$), which is a clear contradiction since $T \geq 2$. In addition, if for some $x$ $f(x+1)=f(x)-1$, we similarly have that $$(f(x)+x+1)(f(x+1)+x)=T^2-1$$is a perfect square (with $T=f(x)+x$), which is a clear contradiction again. To end, we conclude that $f(x+1)=f(x)+1$ for all $x$, hence $f(x)=x+c$ with $c \in \mathbb{Z}_{\geq 0}$, which clearly satisfies.

The answer is $g(x)=x+C$ for any integer $C\ge 0$, which clearly works. Suppose $g$ works. We have the following killer claim. Claim: If a prime $p\mid g(a)-g(b)$, then $p\mid a-b$. Proof: Suppose for now that $p\ge 3$. Note here that \[A-A=\mathbb{Z}/p\mathbb{Z}\]where $\{1,2,\ldots,p-1\}=A\subseteq\mathbb{Z}/p\mathbb{Z}$, so there are some $1\le u,v\le p-1$ such that \[g(a)-g(b)\equiv (u-v)p\pmod{p^2}.\]Pick \[n\equiv up-g(a)\equiv vp-g(b)\pmod{p^2}.\]Now, $n+g(a)$ is divisible by $p$ but not by $p^2$, so since \[(n+g(a))(a+g(n))\]is a square, we must have $g(n)\equiv -a\pmod{p}$. We similarly derive $g(n)\equiv -b\pmod{p}$, so $p\mid a-b$, as desired. Now suppose $p=2$. If $g(a)\equiv g(b)\pmod{4}$, then we may select $u=v=1$ and proceed similarly as above. So suppose now that \[g(a)\equiv g(b)+2\pmod{4}.\]Select \[n\equiv 8-g(a)\pmod{16},\]so $v_2(g(a)+n)=3$ and $g(b)+b\equiv 2\pmod{4}$, so $v_2(g(b)+n)=1$. These $v_2$ values are both odd, so we may proceed similarly as above to derive $2\mid a-b$, as desired. $\blacksquare$ The claim implies that $g$ is injective, since if $g(a)=g(b)$, then $p\mid a-b$ for all primes $p$, so $a=b$. It further implies that \[g(n+1)\in\{g(n)+1,g(n)-1\}\]for all $n$, and by injectivity, implies that the same sign must be chosen for each $n$. Since $g(n)$ is always positive, the positive sign must be chosen for all $n$, so $g(n)=n+g(1)-1$ for all $n$, as desired.

Solved with Daniel Yuan, Jeffrey Chen We claim $g$ must be of the form $g(x)=x+c$ for $c\geq 0$. Such $g$ clearly work because the expression becomes $(m+n+c)^2$. $\textbf{Claim: }$ $g(n)$ is injective $\textbf{Proof: }$ Let $g(a)=g(b)=k$. Then, consider some prime $p>k$ such that $p\nmid a-b$. Then, take $n=p-k$ \[(n+k)(g(n)+a)\text{ and } (n+k)(g(n)+b)\]are both squares, so $p$ divides both $g(n)+a,g(n)+b$, a contradiction.$\square$ $\textbf{Claim: }$ If $g(a)\equiv g(b)\pmod{p}$, there always exists some positive integer $n$ such that $v_p(g(a)+n)\equiv v_p(g(b)+n)\equiv 1 \pmod{2}$ $\textbf{Proof: }$. For $p\geq 3$, there clearly exists some $n\equiv -g(a)\pmod{p}$ but $n\not\equiv -g(a),-g(b)\pmod{p^2}$. Which gives $v_p$ equal to 1 for both. For $p=2$. Issues only arise to break $p\geq 3$ logic when $g(a)\equiv 1, g(b)\equiv 3 \pmod{4}$. In this case, just take $n$ such that $n=2^{2k+1} - g(b)$ where $k > \max(10,\log_2(b))$. Thus, $v_2(g(b)+n)=2k+1$ and $v_2(g(a)+n) = v_2(g(b)+n + (g(a)-g(b))) = 1$.$\square$ $\textbf{Claim: }$ $g(a)\equiv g(b)\pmod{p}\Longrightarrow a\equiv b \pmod{p}$ $\textbf{Proof: }$. Consider $n$ such that $v_p(g(a)+n)\equiv v_p(g(b)+n)\equiv 1 \pmod{2}$. Thus, we have $p\mid g(n)+a,g(n)+b$, so \[a\equiv -g(n)\equiv b \pmod{p}\]$\square$. $\textbf{Claim: }$ $a\equiv b\pmod{p}\Longrightarrow g(a)\equiv g(b) \pmod{p}$ $\textbf{Proof: }$ The set of residues mod $p$ is the same for both $g(x)$ and $x$. Since $g(x)$ get sent to different values, and the sizes are the same, this is a bijection so the claim is clear. $\square$. Combining the previous two claims, we clearly have that $g(a)-g(b)$ have the same set of prime divisors as $a-b$. Then, by taking $a=b+1$, we have that $g(b+1)-g(b)=\pm 1$. Since $g$ is injective we cannot have two adjacent differences being $\{1,-1\}$. Thus, the differences must be constant. They also cannot all be -1 because $g\to \mathbb{N}$. Thus, all adjacent differences must be 1, so $g$ must be of the form $g(x)=x+c$ for $c\geq 0$ and we're done. $\blacksquare$.

First we assume that there is some $n\in\mathbb{N}$ for which there exists a prime $p,$ such that $p\mid g(n+1)-g(n).$ Select $m=kp-g(n)$ for some large $k$ to be determined later and write $$(g(m)+n)(kp)=x^2$$$$(g(m)+n+1)(g(n+1)-g(n)+kp)=y^2$$If $p^2\mid g(n+1)-g(n),$ then let $k$ be such that $p\nmid k$ and note that $$v_p(kp)=1=v_p(g(n+1)-g(n)+kp)$$and since $p\mid x^2, y^2,$ it must be also true that $p\mid g(m)+n, g(m)+n+1,$ a clear contradiction$.$ Now if $p\parallel g(n+1)-g(n),$ select $k=tp^2,$ where $t$ is such that $p\nmid t$ and $m=tp^3-g(n)>0,$ and note that $$v_p(kp)=3, v_p(g(n+1)-g(n)+kp)=1$$and we again have $p\mid g(m)+n, g(m)+n+1,$ which is impossible$.$ Therefore $\left| g(n+1)-g(n)\right|=1$ for all $n\in\mathbb{N}. \hspace{0.3cm}(*)$ Now assume that for some $n$ we have $g(n+2)=g(n).$ Choose $m=p-g(n)=p-g(n+2)$ for a large prime $p$ and write $$(g(m)+n)(p)=x^2$$$$(g(m)+n+2)(p)=y^2$$We again see that $p\mid g(m)+n, g(m)+n+2,$ a contradiction$.$ Therefore $g(n+2)\neq g(n)$ for all $n\in\mathbb{N}. \hspace{0.3cm} (\square)$ Finally$,$ $(*)$ and $(\square)$ are enough to conclude that $g(n)=n+c$ for all $n\in\mathbb{N},$ where $c\in\mathbb{N}_0$ is some constant$.$ This function clearly satisfies the condition of the problem and we are done$.$

The answer is $\boxed{g(m)=m+c}$ for any nonnegative integer constant $c$. These clearly work. We will show they are the only solutions. Claim: $g(m)\ne g(m+1)$ and $g(m)\ne g(m+2)$. Proof: If $g(m)=g(m+1)$, then $(g(m)+m+1)(g(m)+m)$ is a perfect square, a contradiction. If $g(m)=g(m+2)$, then $(g(m)+m+2)(g(m)+m)$ is a perfect square, a contradiction. $\blacksquare$ Claim: $|g(m+1)-g(m)|=1$. Proof: Suppose not, and there exists a prime $p$ with $g(m)\equiv g(m+1)\pmod p$. If we find $n$ such that $\nu_p(g(m)+n)$ and $\nu_p(g(m+1)+n)$ are both odd, then we need $p\mid g(n)+m$ and $p\mid g(n)+m+1$, a contradiction. It suffices to find such $n$. Let $a=\nu_p(|g(m+1)-g(n)|)$. If $a$ is odd, set $n=p^k-g(m)$ for odd insanely large $k$. Then \[\nu_p(g(m)+n)=\nu_p(p^k)=k\]and \[\nu_p(g(m+1)+n)=\nu_p(g(m+1)-g(n)+p^k)=a\] Note that both $k$ and $a$ are odd. If $a$ is even, then set $n=p^k+p-g(m)$ for insanely large $k$. Then \[\nu_p(g(m)+n)=\nu_p(p^k+p)=1\]and \[\nu_p(g(m+1)+n)=\nu_p(p^k+p+g(m+1)-g(n))=1,\]since $a>2$. $\blacksquare$ Note that if $g(m+1)=g(m)-1$ for some $m$, then since $g(m+1)\ne g(m-1)$, $g(m-1)=g(m)+1$, so $g(m)=g(m-1)+1$. Now we can get $g(m-2)=g(m-1)+1$, and so on until $g(1)=g(2)+1$. Now we can also go upwards, and get $g(m+2)=g(m+1)-1$. So $g(m+3)=g(m+2)-1$, and so on. We can continue until $g(x)<1$ for some positive integer $x$, a contradiction. Henceforth assume $g(m+1)\ne g(m)-1$ for any $m$. Then $g(m+1)=g(m)+1$ for all $m$. So $g(m)=m+g(1)-1$, which implies the desired result. $\blacksquare$

Basically this problem is completely number theory, also imo p3. Let's Proceed: Claim 1: $g(a) \neq g(a+1).$ Assume the contrary. Then $(g(a+1)+a)(g(a)+a+1)$ is a perfect square. But notice that $$ (g(a)+a)^2<(g(a+1)+a) (g(a)+a+1) <(g(a)+a+1)^2,$$a contradiction. Claim 2: $|g(b+1)-g(b)|=1.$ Let $p$ be a prime such that $g(b+1)\equiv g(n) \pmod{p}.$ We can easily find that such a $p$ exists. Set $|g(b)-g(b+1)| =p^rq: p$ ⫮ $q.$ Case 1: $r=1.$ $$\text{Setting }g(a)+c=p^3 \implies g(a+1)+c=p^3\pm pq =p(s),$$where $p$ ⫮ $s.$ Case 2: $r>1.$ $$\text{Setting }g(a)+c=p \implies g(a+1)+c=p\pm p^rq=p(s),$$where $p$ ⫮ $s.$ Therefore either $p$ ⫮ $g(a)+c$ or $p$ ⫮ $g(a)+c+1.$ It follows that $(g(a+1)+b)(g(b)+a+1)$ and/or $(g(a)+b)(g(b)+a)$ is divisible by an odd power of $p.$ So that number is not a perfect square. We have $g(m)-g(m+1)=1 \implies g(x)=c-x,$ and $g(m)-g(m+1)=-1 \implies g(x)= x+c,$ where $c$ is any natural number. We can easily check that $\boxed{g(x)=x+c},$ is a working solution. Note: If anybody finds any flaw in this, kindly let me know by PM.

Looking at above posts, I have realised I overcomplicated this a lot lol. I could have proceeded as in pythag's solution and saved all of that calculation.

Despite the short and simple-looking solution, this problem is not straightforward at all. The answer is $g(n) = n+c$. The main claim is the following: Claim. If $g(a) \equiv g(b) \pmod p$ for any prime $p$, then $a \equiv b \pmod p$. Proof. Take some integer $k$ such that $\nu_p(g(a) + k)$ and $\nu_p(g(b) + k)$ are both odd. (This is possible by taking $r = \nu_p(g(a) - g(b))$ then setting $k = Np-g(a)$ where $N$ is large) Then, it follows that $p \mid g(k) + a$ and $p \mid g(k) + b$ by the condition, or $a \equiv b \pmod p$. $\blacksquare$ Hence no primes divide $g(n+1) - g(n)$ and it follows that $|g(n+1) - g(n)| = 1$. On the other hand, the possibility $g(k) = g(k+2) = r$ is impossible because $(r+k)(r+k+2)$ is never a perfect square. So $g$ is a linear function with slope $1$ as needed.

Consider the following claim: Claim: If $p \mid g(a) - g(b)$ for some prime $p$, then we can find $k \in \mathbb Z_{>0}$ such that $\nu_p(g(a) + k) \equiv \nu_p(g(b) + k) \equiv 1 (2)$. Proof. Let $a = \nu_p(g(a) - g(b))$ and let $g(b) = g(a) + p^as$ for some integer $s$. If $a$ is odd, then taking $k$ such that $\nu_p(g(a) + k)$ is large and $\nu_p(g(a) + k) \equiv 1 (2)$ works. Otherwise $a \ge 2$. Then taking $k$ such that $\nu_p(g(a) + k) = 1$ works. $\blacksquare$ Therefore by claim, if $p \mid g(a) - g(b)$ for some $a, b$ and prime $p$ then we can find $k$ such that $\nu_p(g(a) + k) \equiv \nu_p(g(b) + k) \equiv 1 (2)$. Since $(g(n) + m)(g(m) + n)$ is a perfect square for all $m, n \in \mathbb Z_{>0}$, hence $1 \equiv \nu_p(g(a) + k) \equiv \nu_p(g(k) + a) (2)$. Similarly $\nu_p(g(k) + b) \equiv 1 (2)$. Therefore $p \mid g(k) + a - g(k) - b$, or equivalently $p \mid a - b$. Hence if $p \mid g(n+1) - g(n)$ for some $n$ and prime $p$, then we get $p \mid 1$, a contradiction. Thus $|g(n+1) - g(n)| = 1$ for all $n$. Now assume there exists $n$ such that $g(n) = g(n+2)$, then $(g(n) + n + 2)(g(n) + n) = (g(n) + n + 1)^2 - 1$, a contradiction. Thus we get $g(n) = n + c$ for some $c \ge 0$. $\blacksquare$

easy for a p3 imo but really cool The answer is $g(n)=n+c$ which clearly works. The key claim is the following: Claim: If $g(a)\equiv g(b) \pmod p$ Proof. If $g(a)\equiv g(b) \pmod p$, then taking $n$ such that $v_p(n+g(a))$ and $v_p(n+g(b))$ are odd, we obtain $p\mid a+g(n),b+g(n)$ finishing. Such $n$ is possible since If $g(a)\equiv g(b) \pmod p^2$ then $n=p-k$ or $n=2p-k$ for $k<p$ and $p\mid g(a)-k$ will work becasue $v_p(g(a)+n)>1 \iff v_p(g(b)+1)$ Else, $g(a)-g(b)=cp$, where $n=p^{2k-1}-g(a)$ for sufficiently large $k$ works since $g(a)+n=p^{2k+1}$ and $g(b)+n=p^{2k+1}+cp$. $\blacksquare$ Now, we say Claim: $|g(n+1)-g(n)|=1$ Proof. Obviously, they are not equal as then $a(a+1)$ is a square (and it also contradicts the claim lol). And if they differered by $k>1$, taking $p\mid k$ contradicts the first claim. $\blacksquare$ It suffices to show that $g(n)\neq g(n+1)$ which again is easy as $a(a+2)$ can't be a square.

Let $a$ and $b$ be arbitrary positive integers, and let $p$ be a prime dividing $g(a)-g(b)$. Let $k=\nu_p(g(a)-g(b))$. We claim that we may select positive integer $N$ such that $\nu_p(g(a) + k)$ and $\nu_p(g(b) + k)$ are both odd. If $k\ge 2$ then $\nu_p(g(a)+k)=1\iff \nu_p(g(b)+k)=1$ and both can be satisfied simulatenously by picking $k\equiv p-g(a)\pmod {p^2}\equiv p-g(b)\pmod {p^2}$. If $k=1$ then let $k\equiv -g(a)\pmod {p^3}$ then clearly $\nu_p(g(b)+k)=1$ while $\nu_p(g(a)+k)=3$. $~$ Now $(g(a)+k)(g(k)+a)$ is a perfect square so $\nu_p(g(k)+a)$ is odd. Similarly, $\nu_p(g(k)+b)$ is odd, which means that $a\equiv b\equiv -g(k)\pmod p$. Therefore, if $p\mid g(n+1)-g(n)$ then $p\mid 1$, so $|g(n+1)-g(n)|=1$. Furthermore, if $g(a)=g(b)$ then $p\mid a-b$ for all $p$ so $a=b$. This implies that $g(n)=n+c$ for some $c\ge 0$.

\[(g(m)+n)(g(n)+m)\in \mathbb{Z}^2\]Answer is $g(x)=x+c$ for a constant $c\in Z^+\cup \{0\}$. Note that for a prime $p$, $m=p-g(n)$ gives $p|g(p-g(n))+n$ thus, $g$ is unbounded. Lemma: If $x^2+ax+b$ is perfect square for infinitely many positive integer $x$, then it's a square polynomial. Proof: Omitted. Lemma: If a positive integer $n$ is quadratic residue over all modulo primes, then it must be a perfect square. Proof: Let $p_1\dots p_k$ be the squarefree part of the number. Note that this number is not $2$ because $(\frac{2}{3})=-1$ so $p_k>2$. Pick a prime number $q$ which holds $q\equiv 1(mod \ 4p_1\dots p_{k-1})$ and let $q$ be a quadratic non-residue on $(mod \ p_k)$. Such $q$ exists by Drichlet and Chinese Remainder Theorem. We have $(\frac{p_1\dots p_k}{q})=(\frac{p_1}{q})\dots (\frac{p_{k-1}}{q})(\frac{p_k}{q})=(\frac{q}{p_1})\dots (\frac{q}{p_{k-1}})(\frac{q}{p_k})=(\frac{p_k}{q})=-1$.$\square$ Claim: $(m-n)(g(m)-g(n))$ is perfect square. Proof: We see that $p|g(p-g(m))+m$. Replace $p-g(m)$ with $m$ in order to get $(g(p-g(m))+n)(g(n)+p-g(m))$ is a perfect square. $LHS$ must be quadratic residue $mod p$ hence \[1=(\frac{(g(p-g(m))+n)(g(n)+p-g(m))}{p})=(\frac{(n-m)(g(n)-g(m))}{p})\]By the lemma, $(m-n)(g(m)-g(n))\in \mathbb{Z}^2$.$\square$ Claim: $g$ is injective. Proof: Suppose that $g(a)=c=g(b)$ and $a\neq b$. We observe that $(g(m)+a)(c+m)$ and $(g(m)+b)(c+m)$ are both perfect square thus, their multiplication is also a perfect square. So $g(m)^2+(a+b)g(m)+ab$ is a perfect square. Since $g(m)$ is unbounded, by the lemma we get that $a=b$ which gives a contradiction.$\square$ Claim: $|g(m+1)-g(m)|=1$. Proof: Assume otherwise. Let $p|g(m+1)-g(m)$ which implies $p^2|g(m+1)-g(m)$. Let $g(m)\equiv r\equiv g(m+1)(mod \ p^2)$ and pick $n=pk-r$ and $(p,k)=1$. We see that $\nu_p(g(m)+n)=1=\nu_p(g(m+1)+n)$. \[\nu_p(g(n)+m)\equiv \nu_p(g(m)+n)\equiv 1\equiv \nu_p(g(m+1)+n)\equiv \nu_p(g(n)+m+1)(mod \ p)\]However $p|g(n)+m+1$ and $p|g(n)+m$ are impossible. Thus, $g(m+1)-g(m)=\pm 1$.$\square$ Since $g$ is injective, we must have $g(x+1)-g(x)=1$ hence $g(n)=n+c$ as desired.$\blacksquare$