# 2019 APMO P1
## 題目
Let $\mathbb{Z}^+$ be the set of positive integers. Determine all functions $f : \mathbb{Z}^+\to\mathbb{Z}^+$ such that $a^2+f(a)f(b)$ is divisible by $f(a)+b$ for all positive integers $a,b$.
## 解法1
令$P(a, b)$代表$f(a)+b|a^2+f(a)f(b)$
$P(1, 1): f(1)+1|f(1)^2+1\Rightarrow f(1)+1|(-1)^2+1=2\Rightarrow f(1)=1$
令$p$為奇質數
$P(p, 1): f(p)+1|p^2+f(p)\Rightarrow f(p)+1|p^2-1$---(1)
$P(p, p): f(p)+p|p^2+f(p)^2\Rightarrow f(p)+p|p^2+(-p)^2=2p^2$
$\because f(p)+p>p\therefore f(p)+p=2p, p^2$, or $2p^2$
$\Rightarrow f(p)=p, p^2-p$, or $2p^2-p$
將這三個帶入(1):
$f(p)=2p^2-p: 2p^2-p+1|p^2-1$ but $|2p^2-p+1|>|p^2-1|>0$(矛盾)
$f(p)=p^2-p: p^2-p+1|p^2-1\Rightarrow p^2-p+1|p-2$ but $|p^2-p+1|>|p-2|>0$(矛盾)
所以$f(p)$只能是$p$
對於任意正整數$b$，取夠大的質數$p$滿足$\gcd(p, b)=1$
$P(p, b): p+b|p^2+pb=p(p+f(b))$
$\because\gcd(p, b)=1\therefore p+b|p+f(b)\Rightarrow p+b|f(b)-b$
因為可以取夠大的質數$p$，所以$|p+b|>|f(b)-b|$ but $p+b|f(b)-b$
$\Rightarrow f(b)=b,\; \forall b\in\mathbb{Z}^+$

## 解法2
同解法1中算出$f(1)=1$
使用數學歸納法證明對於所有的$n\in\mathbb{Z}^+$，$f(n)=n$
當$n=1$時$f(1)=1$成立
設當$n=k$時$f(k)=k$
則當$n=k+1$時：
$P(k+1, k): f(k+1)+k|(k+1)^2+f(k+1)k\Rightarrow f(k+1)+1|(k+1)^2-k^2=2k+1$
$\Rightarrow f(k+1)+k\leq 2k+1\Rightarrow f(k+1)\leq k+1$
又$P(1, k+1): 1+k+1|1+f(k+1)\Rightarrow k+1\leq f(k+1)$
$\therefore f(k+1)=k+1$，歸納假設成立
$\therefore\forall n\in\mathbb{Z}^+$，$f(n)=n$