Let $f:\mathbb{N}\rightarrow \mathbb{N}$ be a function such that $f(ab)$ divides $\max \{f(a),b\}$ for any positive integers $a,b$. Must there exist infinitely many positive integers $k$ such that $f(k)=1$?
Problem
Source: CSMO 2019 Grade 10 Problem 3
Tags: function, number theory
30.07.2019 10:54
30.07.2019 10:59
Let's choose some $a$ such that $a>1$ and some prime $p>f(a),a$. First notice that $f(a \cdot a) \mid \max \{f(a),a \} => p>f(a^2)$, and as $f(a^{n-1} \cdot a ) \mid \max \{f(a^{n-1}),a \} => p>f(a^n)$ for all naturals $n$ (by induction). Also notice $f(a^n \cdot p) \mid \max \{f(a^n),p \} => f(a^np) \mid p$- thus $f(a^n p)=1$ or $=p$. Now write $a^n p=ap \cdot a^{n-1} => f(a^n p) \mid \max \{f(ap),a^{n-1} \}$- clearly, for large enough $n$, $a^{n-1} > f(ap) => f(a^np) \mid a^{n-1}$ for large $n$- but we know $(p,a)=1$ as $p>a$, $p$ can't divide $a^{n-1}$- hence for large $n$, $f(a^n p) \neq p => f(a^n p)=1$ for all large $n$, hence infinitely many $n$- Thus we're done. Nice problem.
30.07.2019 11:35
Let $P(a,b)$ denote the assertion. Let $p$ be a prime such that $p\geq f(1)$, then taking $P(1,p)$ we see that $f(p)$ is either $1$ or $p$. Taking $P(p,p),(p^2,p),\dots,P(p^k,p)$ we see that $f(p^i)$ is either $1$ or $p$ for all $i \in \mathbb{N}$. Assume there exists two primes $p,q$, $p>q$ such that $f(p^i)=p, f(q^j)=q$, and $f(p^iq^j)\neq 1, \forall i,j \in \mathbb{N}$, (if these primes wouldn't exist we would already be done.) Let $k$ be the least natural such that $q^k>p$. Take $P(p,q),P(pq,q),\dots P(pq^{k-1},q)$ to see that $f(pq)=f(pq^2)=\dots=f(pq^k)=p$, but taking $P(p,q^k)$ we see that $f(pq^k) \mid q^k$ wich is contradiction. $\blacksquare$
30.07.2019 11:46
Suppose that there exists positive integer $C$ that $f(k)>1$ for all $k>C$. As usual, let $P(a,b)$ denote the statement in the problem. $P(a,p)$ gives us $f(ap)=p$ for all prime $p>\max \{ f(a),C\}$ and positive integer $a$. $P(ap,p)$ gives us $f(ap^2)=p$ for all prime $p>\max \{ f(a),C\}$ and positive integer $a$. Choose prime numbers $p,q$ that $\max \{ f(1),C\} <p<q<p^2$. We get $f(p^2q)=q$ since $q>C$ and $q>f(p^2)=p$. On the other hand, $f(p^2q)\mid \max \{ f(q),p^2\} =p^2$. Contradiction.
30.07.2019 13:06
The answer is yes. If when $k$ is large enough, we have $f(k)>1$. Select $a=1$, $b=p$ is a prime which is large enugh , $p>f(1)$, $f(p)>1$, then we can get $f(p)=p$. It is easy to prove that: for any $n \geq 1$, we have $f(p^n)=p$. Now, we fix two large enough primes $p, q$($p \neq q$), select positive integers $n,m$ which is large enough, such that $p^n>q$, $q^m>p$. Then $f(p^nq^m) \mid p^n$, $f(p^nq^m) \mid q^m$, and $f(p^nq^m) \mid gcd(p^n, q^m)=1$, a contradiction.