Let there be positive integers $a, c$. Positive integer $b$ is a divisor of $ac-1$. For a positive rational number $r$ which is less than $1$, define the set $A(r)$ as follows. $$A(r) = \{m(r-ac)+nab| m, n \in \mathbb{Z} \}$$Find all rational numbers $r$ which makes the minimum positive rational number in $A(r)$ greater than or equal to $\frac{ab}{a+b}$.
Problem
Source: 2018 Korean Mathematical Olympiad Problem 8
Tags: number theory
11.11.2018 11:48
$ \frac{a}{a+b} $ I think.
11.11.2018 11:49
Actually, the question was edited: rkm0959 wrote: Let there be positive integers $a, c$. Positive integer $b$ is a divisor of $ac-1$. For a rational number $r$ which is less than $1$, define the set $A(r)$ as follows. $$A(r) = \{m(r-ac)+nab| m, n \in \mathbb{Z} \}$$Find all rational numbers $r$ which makes the minimum rational number in $A(r)$ are greater or equal than $\frac{ab}{a+b}$.
11.11.2018 11:50
Thanks @lminsl for the edit! I wish I was at KMO this year
11.11.2018 12:13
Sorry i don't understand problem what happen if we take m=n=0
11.11.2018 12:19
kwanglee123456 wrote: Sorry i don't understand problem what happen if we take m=n=0 Actually, the original one was : rkm0959 wrote: Let there be positive integers $a, c$. Positive integer $b$ is a divisor of $ac-1$. For a positive rational number $r$ which is less than $1$, define the set $A(r)$ as follows. $$A(r) = \{m(r-ac)+nab| m, n \in \mathbb{Z} \}$$Find all rational numbers $r$ which makes the minimum positive rational number in $A(r)$ greater than or equal to $\frac{ab}{a+b}$.
11.11.2018 12:29
Darn why am i so clumsy today... fixed.
11.11.2018 12:33
Let $r=\frac{p}{q}$ for coprime positive integers $p<q$. Then $m(r-ac)+nab=m(\frac{p}{q}-ac)+nab)=\frac{m(p-qac)+n(qab)}{q}$. Note that $\{ mx+ny | m, n \in \mathbb{Z} \}=\{ k \gcd(x,y) | k \in \mathbb{Z} \}$, so $$A(r)=\{ \frac{k\cdot \gcd(p-qac,qab)}{q} | k \in \mathbb{Z} \}$$holds. In order to compute the minimum positive element of $A(r)$, we compute $\gcd(p-qac, qab)$. $\gcd(p-qac,q)=\gcd(p,q)=1 \implies \gcd(p-qac,qab)=\gcd(p-qac, ab)$ Also $b | ac-1$, $(b,ac) | (ac-1, ac)=1 \implies (b,ac)=1 \implies (b,a)=1$. Hence $(p-qac, ab)=(p-qac,a) \cdot (p-qac,b)=(p,a) \cdot (q-p,b)$. Now the minimum positive element of $A(r)$ is $\frac{\gcd(p-qac, qab)}{q}=\frac{(p,a) \cdot (q-p,b)}{q}$. Let $p=gu, a=gv$, $q-p=g'u', b=g'v'$ where $g=\gcd(p,a), g'=\gcd(q-p,b)$ and $g,g',u,u',v,v' \ge 1$. Then $\frac{(p,a) \cdot (q-p,b)}{q}=\frac{gg'}{gu+g'u'} \ge \frac{ab}{a+b}=\frac{gg'vv'}{gv+g'v'} \iff gu+g'u' \le \frac{g}{v'}+\frac{g'}{v}$. But $g+g' \le gu+g'u' \le \frac{g}{v'}+\frac{g'}{v} \le g+g'$ gives that $u=u'=v=v'=1$, so $p=g=a$ and $q-p=g'=b$. Hence the only $r$ is $r=\frac{a}{a+b}$.
11.11.2018 12:54
I did exactly the same.