First step, observe $d \mid n \implies f(d) \mid f(n).$ Second step, prove $f(n) = a \implies f(a) = n.$ This can be proven by seeing that the minimal $b$ where $f(b)$ is a multiple of $n$ is indeed $a.$ This is because $f(b),(2b), f(3b), \dots$ are multiples of $n,$ so $a$ will have to divide $b.$ But $b < 2a.$ Furthermore, $f(n), f(2n), \dots$ are multiples of $a$ so $f(a)$ divides $n.$ Obviously $f(1)=1,$ so if we have a maximal $C$ where $f(C)=C$ we can derive a contradiction by looking at say, $f(2f(2C)).$ If $f(2C) = kC$ where $k> 2,$ then $f(kC) = 2C.$ So $kC$ cannot be a multiple of $2C$ for obvious reasons. But then $f(2kC)$ is a multiple of $2kC,$ but then that means it must equal $2kC$ exactly. $\blacksquare$

Notice for each $n$ the condition is equivalent to saying that $f(n)$ is the period over $x$ of the boolean condition $n \mid f(x)$. Since $2n \mid f(x) \Longrightarrow n \mid f(x)$, it follows that the period of divisibility by $n$ divides the period of divisibility of $2n$, so $f(n) \mid f(2n)$, so the period of divisibility of $f(n)$ itself, which is $f(f(n))$ divides $2n - n = n$. Thus $f(f(n)) \mid n$ for all $n$. Finally notice if $f(x) = 1$ then $x | f(m)$ for all $m \geq 2$ so if $x > 1$ then $x \mid f(x) = 1$ which is a contradiction. Thus $x = 1$. Hence $f(f(p)) = p$ for any prime $p$. Notice by crt that $f(\text{lcm}(x, y)) = \text{lcm}(f(x), f(y))$, so $f(\text{lcm}(p, f(p))) = \text{lcm}(f(p), f(f(p)) = p)$ so simply choose a larger unused prime $p$ each time and you obtain infinitely many such $n$.

Note that the numbers divisible by $2n$ are periodic with period $2n$ and the ones divisible by $n$ periodic with period $n$ so $f(n) | f(2n)$. For each $n$, there is some $a$ such that $x \equiv a \pmod{f(n)} \iff n | f(x)$. But observe that $n | f(x) | f(2x)$ so $2x \equiv a \pmod{f(n)}$ too, which means $a = 0$ so $$f(n) | x \iff n | f(x)$$But now this is the same as this problem so by the solution set from there, every number of the form $pf(p)$ where $p$ is a prime is a fixed point, so we indeed have $f(n) = n$ for infinitely many $n$. (The other problem in fact classifies all such $f$ too)

Note that the numbers $x$ with $n\mid f(x)$ are periodic with period exactly $f(n)$ and the numbers with $an\mid f(x)$ are periodic with period exactly $f(an)$ for any positive integer $a$. If $an\mid f(x)$, then $n\mid f(x)$, so the period of divisibility by $n$ divides the period of divisibility by $an$. Thus, $f(n)\mid f(an)$ for any positive integers $n$ and $a$. Claim: $f(f(n))\mid n$ for any positive integer $n$. Proof: Note that the numbers $x$ with $f(n)\mid f(x)$ have period exactly $f(f(n))$. However, $x=n$ satisfies $f(n)\mid f(x)$. Also, $x=2n$ satisfies $f(n)\mid f(x)$. So $f(f(n))\mid 2n-n=n$. $\blacksquare$ Claim: $f(f(p))= p$ for any prime $p$. Proof: Note that $f(f(p))\mid p$, so $f(f(p))\in \{1,p\}$ for all primes $p$. If $f(x)=1$ for some $x>1$, then in the problem condition setting $m=x-1$ and $n=x$ gives $x\mid f(x)$ contradiction. So $f(f(p))>1$, which implies $f(f(p))=p$. $\blacksquare$ Now, if $f(p)\mid x$, then $p\mid f(f(p))\mid f(x)$, and if $p\mid x$, then $f(p)\mid f(x)$. Claim: If $n\mid f(n)$ for some positive integer $n$, then $f(n)=n$. Proof: Let $f(n)=cn$. Note that since $f(f(n))\mid n$, we have $f(cn)\mid n\mid f(n)$. However, $f(n)\mid f(cn)$, so $f(n)\mid n$, which implies $c=1$, so $f(n)=n$. $\blacksquare$ However, $f(p)\mid \mathrm{lcm}(p,f(p))$, so $p\mid f(\mathrm{lcm}(p,f(p)))$ and $p\mid \mathrm{lcm}(p,f(p))$, so $f(p)\mid \mathrm{lcm}(p,f(p))$. Thus, $\mathrm{lcm}(p,f(p))\mid f(\mathrm{lcm}(p,f(p)))$, which implies that $f(\mathrm{lcm}(p,f(p)))=\mathrm{lcm}(p,f(p))$. It suffices to show that $\mathrm{lcm}(p,f(p))$ can take on infinitely many values. Suppose not and for some prime $p$, $\mathrm{lcm}(p,f(p))$ is maximal. Set $q$ to be a prime greater than $pf(p)$. Note that $\mathrm{lcm}(q,f(q))>pf(p)\ge \mathrm{lcm}(p,f(p))$, a contradiction.

#4 (Number Theory) For my 500th post, I would like to post my first USA TSTST solved.

Step 0: Trivial Observation

Step 1: a|b then f(a)|f(b)

Step 2: f(1) is 1

Step 3: If f(n) is 1 then n is 1

Step 4: If n|f(m) then f(n)|m

Step 5: If p is prime then f(f(p)) is p

Step 6: lcm(p,f(p))|f(lcm(p,f(p)))

Step 7: f(lcm(p,f(p)))|lcm(p,f(p))

Step 8: Finishing the problem

First Step: $$f(n) \mid f(kn)$$Proof : the problem is saying that the period in which $n \mid f(x)$ is exactly $f(n)$ , now since if $kn \mid f(x)$ then $n \mid f(x)$ the period in which $kn \mid f(x)$ divides the period in which $n \mid f(x)$ , which leads to $f(n) \mid f(kn)$. 2nd Step : $$f(f(n)) \mid n$$Proof : we know that the period in which $f(n) \mid f(x)$ is $f(f(n))$ , but we know that $f(n) \mid f(n)$ and $f(n) \mid f(2n)$ by the first step , So we know that $f(f(n)) \mid 2n - n=n$ 3d Step : $$f(f(p))=p$$for all prime numbers $p$. Proof : By the 2nd Step we know that $f(f(p))$ is either $1$ or $p$ , assume that its $1$ for some prime number $p$ , now set $(m,n) = (f(p)-1,f(p))$ : So we have $f(p) \mid f(f(p))=1$ so $f(p)=1$ and by the same method we have $p \mid f(p)=1$ which is a contradiction. 4th Step : $$f(\text{lcm}(m, n)) = \text{lcm}(f(m), f(n))$$Proof : we know that the period in which $n \mid f(x)$ is $f(n)$ and the period in which $m \mid f(x)$ is $f(m)$ so the period in which $\text{lcm}(m, n) \mid f(x)$ is in one hand $f(\text{lcm}(m, n))$ and in the other hand $\text{lcm}(f(m), f(n))$ therefore $f(\text{lcm}(m, n)) = \text{lcm}(f(m), f(n))$. Now by the 4th step we have : $f(\text{lcm}(f(p), p)) = \text{lcm}(f(f(p)), f(p)) = \text{lcm}(p, f(p))$ , so for every prime number $p$ , $\text{lcm}(p, f(p))$ is a fixed point and this is sequence is obviously unbounded so we are done.

Note that $n\mid f(m)\mid f(2m).$ But also $n\mid f(m)\iff f(n)\mid m-k$ for some $k.$ Since $f(n)\mid 2m-k$ this forces $k=0.$ Hence $n\mid f(m)\iff f(n)\mid m.$ By Indonesia Problem 5 we have $f(n)=n$ for infinitely many $n.$ Q.E.D.

ZETA_in_olympiad wrote: Note that $n\mid f(m)\mid f(2m).$ But also $n\mid f(m)\iff f(n)\mid m-k$ for some $k.$ Since $f(n)\mid 2m-k$ this forces $k=0.$ Hence $n\mid f(m)\iff f(n)\mid m.$ By Indonesia Problem 5 we have $f(n)=n$ for infinitely many $n.$ Q.E.D. Your solution is incomplete and this is the case for all your posted solutions, which makes me feel you took the solution from different parts of other solutions and just posted it without even reading your solution. 1. Why f(m) | f(2m)? 2) why n|f(m) means f(n)|m-k? Please stop the cap.

Wrong, ignore.

Unusual but quite interesting. The problem statement essentially says that there is a function $T$ such that $n \mid f(m) \iff m \equiv T(n) \pmod{f(n)}$ (and $0 \leq T(n)<f(n)$). We first prove the following independent claim. Claim: If $f(a)=f(b)$ then $T(a)=T(b)$. Proof: Some element of $\mathrm{Img}(f)$ is divisible by $ab$, which must be $T(a) \pmod{f(a)}$ and $T(b) \pmod{f(b)}$, hence $T(a)=T(b)$. This then implies that for each positive integer $n$ there are only finitely many $m$ such that $f(m)=n$, else there should be some modulo-$n$ residue over which $f$ has infinitely many divisors (namely all these $m$), which is absurd. Now note that if $m \mid n$, we have $f(m) \mid f(n)$, since otherwise $x \equiv T(m) \pmod{f(m)}$ cannot always follow from $x \equiv T(n) \pmod{f(n)}$ (regardless of $T(m)$ and $T(n)$). Now, $f(n)$ divides both $f(n)$ and $f(2n)$, so $f(f(n)) \mid 2n-n=n$, since we should have $2n \equiv n \pmod{f(f(n))}$. In particular, $f(f(p)) \mid p$, so $f(f(p))=p$ or $f(f(p))=1$ for all $p$ (independently). If there are infinitely many $p$ with $f(f(p))=1$, then either there are finitely many values $f(p)$ can take or infinitely many. In the former case, there exist infinitely many $m$ such that $f(m)=k$ where $k$ equals one of these $f(p)$, which is illegal. In the latter, there exist infinitely many $m$ (equalling one of these $f(p)$) such that $f(m)=1$, which is also illegal.

If there are infinitely many $p$ with $f(f(p))=p$, then note that any $m \mid f(p)$ must have $f(m) \mid p \implies f(m) \in \{1,p\}$. If $f(m)=p$, then $f(f(m))=f(p)$ but then $f(p) \mid m$, which means that $m=f(p)$. On the other hand, $f(p)$ should take on infinitely many values as noted before, so the divisors of $f(p)$ except for $f(p)$ itself, across all $p$, should also take on infinitely many values unless only finitely many primes $p$ have $f(p)$ composite Proof for completion

. If the non-$f(p)$ divisors of $f(p)$ are infinite, we must have infinitely many solutions to $f(n)=1$, because all of these non-$f(p)$ divisors, so finitely many primes $p$ have $f(p)$ composite, hence there are infinitely many prime pairs $(p,q)$ such that $f(p)=q$ and $f(q)=p$. For such pairs, we should have $p \mid pq \implies f(p)=q \mid f(pq)$, and likewise $p \mid f(pq)$, hence $pq \mid f(pq)$. Thus $f(pq) \mid f(f(pq))$, but also $f(f(pq)) \mid pq$, hence we have $$pq \mid f(pq) \mid f(f(pq)) \mid pq \implies pq=f(pq),$$which gives is infinitely many $n$ with $f(n)=n$, as desired.

Found this buried in my bookmarks from a few months ago. Very nice problem that is also not too easy; a few simple observations naturally bring us to the wanted conclusion. Step 1) $a \mid b \rightarrow f(a) \mid f(b)$ pf) if $a \mid b$, we can see that $b \mid f(x)$ implies $a \mid f(x)$. Since the multiples of $b$ in function $f$ have period $f(b)$ and multiples of $a$ in function $f$ have period $f(a)$, it is not too hard to see that this must mean $f(a) \mid f(b)$ Step 2) If $c = ab$, $f(c) = lcm(f(a),f(b))$ pf) multiples of $a$ have a period of $f(a)$, multiples of $b$ have a period of $f(b)$, and a multiple of $c$ must exist in the range of $f$ by the given condition $\rightarrow$ $f(c) = lcm(f(a),f(b))$ by the chinese remainder theorem Step 3) For any positive integers $a$ and $b$, $a \mid f(b) \rightarrow f(a) \mid b$ pf) $a \mid f(b)$ implies $a \mid f(b)$, $f(2b)$, $f(3b)$, $\ldots$ by Observation 1 Thus, the period of multiples of $a$, which is $f(a)$, must divide $b$, indicating that $f(a) \mid b$ Step 4) $f(f(x)) = x$ pf) By plugging in $(a,b) = (f(x),x)$ into Step 3, we get that $f(f(x)) \mid x$ Furthermore, step 3 gives us that in order for $x \mid f(y)$ to be true, $y$ must be a multiple of $f(x)$. This is a much, much more powerful statement than it seems; since the multiples of $x$ have a period of $f(x)$, this gives us the fact that $x \mid f(f(x))$, $f(2f(x))$, $f(3f(x))$, $\ldots$. Thus, $x \mid f(f(x))$, and since we have already established that $f(f(x)) \mid x$ this means that $f(f(x)) = x$. There are two notable corollaries from step 4 that we must note Corollary 1: $f$ is bijective Corollary 2: Step 3 is now an iff statement ($a \mid f(b) \iff f(a) \mid b$) Now we have found all the key information we need to finish this solution It is not too difficult to see that for any prime $p$, $f(p)$ must also be prime. This is because, by corollary 2, $f(a) \mid p \iff a \mid f(p)$, and since $f$ is bijective and $p$ has two factors this means $f(p)$ can also only have two factors. Assume that there are finitely many $n$ satisfying $f(n) = n$. This implies that there exists some $N \in \mathbb{N}$ such that for all $n \geq N$, $f(n) \neq n$. Furthermore, since there are finitely many primes less than $N$ and $f$ is bijective, this means there must exist two primes $p$ and $q$ satisfying $f(p) = q$ and $p, q > N (p \neq q)$ By step 2, this means that $f(pq) = pq$, and since $pq > N$ this causes a contradiction It is probably possible to rewrite this solution to be much shorter and more elegant, but I wanted to show my 'natural' thinking process that led me to the result. Hope its not too hard to understand

Claim: $ff(x)=x$ Claim: If $p$ is a prime, $f(p)=k\neq p$, then $f(kp)=kp$. Proof: $f(p)=k$ and $f(k)=p$. Since $\gcd(p,k)\mid f(kp)$, it suffices to show $\gcd(k, p)=1$. If $p\mid k$, then $k=f(p)\mid f(k)=p$. So $k=p$ contradiction.

Beautiful problem.(Spent 4 hrs on it) IDK why. $Claim:$ If $d \mid n \implies f(d) \mid f(n).$ Proof)Trivial by Congruence $Claim:$ If $f(n) = a \implies f(a) = n.$(This is easy to prove) $Claim:$ If $p$ is a prime, $f(p)=q\neq p$, then $f(qp)=qp$. Proof: Since we already have this $f(p)=q$ and $f(q)=p$. . We just have to prove GCD ($p,q)$ =1 FTSOC assume $p\mid q$, then $q=f(p)\mid f(q)=p$. So $q=p$ contradiction. Its not possible for every $f(p)=1$ . So we are done