Let $\mathbb N$ denote the set of positive integers. Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that: (i) The greatest common divisor of the sequence $f(1), f(2), \dots$ is $1$. (ii) For all sufficiently large integers $n$, we have $f(n) \neq 1$ and \[ f(a)^n \mid f(a+b)^{a^{n-1}} - f(b)^{a^{n-1}} \] for all positive integers $a$ and $b$. Proposed by Yang Liu
Problem
Source: ELMO 2014 Shortlist N8, by Yang Liu
Tags: function, greatest common divisor, number theory, number theory proposed
26.07.2014 15:02
Trivial stuff first. Take $a=1$ and fix $b$ to get $f(1)^n|f(b+1)-f(b) \forall$ large $n \in \mathbb{N}$. This gives $2$ cases. $f(b+1)-f(b)=0 \forall b \in \mathbb{N}$ or $f(1)=1$. In the first case, $f$ must be constant. Due to the first condition $f$ must be the identity function. Now, we are left to deal with the second case. Let $p$ be a prime and let $k$ be the exponent of $p$ in $f(a)$. Let the minimum number $n$ for which the second condition is satisfied be $N$. Now, consider the exponent of $p$ in $f(a+1)^{a^{n-1}}-1$. Using LTE, we have \[ nk \le v_p(f(a+1)^{a^{n-1}}-1) \] \[= v_p(f(a+1)^{a^{N-1}}-1) + v_p(a^{n-N})= v_p(f(a+1)^{a^{N-1}}-1) + (n-N)v_p(a)\]\[\implies v_p(f(a+1)^{a^{N-1}}-1) - Nv_p(a) \ge n(k - v_p(a)) \forall \text{ large } n \in \mathbb{N}\]Since the LHS is a constant positive quantity, we must have $k \le v_p(a)$. Therefore, whenever $p^k||f(a)$, we also have $p^k|a$. Consequently, $f(a)|a$. Therefore, $f(p)|p$ for all large primes $p$. According to the second criterion, we cannot have $f(p)=1$, so we must have $f(p)=p$. Take $a=p$, $x=f(b+p)^{p^{n-2}}$, $y=f(b)^{p^{n-2}}$. We are given that $p^n|x^p-y^p$. We shall show that $p^{n-1}|x-y$ for some $n \in \mathbb{N}$. Suppose this is not the case. Then, $v_p(x-y) \le n-2$. Therefore, \[ v_p \left( \frac{x^p-y^p}{x-y} \right) \ge 2\]So, $p^2|x^p-y^p \implies p|x^p-y^p \implies p|x-y$. But then, using LTE, \[ v_p \left( \frac{x^p-y^p}{x-y} \right) = v_p(x-y)+v_p(p)-v_p(x-y) =1\]a contradiction. Hence, our claim is true and using descent, we get $p|x-y=f(b+p)-f(b)$. Now suppose that for some $b$, we have $f(b)=1$. Then, $b<p$, for a large prime $p$. Using the last relation, we get $p|f(b+p)-1$. But, $f(b+p)-1 \le b+p-1 <2p-1$, since $f(b+p)|b+p$. But, the only multiple of $p$ between $0$ and $2p$ is $p$. So, $f(b+p)-1=p \implies f(b+p)=p+1|p+b$. Hence, $p+1|b-1$. But, $p+1 > b-1 \ge 0 \implies b-1=0$. Therefore, the only integer $b$ for which $f(b)=1$ is $b=1$. Therefore, $f(p)=p$ for all primes $p$. Using this in the last relation and inducting, we have $p|f(mp) \forall m \in \mathbb{N}$. Now suppose that $f(p^k)=p^l$ for some prime $p$ and $0<l \le k$. Take a very large prime $q$. We know that $q|f(q+p^k)-f(p^k)=f(q+p^k)-p^l$. But, $-q < -p^l < f(q+p^k)-p^l \le q+p^k-p^l < 2q$. Therefore, $f(q+p^k)-p^l =0$ or $q$. In the first case, $p^l|p^k+q \implies p^l|q$, a clear impossibility. In the second case, $p^l+q|p^k+q \implies q+p^l|p^k-p^l$, impossible because $q$ is large, unless $k=l$. Consequently, $f(p^k)=p^k \forall k \in \mathbb{N}$. Substitute $a=p^k$ in the second criterion. Let $x = f(b+p^k)^{p^{k(n-2)}}$ and $y = f(b)^{p^{k(n-2)}}$. We know that $p^{kn}|x^{p^k}-y^{p^k}$. We shall show that $p^{k(n-1)}|x-y$. Suppose that this is not so. Then, $v_p(x-y) \le k(n-1)-1$. Consequently, we have \[v_p \left( \frac{x^{p^k}-y^{p^k}}{x-y} \right) \ge k+1\]This means $p|x^{p^k}-y^{p^k} \implies p|x-y$. Now, using LTE, we have \[v_p \left( \frac{x^{p^k}-y^{p^k}}{x-y} \right)=k\]a contradiction. Therefore, our claim is true. Using descent, we have $p^k|f(b+p^k)-f(b)$. Using the fact that $f(p^k)=p^k$ and inducting, we have $p^k|f(mp^k) \forall m \in \mathbb{N}$. Therefore, whenever $p^k|a$, we also have $p^k|f(a)$. Consequently, $a|f(a) \forall a \in \mathbb{N}$. Combining with our initial inference, we have $f(n)=n \forall n \in \mathbb{N}$. EDIT: And the world thinks its not possible to create a good Number Theory problem
26.07.2014 19:37
dibyo_99 wrote: EDIT: And the world thinks its not possible to create a good Number Theory problem Now that I'm eligible to submit IMO proposals I'll see what I can do about this
14.12.2014 10:06
Indeed a very good problem.In fact one of the most appropriate problems I have seen. Well I would be grateful if anyone points out any flaw in this. By pretty much the same way I obtained $f(a)|a$ for all integers $a$. Now the other part:we know $f(a)|f(a+b)-f(b)$ for integers $a$ and $b$. Now let $f(b)<b$ for some integer $b$.Take a prime $q>b$ and then by dirichlet we can say there are infinitely many k such that $kq+b=p$ is some prime. By taking arbitrarily large primes of this form we can say from $f(a)|a$ and second condition that $f(kq+b)=kq+b$ for sufficienly large suitable $k$. Then $f(kq)|f(kq+b)-f(b)=kq+b-f(b)$.But $f(kq)|kq$ Hhence $f(kq)|b-f(b)$ for all such sufficiently large $k$.Hence we get a finite integer $t$(which is $b-f(b)$) such that there are infinitely many $n$ satisfying $f(n) \le t$.Now use $f(n-1)|f(n)-1$.If $f(n) \neq 1$ then $f(n-1) \le t-1$.Again by iterating like this we get that for all integers $n=kq$,$k$ sufficiently large and such that $kq+b$ is prime,we can guarantee an integer $r$ in the range $[n-t,n]$ such $f(r)=1$.By making $q$ sufficiently large we can make these intervals disjoint ans thus we can find infinitely many integers $r$ such that $f(r)=1$ which is a contradiction. Hence $f(b)=b$ for all $b$.
20.01.2017 01:11
My proof is about half the size of dibyo_99 . Indeed, this is a neat problem! Note that $f(1)^n \mid f(b+1)-f(b)$ for all $b$ so $f(1) \mid \gcd (f(1), f(2), \dots,)=1$ and hence $f(1)=1$. Fix $a$ and let $p \mid f(a)$ be a prime. Note that $p \nmid f(a+1)$ and so let $d$ be the order of $f(a+1)$ mod $p$. By LTE, $$nv_p(f(a)) \le v_p(f(a+1)^d-1)+(n-1)v_p(a) \le (p-1) \log f(a+1)+(n-1) v_p(a).$$An adjustment is applied to the bound for $p=2$. In any case, the result fails to occur if $v_p(f(a))>v_p(a)$ by taking $n$ as sufficiently large. We conclude that $f(a) \mid a$ for all $a \in \mathbb{N}$. So for large primes $p$ we have $f(p)=1$ or $f(p)=p$ wherein only the latter can hold because of the second condition. Observe that $$p^n=f(p)^n \mid f(b+p)^{p^{n-1}}-f(b)^{p^{n-1}},$$for fixed $b \in \mathbb{N}$ and $p$ a large prime. Since $f(b) \le b<p$, it makes perfect sense to talk about the order $l$ of the residue class $\frac{f(b+p)}{f(b)}$ modulo $p$. So $l \mid \gcd (p-1, p^{n-1})=1$ and $l=1$. We conclude that $p \mid f(b+p)-f(b)$ for all $b \in \mathbb{N}$. Repeating the argument shows that $p \mid f(kp+b)-f(b)$ for all positive integers $k$. By Dirichlet's Theorem, there exists a prime of the form $q=kp+b$. It follows that $p \mid f(b)-b$ and so $f(b)=b$ for all natural numbers $b$ which also satisfies all the conditions. P.S. We want more such NT problems in contests!