For positive rational $x$, if $x$ is written in the form $p/q$ with $p, q$ positive relatively prime integers, define $f(x)=p+q$. For example, $f(1)=2$. a) Prove that if $f(x)=f(mx/n)$ for rational $x$ and positive integers $m, n$, then $f(x)$ divides $|m-n|$. b) Let $n$ be a positive integer. If all $x$ which satisfy $f(x)=f(2^nx)$ also satisfy $f(x)=2^n-1$, find all possible values of $n$. Anderson Wang.
Problem
Source: ELMO Shortlist 2012, N2
Tags: function, number theory, relatively prime, number theory proposed
03.08.2012 22:13
Let $x = a/b$ with $\gcd(a,b) = 1$. Then we want $f(ma/nb) = a+b$, WLOG let $\gcd(m,n) = 1$. Then $f(ma/nb) = \frac{ma+nb}{\gcd(ma,nb)}$. Thus $ma + nb = (a+b)\gcd(ma,nb)$. Remark that $\gcd(ma,nb) = \gcd(a,n) \cdot \gcd(b,m)$ because that $\gcd(a,b) = \gcd(m,n) = 1$. Thus $ma + nb = (a+b) \cdot \gcd(a,n) \cdot \gcd(b,m)$ $n(a+b) + (m-n)a = (a+b) \cdot \gcd(a,n) \cdot \gcd(b,m)$ $\implies (a+b)|(m-n)a$. However, $\gcd(a+b,a) = \gcd(b,a) = 1$, thus $(a+b)|(m-n)$ so we're done with part a). Suppose $f(x) = f(2^nx)$ so that $a+b = \frac{2^na + b}{\gcd(2^na, b)}$. Remark that we need $2|b$ or else $f(2^nx) > f(x)$. Let $v_2(b) = k < n$ (if $k \ge n$, then $f(2^nx) < f(x)$ clearly) Then $f(2^nx) = \frac{2^na + b}{2^k} = 2^{n-k}a + \frac{1}{2^k}b = a+b$ $(2^{n}-2^k)a = b(2^k - 1)$ As $\gcd(a,b) = 1$, we have $2^n - 2^k = bz, 2^k - 1 = az$ for some integer $z$. $\implies a+b = \frac{2^n-1}{z}$. Thus the condition holds iff we cannot find $k$ such that $\gcd(2^{n-k}-1, 2^k-1) > 1$. But $\gcd(2^{n-k}-1, 2^k-1) = 2^{\gcd(n-k,k)}-1 = 2^{\gcd(n,k)} - 1$. Thus we want $\gcd(n,k) = 1$ for $1 \le k < n$. This holds exactly when $n$ is prime, and thus we are done.
04.08.2012 21:18
for the 1st part--- let $x=\frac{p}{q}$ , where $p,q \in N$ and $(p,q)=1$ now let's first start with (m,n)=1. then $mx/n=mp/nq$ .let $gcd(mp,nq)=r$ then $f(mx/n)=f(mp/nq)=f([mp/r]/[nq/r])=[mp+nq]/r$ , because $g(mp/r,nq/r)=1$ , $mp/r ,nq/r \in N$ then $r(p+q)=mp+nq=mp+mq+nq-mq=m(p+q)+q(n-m)$, so p+q divides q(n-m). now , as (p,q)=1 , so (p+q,q)=1 , so , p+q divides $(n-m)$. now we can easily generalize it for (m,n)=g [just take m=ga , n=gb , a,b >0 with (a,b)=1 , then $mx/n=ax/b$ , with (a,b)=1 . so , $f(x)=f(ax/b)$. now by the given argument , f(x) divides [a-b] , so , f(x) divides g(a-b)=m-n. hence done!