can be done easily using dirichlet's theorem

Here it is a solution that I did find when I did get the shortlist. Somehow for me it took me faster to solve this then N1 which was on the test. Also it should be $a+b>C$ and not $a+b>2019.$ Since $gcd(f(1),1)=1$ from Dirichlet's theorem we have there exist infinitely prime numbers of the form $1+nf(1)$. Taking all such $n>C$ then for $a=1$ and $b=n$ we have, $$1+f(n)|1+nf(1)\Rightarrow f(n)=nf(1).$$ Now taking $a$ fixed and $b=n>C$ large enough we have, $$a+nf(1)|a+f(n)|a^2+nf(a)|f(1)a^2+f(1)nf(a)\Rightarrow a+nf(1)|f(1)a^2+f(1)nf(a)-(a+nf(1))f(a)$$$$\Rightarrow a+nf(1)|a(f(1)a-f(a))\Rightarrow f(a)=f(1)a=ka.$$ Hence $f(a)=ka$ for all positive integers $a$, and clearly for any positive integer $k$ hold.

Oh wow, I thought my solution was pretty unique to use Dirichlet's Theorem, but it seems other people had the same idea lol oops

Comment: Extremely standard NT functional divisibility. This trick used to solve this problem have been appeared many many times. As in every functional divisibility problems, the main point is to prove that $f$ is linear on some infinite set. We prove the following claim. Claim: There exists infinite sequence $C<x_1<x_2<\hdots$ such that $f(x_i)=kx_i$ for some constant $k$. Proof: The idea is to force the right hand side to be prime. By Dirichlet, there exists infinitely many $x>C$ which $1+xf(1)=p$ is prime. However, $$1+f(x)\mid xf(1)+1\implies f(x)+1\in\{1,p\}\implies f(x)=xf(1)$$for infinitely many $x$. Hence we are done. $\blacksquare$ Once we have this we are almost done. Fix $n\in\mathbb{Z}^+$. Since \begin{align*} &n+kx_i\mid n^2+x_if(n) \\ \implies &n+kx_i\mid k(n^2+x_if(n)) - f(n)(n+kx_i) \\ \implies &n+kx_i\mid kn^2-nf(n) \end{align*}and $x_i$ is arbitrarily large. We get $f(n)=kn$ for any $n$.

nukelauncher wrote: Find all functions $f:\mathbb Z_{>0}\to \mathbb Z_{>0}$ such that $a+f(b)$ divides $a^2+bf(a)$ for all positive integers $a$ and $b$ with $a+b>2019$. It somehow seemed very easy to me than N1.

Let $P(a,b)$ denote the assertion that $a+f(b) \mid a^2+bf(a)$. Naturally, a $P(1,b)$ substitution gives us $1+f(b) \mid 1+bf(1) \implies bf(1) \geq f(b)$. We'll now denote $f(1)$ by $k$, as we shall be using it quite extensively. $P(a,1): a+k \mid a^2+f(a) \implies a+k \mid a^2+f(a)-a(a+k) \implies a+k \mid f(a)-ak \implies a+k \mid f(a)-ak +k(a+k)$. Hence we get $a+k \mid f(a)+k^2$. Coupled with our first bound, this gives us that $f(a)=at+tk-k^2$ for large enough $a$. Here, although it is quite instinctual to substitute $a$ as a prime, we can in fact avoid that altogether and deal just with our regular naturals- although it will get quite ugly, but at the very least it will remain very mechanical. Our aim, as it always is in such problems, is to manipulate the divisibility so as to be able to make the left hand side arbitrarily large without altering the expression on the right, hence forcing the right hand side to be become zero. A simple $(a,b)$ substitution in the original expression with a little modification would give us what we're looking for. Firstly- $$a+f(b) \mid a^2+bf(a) \implies a+f(b) \mid a^2+bf(a)-a(a+f(b))$$$$\implies a+f(b) \mid bf(a)-af(b) +f(b)(a+f(b)) \implies a+f(b) \mid bf(a)+f(b)^2$$ Thus we have $a+f(b) \mid f(b)^2 + bf(a)$. We now substitute $f(a)=at+(k^2-kt)$ to get- $$a+f(b) \mid b(at+k^2-kt)+f(b)^2$$$$\implies a+f(b) \mid abt+bk^2-bkt+f(b)^2-bt(a+f(b)) \implies a+f(b) \mid b(k^2-kt)+f(b)^2-btf(b)$$Observe now that we can make our $a$ arbitrarily large for a constant $b$, and noting that $k=f(1)$ has a fixed value along with $t \leq k$ forces $f(b)^2-btf(b)+b(k^2-kt)=0$, as planned. Writing $f(b)=rb+rk-k^2$ gives us $(rb+rk-k^2)^2-bt(rb+rk-k^2)+b(k^2-kt)=0$. For large $b$, since our $k$ and $t$ are small (compared to our now large $b$), we can simply equate the coefficients of $b^2$ and $b$ and the constant term zero individually. Hence, $r^2-rt=0 \implies r=t$ and equating the constant term to zero gives us $r=k$. Thus, for arbitrarily large $n$, we have $f(n)=kn$. The finish is now quite simple- $$P(n,b): n+f(b) \mid n^2+knb-n(n+f(b))-(kb-f(b))(n+f(b))$$$$\implies n+f(b) \mid (kb-f(b))f(b)$$for large $n$, hence forcing $f(b)=kb$ for all $b$. Clearly $f(n)=kn$ satisfies the original condition, and hence we're done. Quite a standard one, and rather mechanical, especially if you've done something like this before (POP). Nevertheless, quite an instructive exercise on functional divisibilities...

guess this has been said before, but here goes We claim the answer is $f(x)=kx$ for $k\in \mathbb{Z}_{>0}.$ Fix $a=1.$ Note that $1+bf(1)$ is a prime infinitely often by Dirichlet (is this how you spell it?). So let $b$ be some absurdly large number such that $a+b>2019$ and $1+bf(1)$ is prime; then $1+f(b)\mid 1+bf(1).$ Since $1+bf(1)$ is prime we either have $1+f(b)=1$ or $1+f(b)=1+bf(1).$ Clearly the latter holds, so there are infinitely many $b$ such that $f(b)=bf(1).$ Now take some mega ultra large $b$ such that $f(b)=bf(1),$ and note that $a+f(b)=a+bf(1)\mid a^2+bf(a)$ and $a+bf(1)\mid a^2+abf(1).$ Subtracting the latter from the former gives $a+bf(1)\mid b(f(a)-af(1)).$ Note that $\gcd(a+bf(1),b)=\gcd(a,b),$ so if $a$ is prime this implies that $a+bf(1)\mid f(a)-af(1).$ Since $b$ is, as I quote, "ultra mega large," $|a+bf(1)|>|f(a)-af(1)|,$ so for all prime $a$ we have $f(a)=af(1).$ Now take some ultra mega large prime $b,$ which we have just shown exists, and note that \[a+bf(1)\mid b(f(a)-af(1)), \text{ which implies that}\]\[a+bf(1)\mid f(a)-af(1),\]and since $b$ is ultra mega large, we have shown that $f(a)=af(1)$ in general.

Solution by my friend RustyFox who is banned now.So I am posting his solution. nukelauncher wrote: Find all functions $f:\mathbb Z_{>0}\to \mathbb Z_{>0}$ such that $a+f(b)$ divides $a^2+bf(a)$ for all positive integers $a$ and $b$ with $a+b>C$. Solution : Let $P(x, y)$ be the assertion. $P(1, k) \implies kf(1)\geq f(k)$. This is going to be useful. Let $p \mid x$ where $p$ is a prime. Let $k = Cf(x)$ $P(kp-f(x), x \implies kp \mid (kp-f(x))^2 + f(kp-f(x))x$ which means that $p \mid f(x)$. So, $p \mid f(p)$ for all primes $p$. Let us say that $f(p)= g(p)p$ for primes $p$. Observe that $0 < g(p) \leq f(1)$. If $g(p)\neq g(q)$ for two distinct primes $p, q$ which are much much greater than $C$ (say it's much greater than $(C+2019f(1))!\uparrow \uparrow (C+2019f(1))!)$, then $P(p, q) \implies p + qg(q) \mid p^2 + pqg(p)$ or in other words $p + qg(q) \mid pq(g(p)-g(q))$. Now since $gcd(p, q) = gcd(p, g(q)) = gcd(p, qg(q)) = 1$, we havs $p + qg(q) \nmid pq$. Now, $p + qg(q) \mid g(p)-g(q)$ but the dividend is less than $f(1)$ and due to our value of $p, q$, $p + qg(q) >> f(1)$ which means that for all sufficiently large primes we have $g(p) = g(q) = c$. Now for any prime $p$ such that $f(p) = pc$ and any other prime $q$ for which we aren't sure if $f(q)$ equals $qc$ or not and obviously here $q < p$,we take $P(q, p)$ to get that $q + pc \mid p(f(q)-qc)$ and since $pc + q > pc \geq p$, we havs $q + pc \mid f(q)-qc$ and so see that $f(q) - qc \leq qf(1)-qc = q(f(1)-c)$ and so choosing $p > q(f(1)-c)$ would suffice and so for all primes $p$, we have $f(p)=pc$. Now, let $p >>a$. Then $P(a, p) \implies a + pc \mid pf(a)-pca$ but $gcd(p, a)=1$ and so $a+pc \mid f(a)-ac$. Choosing large enough $p$ yields that $\boxed{f(a)=ac}$ for all naturals $a$

Since gcd(f(1,),1)=1 from Dirichlet's theorem we have there infinitely prime numbers of the form 1+nf(1). Taking all such n>C then for all a=1 and b=n we have $$1+f(n)|1+nf(1)\Rightarrow f(n)=nf(1).$$Now taking a fixed and b=n> C large enough we have, $$a+nf(1)|a+f(n)|a^2+nf(a)|f(1)a^2+f(1)nf(a)\Rightarrow a+nf(1)|f(1)a^2+f(1)nf(a)-(a+nf(1))f(a)$$$$\Rightarrow a+nf(1)|a(f(1)a-f(a))\Rightarrow f(a)=f(1)a=ka.$$hence f(a)=ka for all positibe integers , clearly for any positive integer k hold. Acknowledgements to dangerousliri's in post 4. I didn't make it.

Let $P(a,b)$ denote the assertion of the question. Claim:For all prime $p$ we have $p|f(p)$. proof.Fix a prime $p$.$k$ be an integer such that $(k+1)p-f(p)>2020^{2020}$.Then $P(kp-f(p),p)\implies p|kp-f(p)+f(p)|(kp-f(p))^2+pf(stuff)\implies p|f(p)$. $\blacksquare$. Then $f(p_n)=c_np_n$ where $p_n$ is the $n^{th}$ prime.But as $P(1,b)\implies f(b)\le f(1)b$ $\forall b\ge 2020$. So $c_n$ is bounded sequence.Hence,there exists an integer $r$ such that it is equal to infinitely many $c_i$.So there exists an increasing sequence $(q_n)_{n=1}^{\infty}$ of prime integers such that $f(q_s)=rq_s$ $\forall s\in \mathbb N$. Now, for a fix $a$ take a big $q_i$ such that $gcd(a,q_i)=1$.Then, $P(a,q_i)\implies\\ a+rq_i|a^2+q_if(a)\\ \implies a+rq_i|a^2+q_if(a)-a^2-arq_i\\ \implies a+rq_i|q_i(f(a)-ar)\\ \implies a+rq_i|(f(a)-ar)$. Now for sufficiently large $q_i$ we get $f(a)=ar$.Hence,$\boxed{f(x)=rx}$ is the only solution which indeed satisfies the functional equation. $\blacksquare$.

Let $P(a,b)$ denote the divisibility $(a+f(b)) \mid (a^2+bf(a)). ($For simplicity say $C = 2019)$ Let $n$ denote $f(1).$ We are going to show that $f(k) = kn,$ for all $k \in \mathbb{Z}_{>0}.$ Let $\mathbb{A} = \{C+1, C+2, ...\}.$ Lemma 1: Define $g:\mathbb{A} \rightarrow \mathbb{Q}$ as $g(a) = \frac{an-f(a)}{a+n},$ then $g$ is limited. Proof: Let $a$ be a positive integer greater than $C.$ Then $P(a,1)$ gives $a+n \mid a^2 + f(a) \implies (a+n).q = a^2 + f(a)$ with $q \in \mathbb{N}.$ On the other hand $P(1, a) \implies 1+f(a) \mid 1+an \implies f(a) \leq an,$ therefore $(a+n).a =$ $a^2 + an \geq a^2 + f(a), $ suppose for the sake of contradiction that $f(a) < an \implies q < a \implies q = a-k$ so $(a+n)(a-k) = a^2 + f(a) > a^2,$ since $(a+n)(a-n) < a^2$ we have $k < n \implies k$ is bounded as $a$ varies along the natural numbers greater than $C,$ yielding $k = \frac{an-f(a)}{a+n} = g(a)$ is limited.$\blacksquare$ Lemma 2: There are infinitely many positive integers $s$ such that $f(s) = sn.$ Proof: Let $S = \{a_1, a_2, ...\}$ be the set of positive integers such that $\frac{a_in-f(a_i)}{a_i+n} = t$ a constant, with $C < a_1 < a_2 < ...,$ there exists such $t,$ because the set $\mathbb{A}$ is unbounded. So $\frac{a_in-f(a_i)}{a_i+n} = t \implies$ $f(a_i) = a_in-t(a_i+n),$ for all $i.$ Now fix $j$ such that $a_j(n-t+1) \ne nt.$ Plugging $a = a_i, b = a_j$ gives: $$(a_i + f(a_j)) \mid (a_i^2 + a_jf(a_i)) \implies$$$$(a_i + a_jn - t(a_j+n)) \mid [(a_i^2 + a_ja_in - a_jt(a_i+n)) - a_i(a_i+a_jn-t(a_j+n))] \implies$$$$(a_i+a_jn-t(a_j+n)) \mid (a_i-a_j)nt.$$Let $d_i$ be $gcd(a_i + a_jn-t(a_j+n), a_i - a_j),$ (of course $i \ne j$) if $d_i > max(a_j(n-t+1), nt) \implies$ $a_i + a_jn-t(a_j+n) \equiv a_j + a_j(n-t) - nt \pmod {d_i} \implies d_i \mid a_j(n-t+1)-nt,$ as supposed we must have $a_j(n-t+1) = nt,$ contradiction. Therefore $d_i$ is bounded. Observe $(a_i + a_jn-t(a_j+n))|d_int,$ $\forall i \in \mathbb{N}, i \ne j,$ setting $i \rightarrow \infty \implies a_i \rightarrow \infty$ thus, we eventually have: $a_i + a_jn -t(a_j+n) > d_int \implies d_int = 0 \implies t = 0 \implies f(a_i) = a_in,$ for all $i,$ sufficiently large. $\blacksquare$ Fix $k$ a positive integer. Plug $a = k, b = a_i \implies k+a_in \mid k^2 + a_if(k) \implies (k+a_in) \mid (k^2+a_if(k) - k(k+a_in)),$ yielding $(k+a_in) \mid a_i(f(k)-kn)$ so $(k+a_in).q_i = a_i.|f(k)-kn|, q_i \in \mathbb{Z}_{\geq 0} \implies q_i = \frac{a_i.|f(k)-kn|}{k+a_in}$ call $t = |f(k)-kn|$ a constant. If $q_i > t \implies (k+a_in).t < a_i.t$ contradiction. We conclude $q_i$ is bounded. On the other hand if $i \ne j$ and $q_i = q_j \implies \frac{a_it}{k+a_in} = \frac{a_jt}{k+a_jn}$ $\implies a_itk + a_ia_jnt = a_jtk + a_ja_int \implies (a_i-a_j)kt = 0$ then $t$ would be $0.$ Since $q_i, q_j$ are bounded, both positive and we can choose $i, j \in \mathbb{N}$ such that $q_i = q_j, f(k)-kn = 0$ for all $k \in \mathbb{N},$ as $(a+kb).a = a^2 + akb \implies f(a) = an$ for all positive integers $n.$

Remark: Standard problem, seems pretty easy in difficulty unless I messed up. Also, I cite the so called Weak - Dirichlet theorem many times over this proof. Although no proof of Dirichlet Theorem that I know of is elementary, Weak Dirichlet can easily be proven by cyclotomic polynomials - see Evan Chen's Orders handout for more details.

We claim that the answer is all functions $f(x) \equiv cx$ for any positive integer $c$. It's easy to see that all such functions work, because $a + bc | a^2 + abc = a(a+bc)$. Now we show that these are the only functions that work. Consider the more general problem, replacing $2019$ with any constant $C$. Denote the given assertion$P(a,b)$. Now we claim that $f(b) = bf(1)$ holds for infinitely many $b$. Indeed, $P(1,b)$ gives $1 + f(b) | 1 + bf(1)$, and now by Weak Dirichlet, there exists infinitely many $b$ such that $bf(1) + 1$ is prime, and since $1 + f(b) > 1$, we have $f(b) = bf(1)$, as desired. Now we show that this actually implies $f(a) = af(1)$ for all $a$. Indeed, by Weak Dirichlet again, there exists infinitely many primes that are $1 \pmod{f(a) \cdot f(1)}$ for any $a$. Now take a prime of this form, $p$, and let $p$ be arbitrarily large. Note that $p$ is relatively prime to $f(a)$, and it is also of the form $cf(1) + 1$ for some $c$, hence by the first claim, $f(p) = pf(1)$. Then $P(p,a)$ gives $p + f(a) | p^2 + apf(1)$. Now $\gcd(p, p+f(a)) = \gcd(p,f(a)) = 1$ by the assumption that $p$ is $1 \pmod{f(a)}$, so the extra factor of $p$ on the $RHS$ can be taken out. Now we have $p + f(a) | p + af(1)$ for all $a$, and since $p$ is arbitrarily large, so that $p >>> f(a), af(1)$, so the two sides are actually equal, and we are done.

Pretty standard NT FE problem... From the problem, $1+f(n)|1+nf(1)$ for all $n \in \mathbb{N}$. From Dirichlet's Theorem, since $gcd(1,f(1))=1$, there are infinetly prime numbers in the AP $\{1+nf(1)\}_{n \geq 1}$. Thus, since $1+f(n)>1, 1+f(n)=1+nf(1)$ when $1+nf(1)$ is prime $\implies f(n)=nf(1)$ in this case. Hence, there exists a sequence $\{a_n\}_{n=1}^{\infty}$ such that $f(a_n)=a_nf(1)$ for all $n \in \mathbb{N}$. Then, from the problem, $$a+a_nf(1)|a^2+a_nf(a) \implies a+a_nf(1)|a^2f(1)+a_nf(a)f(1),af(a)+f(a)f(1)a_n$$$$\implies a+a_nf(1)|a^2f(1)-af(a)$$for all $n \in \mathbb{N}$ Taking $n$ large enough, $a^2f(1)-af(a)$ must be $0$. Therefore, $f(a)=af(1)$ for all $a \in \mathbb{N}$, which clearly works. $\blacksquare$

A solution without using Dirichlet's Theorem: \[ a+f(b)\mid a^2+bf(a) \]is equivalent to \[ a+f(b)\mid f(b)^2+bf(a) \]$b=1$ gives for $a\geq C$: \begin{align*} a+f(1)\mid f(1)^2+f(a)\\ a+f(1)\leq f(1)^2+f(a)\\ f(a)\geq a+f(1)-f(1)^2 \end{align*}In the original condition, $a=1$ gives for $b\geq C$: \begin{align*} 1+f(b)\mid 1+bf(1)\\ 1+f(b)\leq 1+bf(1)\\ f(b)\leq bf(1) \end{align*}We get $f\in\Theta(n)$. For $n\geq C$ the conditions $n+f(1)\mid f(1)^2+f(n)$ and $1+f(n)\mid 1+nf(1)$ imply: \[ (n+f(1))(1+f(n))\mid(f(1)^2+f(n))(1+nf(1)) \]Since $f\in\Theta(n)$ and $(n+f(1))(1+f(n))=nf(n)+ O(n)$ and $(f(1)^2+f(n))(1+nf(1))= f(1)nf(n)+ O(n)$, the quotient $\frac{(f(1)^2+f(n))(1+nf(1))}{(n+f(1))(1+f(n))}$ must be $f(1)$ for sufficient large $n$. Now, we have for sufficent large $n$: \begin{align*} f(1)(n+f(1))(1+f(n))=(f(1)^2+f(n))(1+nf(1))\\ f(1)n+f(1)^2f(n)=f(n)+f(1)^3n\\ (f(1)^2-1)f(n)=(f(1)^2-1)f(1)n \end{align*}We got either $f(n)=f(1)n$ for sufficent large $n$ or $f(1)=1$. In the case $f(1)=1$, we get using $n+f(1)\mid f(1)^2+f(n)$ and $1+f(n)\mid 1+nf(1)$ : \[ n+1\mid f(n)+1\mid n+1 \]and $f(n)=n=f(1)n$ for sufficent large $n$. If $n$ is not so large, let $p$ be a prime sufficent large for $f(p)=f(1)p, p>f(1)n,p>f(n)$ and $p+n>C$. Plugging $a=p$ and $b=n$ in the original condition gives: \[ p+f(n)\mid p^2+nf(p)=p(p+f(1)n) \]Since $p<p+f(n)<2p$, $p$ does not divide $p+f(n)$. So we must have \[ p+f(n)\mid p+f(1)n \]Since $0<p+f(1)n<2p<2(p+f(n))$, we must have $p+f(n)=p+f(1)n$ and \[ f(n)=f(1)n \]for any positive integer. Obviously, $f(n)=kn$ works for any positive interger $k$.

Our team solution. Sorry for pic and Russian language.

I thought this was hard?!?!? I'm prolly just bad. Let $P(a, b)$ denote the assertion. $P(1, b) \implies 1 + f(b) \mid 1 + bC$ where $f(1) = C$ is constant. By Dirichlet's, there are infinitely many positive integers $b_i$ for which $1 + b_iC$ is prime. For these $b_i$, it follows that $1 + f(b_i) \in \{1, 1 + b_iC\} \implies f(b_i) = Cb_i$. Now choose a really large $b_j$. Consider $P(x, b_j)$ for any $x$ (small enough). We get\begin{align*}&x + Cb_j \mid x^2 + f(x)b_j\\ \implies &x + Cb_j \mid C(x^2 + b_jf(x)) - f(x)(x + Cb_j) \implies x + Cb_j \mid Cx^2 - xf(x) \end{align*}Since $b_j$ is assumed to be super large it forces $Cx^2 - xf(x) = 0 \implies f(x) = Cx$ as desired. It is easy to check that all $f(x) = Cx$ for constants $C$ work. $\blacksquare$

nukelauncher wrote: Find all functions $f:\mathbb Z_{>0}\to \mathbb Z_{>0}$ such that $a+f(b)$ divides $a^2+bf(a)$ for all positive integers $a$ and $b$ with $a+b>2019$. Posted for storage. Let $p(a,b)$be the assertion for $a+f(b)$ divides $a^2+bf(a)$. $p(1,n)$ ,we get that $1+f(n)|1+nf(1)$...(1) its obvious that $gcd(1,f(1))=1$,so from Dirichlet we get that there exist infinitely many prime numbers such that $q=1+nf(1)$. Now geting back at ...(1) we get that $1+f(n)\mid nf(1)+1\implies f(n)+1\in\{1,p\}\implies f(n)=nf(1)$. Now let us fix $a$ and take p(a,n) such that $n>2019$ we get that $a+nf(1)|a^2+nf(a)$ $a+nf(1)|f(1)(a^2+nf(a))-f(a)(a+nf(1))$ $a+nf(1)|a^2f(1)-af(a)$ now taking n-very larg we get that, $a^2f(1)-af(a)=0$, which gives us $f(a)=ac$

Died on this problem twice before, but now I've solved it ISL 2004 N3 helps quite a bit, since the main idea is the same, although here it is probably a bit more difficult. The idea is to do things to show that $f$ is unbounded but that $a+f(b)$ divides some expression in $a$ and do things with primes. The answer is $f(x)=cx$ only, which can be easily verified to work. Let the assertion be denoted by $P(a,b)$. From $P(1,b)$ with $b \geq 2019$ we obtain: $$f(b)+1 \mid bf(1)+1.$$By Dirichlet's theorem, there exist infinitely many primes $p$ of the form $bf(1)+1$. Suppose we pick a $b$ such that $bf(1)+1$ is prime. Then we need $f(b)+1 \in \{1,bf(1)+1\}$, but $f(b)+1=1$ is impossible so $f(b)+1=bf(1)+1 \implies f(b)=bf(1)$ when $bf(1)+1$ is prime. The important conclusion from this is that there exist infinitely many $b$ with $f(b)=bf(1)$, since $bf(1)+1$ being prime occurs infinitely often. Now by $P(a,b)$ where $bf(1)+1$ is a prime and $b \geq 2019$ we obtain after using $f(b)=bf(1)$: $$a+bf(1) \mid a^2+bf(a) \mid a^2f(1)+bf(1)f(a),$$hence by the Euclidean algorithm we require: $$a+bf(1) \mid a^2f(1)-af(a).$$Suppose $a^2f(1)-af(a) \neq 0$. Then we can fix $a$ and pick $b$ large enough, such that $a+bf(1)>|a^2f(1)-af(a)|$, which implies for size reasons that $a+bf(1) \nmid a^2f(1)-af(a)$, contradiction. Thus we require $a^2f(1)-af(a)=0$ for all $a$, which easily gives $f(a)=af(1)$ and thus $f(x)=cx$ for some positive integer $c$. $\blacksquare$

Another problem of similar flavor.. There are infinite n s.t. $1+nf(1)$ is prime by Dirichlet's, so from (n,1): $1+f(n) \mid 1+nf(1)$, we have nf(1)=f(n) for infinite n. Take i as one of these numbers, and j as an arbitary number; (i,j) gives $i+f(j)\mid i^2+jf(i)=i^2+jf(i)-i(i+f(j))=(i-(i+f(j))(jf(1)-f(j))$; taking i sufficiently large, LHS>RHS which is fixed, hence RHS=0, or jf(1)=f(j) for all j; in particular, f(n)=nc for c=f(1). Remark. The infinitude of n and such i makes the a+b>2019 a "red herring", as evan likes to say

Subpar dirch app Fix some $b$. We now show that $f(b) = b$. Let $c = f(1)$. Claim: $f(x) = cx$ holds infinitely many times. Furthermore, if $f(b) - cb \ne 1$, then $x \not\equiv 0 \pmod{f(b) - cb}$ holds infinitely many times. Proof. $1 + c = 1 + bc$ holds by the assertion whenever $1 + bf(1)$ is prime, which occurs infinitely many times by Dirichlet's. If $f(b) - cb \ne $, then by taking $1 + bf(1)$ to be $1 + f(1) \pmod{f(1) \cdot (f(b) - cb)}$, it follows that $b \not\equiv 0 \pmod{f(b) - cb}$. $\blacksquare$ Claim: $f(b) = c \cdot b$. Proof. Consider $f(b)$. We have that $a + f(b) \mid a(a + cb)$ for infinitely many $a$., and thus $\gcd\{a + f(b), a + cb\} > 1$ for arbitrarily large $a \not\equiv 0 \pmod{f(b) - cb}$. This results in contradiction unless $f(b) - cb = 0$. $\blacksquare$

The answer is $f(x) = xk$ for some $k \ge 1$. Let $P(a, b)$ be given assertion. Then $P(1, b)$ gives $1 + f(b) \mid 1 + bf(1)$, so $f(b) \le bf(1)$ for all $b \ge 2019$. Claim: Let $p \ge 2019$ be a prime. Then $p \mid f(p)$. Proof: Assume the contrary, $\gcd(p, f(p)) = 1$. Take integer $a$ such that $p \mid a + f(p)$. Then $P(a, p)$ gives $a + f(p) \mid a^2 + pf(a)$, so $p \mid pf(a) - af(p)$. Thus $p \mid af(p)$, a contradiction. $\blacksquare$ Claim: If $p$ is sufficiently large prime, then $f(p) = pf(1)$. Proof: $P(p, 1)$ gives $p + f(1) \mid p^2 + f(p)$, so since $\gcd(p, p + f(1)) = 1$, we have $p + f(1) \mid p + \frac{f(p)}{p} \le p + f(1)$. Thus $f(p) = pf(1)$. $\blacksquare$ Now fix any positive integer $a$. Take sufficiently large prime $p$. Then $P(a, p)$ gives $a + pf(1) \mid a^2 + pf(a)$, so $a + pf(1) \mid p(f(a) - af(1))$ and since $\gcd(p, a + pf(1)) = 1$, thus $a + pf(1) \mid af(1) - f(a)$. So it forces $f(a) = af(1)$. Therefore for all $x$, we have $f(x) = xk$ for some $k$. $\blacksquare$

Straightforward with a little twist at the end. The given condition rewrites as $$a+f(b) \mid bf(a) - af(b).$$Setting $a=1$, we have $1+f(b) \mid 1+bf(1)$, so $f(b) \leq bf(1)$ for $b \geq 2019$. On the other hand, using this exact same equation, force $1+bf(1) = p$ for some prime $p$ using Dirichlet. It follows that $f(b) = p-1$. For the next step, I claim that for any $a$ with $\gcd(a, 1+f(1)) = 1$, we have $f(a) = f(1)a$. To see this, pick $b = ak+1$ such that $1+(ak+1)f(1) = p$ for a prime $p$ by Dirichlet again. Then, the given equation rewrites as $$a+f(1)b \mid b(f(a) - af(1)).$$Because $\gcd(a, b) = 1$, by making $b$ arbitrarily large, we can force $f(a) = af(1)$. Finally, to extend to all positive integers $n$, simply set $a$ to be a sufficiently large prime and repeat the process with $(n, a)$ instead of $(a, b)$.

It seemed similar to 2019 APMO P1 initially but after working on it it is just an application of Dirichlet's.. Let $P(x,y)$ be the given assertion. $P(1, b)$ yields $1 + f(b)| 1 + bf(1)$. We know that $\text{gcd}(f(1), 1) = 1$, so by Dirichlet's, there exist infinitely many $b$ for which $1 + bf(1)$ is prime. Since $f(b) > 0$, we have $1 + f(b) = 1 + bf(1) \implies f(b) = bf(1)$. Now, we use such $b$ and substitute $P(a,b)$: $$a + f(b)| a^2 + bf(a) \implies a + bf(1) | a^2 + bf(a) \implies a + bf(1) | f(1)(a^2 + bf(a)) - f(a)(a + bf(1)) \implies a + bf(1) | a^2f(1) - af(a)$$For sufficiently large $b$, $a + bf(1) > a^2f(1) - af(a) \implies a^2f(1) - af(a) = 0 \implies f(a) = ca$ where $c$ is some constant. Substituting this back into the assertion it clearly works so we are done.

Solved in 10 mins. Was an application of Dirichlet's.

We claim our only answer is $\boxed{f(x)=cx}$. Denote the assertion as $A(a,b)$. We first rewrite our condition as \[a+f(b) \mid (a^2+bf(a)) - a(a+f(b)) = af(b) - bf(a).\] Consider the infinite set of primes $p \equiv 1 \pmod{f(1)}$ greater than 2019, which exists by Dirichlet. Then \[A\left(1, \frac{p-1}{f(1)}\right) \implies f\left(\frac{p-1}{f(1)}\right) = p-1.\] Afterwards, we can choose a prime $q \neq f(1)$ and a sufficently large $p$ with $\gcd(q,p-1) = 1$. Then \[A\left(q, \frac{p-1}{f(1)}\right) \implies f(q) = qf(1).\] Thus we can finish by fixing an integer $k$, allowing $q$ to be sufficiently large, and using $A(k,q)$. $\blacksquare$

It is easy to see that all functions of the form $f(x) = cx$ for some $c \in \mathbb{Z}_{>0}$ works. We will show that these are the only possible functions. Lemma: There are infinitely many $x \in \mathbb{Z}_{>0}$ such that $f(x) = xf(1)$. Proof: Assume $x$ is sufficiently large. Setting $a = 1$ and $b = x$ in the condition, we have $f(x) + 1 \mid xf(1) + 1$. By Dirichlet's theorem, there are infinitely many $x$ such that $xf(1) + 1$ is prime. Since $f(x) + 1 > 1$, this forces $f(x) + 1 = xf(1) + 1$, so $f(x) = xf(1)$. $\square$ Now consider any integer $k > 1$; we claim that $f(k) = kf(1)$. To do that, consider setting $b = k$; then $a + f(k) \mid a^2 + kf(a)$ for sufficiently large $a$. By the lemma, $a + f(k) \mid a^2 + akf(1)$ for infinitely many $a$. Subtracting $a(a + f(k))$ from $a^2 + akf(1)$ gives $a + f(k) \mid a(kf(1) - f(k))$. Let $C = kf(1) - f(k)$; we want to show $C = 0$. The divisibility implies $\frac{Ca}{a + f(k)} = C - \frac{Cf(k)}{a + f(k)}$ is an integer for infinitely many $a$, so $y = \frac{Cf(k)}{a + f(k)}$ is an integer for infinitely many $a$. But if $C > 0$, then $y$ lies strictly between $0$ and $1$ for all large $a$; if $C < 0$ then $y$ lies strictly between $-1$ and $0$ for all large $a$. Therefore $C = 0$.

@above As mentioned abpve , we can do use Dirchlet theorem,which basically is a corollary of Chebotarev density theorem (Galois Closure etc)

ooga booga force prime The answer is $f(x) = Cx$ for any $x$. Let $C = f(1)$. Claim: For any prime $p = 1 + kC$ (of which infinitely many $p$ and $k$ exist by Dirichlet), $f(k) = Ck$. Proof. $P(1, k)$ gives $1 + f(k) \mid 1 + kC$, and since $1 + kC$ is prime, $1 + f(k) = 1 + kC$ so $f(k) = Ck$. $\square$ To finish, select a sufficiently large $k$ that satisfies the conditions in the claim and consider $P(a, k)$ for arbitrary $a \in \mathbb{N}$ - we have $a + Ck \mid a^2 + kf(a)$, or $a + Ck \mid C(a^2 + kf(a)) - f(a)(a + Ck) = Cn^2 - nf(n)$, and since $k$ is sufficiently large this forces $f(n) = Cn$.

Answer is $f(n)=cn \ \forall \ n\in Z^+$. We have $a+f(b)|af(b)-bf(a)$ for $a+b>2019$. Let $f(1)=k$. Take a large enough prime $p$. $P(1,p-k)\implies 1+f(p-k)|1+k(p-k)\implies f(p-k)\leq k(p-k)$ Plugging $p-k,1$ gives $p|(p-k)k-f(p-k)$. Note that $(p-k)k\geq f(p-k)$. Since $p|k^2+f(p-k),$ we get that $f(p-k)$ is unbounded. If $k=1,$ then $p|p-1-f(p-1)$ where $0\leq p-1-f(p-1)<p-1$. Hence $f(p-1)=p-1$ for all large enough primes $p$. Plugging back yields \[p-1+f(b)|(p-1+f(b))(f(b)-b)-(p-1)(f(b)-b)=f(b)(f(b)-b)\]If we let $p$ to go to positive infinity, we have $f(b)=b$. If $k>1,$ then taking $a=p-k,b=1$ and $a=1,b=p-k$ give \[p|(p-k)k-f(p-k) \ \text{and} \ f(p-k)+1|(p-k)k-f(p-k)\]If $p$ doesn't divide $f(p-k)+1,$ then \[pf(p-k)+p|\underbrace{(p-k)k-f(p-k)}_{\geq 0}\]If $(p-k)k\neq f(p-k),$ then $f(p-k)<k$ since $pf(p-k)<LHS\leq |RHS|<(p-k)k<pk$. But this contradicts with $p|k^2+f(p-k)$ hence $(p-k)k=f(p-k)$ or $p|f(p-k)+1$. Now assume that there exists infinitely many primes $p$ such that $f(p-k)=k(p-k)$. Plugging $p-k,b$ gives \[p-k+f(b)|(p-k)(kb-f(b)) \ \text{and} \ p-k+f(b)|(p-k)(kb-f(b))+f(b)(kb-f(b))\]Thus, $p-k+f(b)|f(b)(kb-f(b))$ Since there are infinitely many $p$ where $f(p-k)=k(p-k),$ we can take $p$ sufficiently large which forces right hand side to be $0$ so $f(b)=kb$ for all $b$. Suppose that there are finitely many primes which hold $f(p-k)=(p-k)k$. There exists some $N$ such that if $p\geq N$, then $p|f(p-k)+1$. But since $p|f(p-k)+k^2,$ we get that $p|k^2-1$ for infinitely many primes but $k^2-1>0$ is constant hence we get a contradiction.$\blacksquare$

We claim that the answer is \[f(n)=nc\]for all $n \in \mathbb{N}$ and some $c\in \mathbb{Z}_{>0}$. It is clear that these solutions work. Now, we shall show that they are the only ones. First, we consider $a\geq 2019$. Note that $1+a>2019$. Then, we have \[1+f(a) \mid 1+af(1)\]which requires $f(a)\leq af(1)$ for all $a\geq 2019$. We further note that, \begin{align*} a+f(1) &\mid a^2 + f(a)\\ a+f(1) & \mid af(1)- f(a) \end{align*}Thus, if $af(1)\neq f(a)$ we must have \[f(a) \leq af(1) - f(a) - f(1)-a\]Further, say we have \[a+f(1) \mid af(1)-f(a) - kf(1)-ka\]and $f(a) \leq af(1) - kf(1)-ka$ for some $k \in \mathbb{N}$. Then, note that we need from the divisibility, \[a+f(1)\leq af(1)-f(a)-kf(1)-ka \implies f(a)\leq af(1) - f(a) - (k+1)f(1)-(k+1)a \]and we also have \[a+f(1) \mid af(1)-f(a) - (k+1)f(1)-(k-1)a\]of which we know the RHS is positive. Now, this means that if $af(1)\neq f(a)$ we must have $f(a) \leq af(1) - kf(1)-ka$ for all $k$ which clearly cannot be true since $f(1),f(a)>0$. Thus, we conclude that for all $a\geq 2019$, $f(a)=af(1)$. Now, to deal with smaller values. Consider $1\leq b<2019$. Then, consider $a>|f(b)-2bf(1)|$ such that $\gcd(a,b)=1$ which is always possible. Now, we have \begin{align*} b+f(a) &\mid b^2+af(b)\\ af(1)+b &\mid af(b)- abf(1)\\ af(1)+b &\mid a(f(b)-bf(1))\\ a+b &\mid f(b)-bf(1) \end{align*}since $\gcd(a+b,a)=\gcd(a,b)=1$. But, we know that \[|(a+b)|=a+b >|f(b)-2bf(1)|+bf(1) \geq |f(b)-bf(1)|\]which is indeed impossible unless we have $f(b)=bf(1)$. Thus, for all $n\leq 2018$ and all $n\geq 2019$ we have that $f(n)=nf(1)$ which is simply saying that the initially claimed solution is the only one.

Put $a=1$ to get $1+f(b) | 1+bf(1)$. Call $f(1)=c$ for brevity. Then $f(b) \leq cb$. Also, by Dirichlet's, there exist infinitely many $b$ such that $cb+1$ is prime. This gives that $f(b)=cb$ for these $b$. Take $b$ of the above form and very large in size to get $$a+cb | a^2 +bf(a) \implies bf(a)-abc<0 \implies a+cb | abc-bf(a)>0$$Also set $b$ to be coprime to $a$. Hence $a+cb | ac-f(a)$ but since $b$ is large, $f(a)=ac$ and we are done.

Should've been a RELMO problem The answer is $f(x) = cx$ for any positive integer $c$. Claim: Let $K$ be a fixed integer. There exist infinitely many integers $n$ such that $K \mid n$ and $f(n) = nf(1)$. Proof: By Dirichlet's theorem, there exist infinitely many $n$ for which $1+ \tfrac{n}{K} \cdot (K f(1) ) = 1+nf(1)$ is prime. Taking $P(1,n)$ for such $n$ gives us \[1+f(n) \mid 1+nf(1), \]and since $1+f(n) > 1$ it follows that $1+f(n) = 1+nf(1)$, implying the claim. Claim: $f(x) = x$ for each $x$. Proof: Fix $x$ and let $n$ be a sufficiently large multiple of $f(x)$ such that $f(n) = nf(1)$ – let $L = \tfrac{n}{f(x)}$. Taking $P(n,x)$ gives us \begin{align*} n + f(x) & \mid n^2 + nxf(1) \\ n + f(x) & \mid nxf(1) - nf(x) \\ f(x) \cdot (L+1) & \mid L f(x) (xf(1) - f(x)) \\ L+1 & \mid xf(1) - f(x) \\ f(x) & = xf(1). \end{align*}

We claim that the answer is $f(x)=$ @Catherine Xu, which clearly works. Let $f(1)=c$. Claim: If $bc+1=p$ is a prime and $b$ is sufficently large, then $f(b)=p-1$. Plug in $a=1$ to get $$1+f(b)\mid 1+bc.$$If $1+bc$ is prime, then $f(b)=p-1$, as desired (since $1+f(b)$ can't be $1$). In particular, $ac+1$ is prime for infinitely many $a$ by Dirichlet's prime theorem. Thus, let $ac+1=p$ for sufficently large $a$, so $$a+f(b)\mid a^2+abc.$$However, $$\frac{a^2+abc}{a+f(b)}=a+bc-f(b)+\frac{f(b)^2-f(b)bc}{a+f(b)},$$so unless $f(b)^2-f(b)bc=0$, that is, $f(b)=bc$, this is a contradiction for sufficently large $a$. We are done.