Find all function $f:\mathbb{N} \longrightarrow \mathbb{N}$ such that forall positive integers $x$ and $y$, $\frac{f(x+y)-f(x)}{f(y)}$ is again a positive integer not exceeding $2022^{2022}$.
Problem
Source: kjmo 2022 P4
Tags: algebra, functional equation, function
29.10.2022 16:40
Let 2022^2022=C some constant. If $f$ is a solution then so is $Af$ for any constant $A$ so assume $\gcd(f(1), f(2), \dots)=1$. By condition $f(1)$ divides all the numbers $f(x)$ so $f(1)=1$. Let $f(x+1)=f(x) + g(x)$ where g is bounded since $g(x)/f(1) \le C$ now swapping x,y with y,x we see that $f(x) \mid f(x+1) - f(1) = f(x+1) - 1$ meaning $f(x) \mid g(x) -1$ but note that $f$ is strictly increasing and $g$ is bounded so $g$ is eventually $1$. Fix some t ,, for large $n$ $f(n+t)=f(n)+t$ meaning $t/f(t) \in \mathbb Z$ but since $f(1)=1$ and $f$ is increasing by induction $f(n) \ge n$ for all $n$ so $f(t)=t$ for any $t$.
29.10.2022 17:01
PRMOisTheHardestExam wrote: By condition $f(1)$ divides all the numbers $f(x)$ so $f(1)=1$ Wrong, it is divide $f(x+1)-f(x)$. Nevertheless, $f(1) \mid f(x) \; \forall x \in \mathbb N $, means that $f(x)=f(1)g(x)$, no more.
29.10.2022 17:10
Dlavez wrote: PRMOisTheHardestExam wrote: By condition $f(1)$ divides all the numbers $f(x)$ so $f(1)=1$ Wrong, it is divide $f(x+1)-f(x)$. Nevertheless, $f(1) \mid f(x) \; \forall x \in \mathbb N $, means that $f(x)=f(1)g(x)$, no more. They assume that the gcd of $f(1),f(2),\dots$ is $1$ by dividing through, so $f(1)=1$.
29.10.2022 18:44
Sorry for poor explanation... Plug x=1 y=1 to get f(1) divides f(2) Now y=1 means f(1) divides f(x+1) - f(x) which induction gives f(1) divides all values i hope it is clear......
29.10.2022 19:32
PRMOisTheHardestExam wrote: Sorry for poor explanation... Plug x=1 y=1 to get f(1) divides f(2) Now y=1 means f(1) divides f(x+1) - f(x) which induction gives f(1) divides all values i hope it is clear...... Yes, I see it now. I don't know why, but I didn't notice $\gcd \left (f(1), f(2), \dots \right) = 1$. My bad.
02.12.2022 20:35
Claim 1 $a|b \Rightarrow f(a)|f(b)$ If we take $x=y=a$, then $f(a)|f(2a)$. By induction it is clear that if we assume $f(a)|f(ka)$, then putting $x=ka, y=a$ gives us $f(a)|f((k+1)a)$. As written above, we are assuming $ \text{gcd} (f(1), f(2), ...)=1$. Then because of Claim 1, we have $f(1)=1$. $f$ is clearly incereasing and putting $x=1$ gives $f(y+1) \equiv 1 \pmod{f(y)}$. Combining with the fact $f(x+1)-f(x) \leq 2022^{2022}$ gives us that $f(x+1)=f(x)+1$ after some point. Therefore, $f(x)=x+c$ for some constant $c$ and sufficiently large $x$. If $c \neq 0$, taking $x$ and $y$ gives a clear contradiction. $f$ is increasing thus $f(x)=x$ for all $x$. All solutions are in the form of $kx$ where $k$ is a positive integer.
22.08.2023 19:21
yeah it is right