Another NT FE

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nukelauncher

354 posts

nukelauncher

#1 h Sep 22, 2020, 11:58 PM • 8 Y

Y by TheLiker, itslumi, Kanep, centslordm, megarnie, ImSh95, TheHU-1729, deplasmanyollari

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nukelauncher

354 posts

nukelauncher

#2 h Sep 22, 2020, 11:59 PM • 3 Y

Y by Mathematicsislovely, centslordm, ImSh95

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anyone__42

92 posts

anyone__42

#3 h Sep 23, 2020, 12:01 AM • 11 Y

Y by idkwhatthisis, Kanep, Aryan-23, centslordm, TheMath_boy, uvuvwevwevwe, megarnie, sabkx, Vladimir_Djurica, ImSh95, TensorGuy666

can be done easily using dirichlet's theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dangerousliri

924 posts

dangerousliri

#4 h Sep 23, 2020, 12:09 AM • 4 Y

Y by A-Thought-Of-God, centslordm, sabkx, ImSh95

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.

This post has been edited 1 time. Last edited by dangerousliri, Sep 23, 2020, 12:10 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blacksheep2003

1081 posts

blacksheep2003

#5 h Sep 23, 2020, 12:43 AM • 3 Y

Y by centslordm, sabkx, ImSh95

Solution

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

This post has been edited 4 times. Last edited by blacksheep2003, Sep 23, 2020, 12:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1593 posts

MarkBcc168

#6 h Sep 23, 2020, 1:42 AM • 12 Y

Y by mijail, Imayormaynotknowcalculus, k12byda5h, A-Thought-Of-God, Aryan-23, Kanep, centslordm, tigerzhang, GeoKing, ImSh95, Stuffybear, iamnotgentle

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$ .

This post has been edited 1 time. Last edited by MarkBcc168, Sep 23, 2020, 1:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FAA2533

65 posts

FAA2533

#7 h Sep 23, 2020, 6:45 AM • 3 Y

Y by Aryan-23, centslordm, ImSh95

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.

Solution

This post has been edited 6 times. Last edited by FAA2533, Jul 18, 2022, 2:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ubermensch

820 posts

ubermensch

#9 h Sep 23, 2020, 10:46 AM • 4 Y

Y by ATGY, Illuzion, centslordm, ImSh95

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...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dchenmathcounts

2443 posts

dchenmathcounts

#10 h Sep 23, 2020, 5:14 PM • 3 Y

Y by centslordm, Marie36, ImSh95

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.

This post has been edited 1 time. Last edited by dchenmathcounts, Sep 23, 2020, 5:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ayan_mathematics_king

1527 posts

ayan_mathematics_king

#11 h Sep 24, 2020, 7:49 AM • 6 Y

Y by DapperPeppermint, Mathematicsislovely, amar_04, A-Thought-Of-God, centslordm, ImSh95

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$

This post has been edited 3 times. Last edited by ayan_mathematics_king, Sep 24, 2020, 7:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ProblemSolver2048

104 posts

ProblemSolver2048

#15 h Sep 25, 2020, 8:14 PM • 2 Y

Y by centslordm, ImSh95

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.

This post has been edited 1 time. Last edited by ProblemSolver2048, Dec 14, 2020, 7:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathematicsislovely

245 posts

Mathematicsislovely

#16 h Sep 26, 2020, 10:52 PM • 5 Y

Y by amar_04, centslordm, ImSh95, sabkx, ylmath123

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$ .

This post has been edited 4 times. Last edited by Mathematicsislovely, Sep 26, 2020, 11:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilove_mathematics

188 posts

Ilove_mathematics

#17 h Sep 26, 2020, 11:58 PM • 3 Y

Y by centslordm, odkaI, ImSh95

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.$

This post has been edited 1 time. Last edited by Ilove_mathematics, Sep 27, 2020, 4:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

solver1104

510 posts

solver1104

#18 h Sep 27, 2020, 4:58 AM • 2 Y

Y by centslordm, ImSh95

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.

random stuff

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rcorreaa

238 posts

rcorreaa

#19 h Sep 28, 2020, 4:36 AM • 2 Y

Y by centslordm, ImSh95

Pretty standard NT FE problem... :maybe:

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ATGY

2502 posts

ATGY

#53 h Jan 20, 2024, 7:24 AM

Y by

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.

This post has been edited 2 times. Last edited by ATGY, Jan 20, 2024, 7:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

172 posts

lelouchvigeo

#54 h Jan 20, 2024, 4:35 PM

Y by

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

Sketch

This post has been edited 1 time. Last edited by lelouchvigeo, Jan 20, 2024, 4:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

787 posts

shendrew7

#56 h Mar 18, 2024, 3:48 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SHZhang

109 posts

SHZhang

#57 h Mar 26, 2024, 9:00 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathhotspot

70 posts

mathhotspot

#58 h Mar 31, 2024, 1:56 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pikapika007

294 posts

pikapika007

#59 h Aug 3, 2024, 12:00 AM

Y by

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$ .

This post has been edited 1 time. Last edited by pikapika007, Aug 3, 2024, 12:01 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bin_sherlo

661 posts

bin_sherlo

#60 h Aug 27, 2024, 1:17 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

548 posts

cursed_tangent1434

#61 h Aug 27, 2024, 2:07 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eka01

204 posts

Eka01

#63 h Dec 3, 2024, 3:10 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3426 posts

ihatemath123

#64 h Dec 19, 2024, 2:05 PM

Y by

Should've been a RELMO problem :wow:

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*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4170 posts

john0512

#65 h Dec 23, 2024, 6:17 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

D4N13LCarpenter

13 posts

D4N13LCarpenter

#66 h Feb 3, 2025, 8:44 PM

Y by

We will prove that the only solution is $f(x)=xk$ for every $x$ , which clearly works. Also, suppose that any $a+b>C$ satisfy the condition, instead of $a+b>2019$ . Let $P(a, b)$ denote the given assertion. We begin by proving the following

Claim. We have $n\mid f(n)$ for every $n$
Proof. Notice that this is equivalent to proving that $\nu _{p}(n) \leq \nu_p(f(n))$ for every prime $p$ . To do this, we will proceed by strong induction on $\nu_p(n)$ .

Base Case.

If $\nu_p(n) = 1$ , consider a sufficiently large $k$ such that $a=pk-f(n)$ satisfies $a+n>C$ . $P(a,n)$ now yields $pk\mid nf(pk-f(n))+f(n)^2,$ or equivalently, $p\mid f(n)^2$ , which is what we wanted.

Inductive Step.

Assume $\nu_p(n)\leq \nu_p(f(n))$ if $\nu_p(n)<\alpha$ and, for the sake of contradiction, suppose that $\alpha= \nu_p(n)\geq \nu_p(f(n))=\beta$ . Now consider sufficiently large $\alpha, t$ such that $a=p^{\alpha t} k-f(n)$ satisfies $a+n>C$ and let $\gamma = \nu_p(f(a))$ . $P(a,n)$ then gives $p^{\alpha t} k\mid nf(p^{\alpha t} k-f(n))+f(n)^2.$ Moreover, $\nu_p(nf(p^{\alpha t} k-f(n))+f(n)^2)\geq \min\{\nu_p(nf(p^{\alpha t} k-f(n))), \nu_p(f(n)^2)\}=\min\{\alpha+\gamma, 2\beta\}$ , but note that $\alpha > \beta$ and $\gamma \geq \beta$ as $\gamma \geq \nu_p(f(p^{\alpha t} k-f(n)))=\beta$ , so $\alpha + \gamma > 2\beta$ . To be precise, this implies $2\beta=\nu_p(nf(p^{\alpha t} k-f(n))+f(n)^2)\geq \alpha t$ which is a contradiction as $2\beta$ is fixed and $\alpha t$ can be arbitrarily large.

Now choose sufficiently large $a$ and let $f(a)=ak$ . $P(1,k)$ yields $1+ak\mid 1+af(1),$ or equivalently $1+ak\mid a(f(1)-k)\implies 1+ak\mid f(1)-k.$ However, this is clearly false if $a$ is large enough, unless $f(1)=k$ .

We now have that $f(x)=xf(1)$ if $x>N$ for some $N$ . We aim to prove that $f(x)=xf(1)$ even if $x\leq N$ . Indeed, let $f(a)=at$ for a certain $a<N$ and choose a $b>N$ which is coprime with $a$ . $P(a,b)$ then gives $a+bf(1)\mid a^2+abt=a(a+bt).$ By letting $\gcd(a, k)=d$ , this then rewrites as $\frac{a+bk}{d}\mid a+bt,$ or equivalently $\frac{a+bk}{d}\mid b(t-k).$ However, $\gcd(a+bk, b)=\gcd(a,b)=1$ so $\frac{a+bk}{d}\mid t-k.$ Nevertheless, $a+bk$ is unbounded, so this is only true if $t=k$ , which ends the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

243 posts

pie854

#67 h Feb 13, 2025, 8:08 PM

Y by

By Dirichlet, $1+kf(1)$ can be a prime infinitely often. Since $1+f(k)\mid 1+kf(1)$ it follows that $f(k)=kf(1)$ for infinitely many $k$ . For any fixed $n>0$ , take a large $k$ such that $f(k)=kf(1)$ . We have $n+kf(1) \mid n^2+kf(n) \implies n+kf(1)\mid n^2f(1)-nf(n).$ This forces $f(n)=nf(1)$ .

Conversely, we can check that $f(n)=cn$ works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

andrewthenerd

16 posts

andrewthenerd

#68 h Yesterday at 7:14 AM

Y by

Solution: Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

917 posts

AshAuktober

#69 h Yesterday at 6:17 PM

Y by

The only sols are $f(b) = bf(1) \forall b$ , which works.
Note that by plugging in $b$ such that $bf(1)+1$ is prime (there exist infinitely many by Dirichlet), we have $f(b) = bf(1)$ for all $b \in \mathcal{B}$ , where $\mathcal{B}$ is defined as $b$ such that $bf(1)+1$ is prime.
Now for any $a$ , note that of the values in $\gcd_{b \in \mathcal{B}}(a, b)$ , some value $d$ shows up infinitely many times. Let $\mathcal{D} = \{b \in \mathcal{B} : \gcd(a, b) = d$ .
Then we have $x+yf(1) \mid y(af(1)-f(a))$ where $a = dx, b = dy$ for $b \in \mathcal{D}$ , which implies $x+yf(1) \mid af(1)-f(a)$ . Since $y$ is unbounded, $f(a) = af(1) \forall a$ . $\square$

Z K Y