Let $\mathbb{Q}$ be the set of rational numbers, $\mathbb{Z}$ be the set of integers. On the coordinate plane, given positive integer $m$, define $$A_m = \left\{ (x,y)\mid x,y\in\mathbb{Q}, xy\neq 0, \frac{xy}{m}\in \mathbb{Z}\right\}.$$For segment $MN$, define $f_m(MN)$ as the number of points on segment $MN$ belonging to set $A_m$. Find the smallest real number $\lambda$, such that for any line $l$ on the coordinate plane, there exists a constant $\beta (l)$ related to $l$, satisfying: for any two points $M,N$ on $l$, $$f_{2016}(MN)\le \lambda f_{2015}(MN)+\beta (l)$$
Problem
Source: CGMO 2016 Q8
Tags: number theory, analytic geometry, number theory unsolved
05.10.2016 07:05
it is too hard,any one can solve it?
16.10.2016 03:35
any solutions?
29.10.2016 19:09
anyone try to solve it?
21.01.2017 16:57
how to solve it?I know the answer is (2015/6)
28.01.2017 14:19
........
28.01.2017 15:27
Come on somebody answer this nice and tough question !
31.01.2017 13:34
kk108 wrote: Come on somebody answer this nice and tough question ! thank you very much!
06.02.2017 10:16
.........
28.07.2017 20:09
Claim: $\min \{\lambda\} = \frac{2015}{6}$. Proof: We first show that $\lambda = \frac{2015}{6}$ satisfies the problem statement. Define rational points as the points on the plane with both rational horizontal and vertical coordinates. First consider the special cases: $\text{(i)}$ If there is at most one rational point on the line $l$, then it suffices to let $\beta(l) = 1$; $\text{(ii)}$ If $l$ is a coordinate axis, then there is not any point from the set $A_m$ on it, and it suffices to let $\beta(l) = 0$; $\text{(iii)}$ If $l$ is parallel to a coordinate axis, by symmetry, let $l$ be $x = r (r \in \mathbb{R_+})$. When $r \notin \mathbb{Q}$, it becomes case $\text{(i)}$; When $r \in \mathbb{Q}$, for any $M(r, m)$, $N(r, n) (m < n)$, $f_{2016}(MN)$ is the number of multipliers of $2016$ in the interval $[mr, nr]$, $f_{2015}(MN)$ is the number of multipliers of $2015$ in the interval $[mr, nr]$. Since there must always be a multiplier of $2015$ between two consecutive multipliers of $2016$, $$f_{2016}(MN) \le f_{2015}(MN) + 1 \le \lambda f_{2015}(MN) + 1,$$then it suffices to choose $\beta(l) = 1$. Now consider the general cases: Let $l$ not be parallel to or on the coordinate axes and let there be at least two rational points on it. We can then let $l$ be $ax + by = c (a, b, c \in \mathbb{Q}, ab \neq 0)$. WLOG, assume that $a, b, c \in \mathbb{Z}, ab \neq 0$. Then by symmetry, we can let $a, b \in \mathbb{Z_+}$. For any positive integer $m$, consider the points $(x, y) \in A_m$ on $l$. Since $ax + by = c$, $ax \cdot by = ab \cdot xy$ are both multipliers of $abm$, and $ax, by \in \mathbb{Q}$, it follows that $ax, by \in \mathbb{Z}$. Therefore the point $(x, y)$ must satisfy that $ax, by$ are integers with their sum being equal to $c$ and their product being a multiplier of $abm$. So adding $2015 \times 2016 ab$ to or subtracting $2015 \times 2016 ab$ from $ax, by$ will not change whether $(x, y) \in A_m$ or not. (i.e. $(x,y)$ and $(x + k 2015 \times 2016b, y - k 2015 \times 2016a) (k \in \mathbb{Z})$ share the common property with respect to $A_m$.) Therefore we can let $\beta(l)$ be the number of points in the set $A_{2016}$ in the period $0 \le x < 2015 \times 2016b$, and it suffices to consider the number of points in the sets $A_{2015}, A_{2016}$ in a period ($0 \le x < 2015 \times 2016b$). Now let $$g_{2015}(l) = \left| \{ u | 0 \le u < 2015 \times 2016 ab, u \in \mathbb{Z}, 2015ab | u(c - u)\} \right|,$$$$g_{2016}(l) = \left| \{ u | 0 \le u < 2015 \times 2016 ab, u \in \mathbb Z, 2016ab | u(c - u)\} \right|.$$ Here we consider $u$ as $ax$, then there are $g_i(l)$ points in the set $A_i (i=2015, 2016)$ in a period. Now if suffices to show that $$g_{2016}(l) \le \frac{2015}{6} g_{2015}(l).$$ Let $2015 \times 2016 ab = 2^{\alpha_1} \cdot 3^{\alpha_2} \cdot 7^{\alpha_3} \cdot 5^{\alpha_4} \cdot 13^{\alpha_5} \cdot 31^{\alpha_6} \cdot p_7^{\alpha_7} \cdots p_s^{\alpha_s}$. For any $p_i^k | 2015 \times 2016 ab$, define $h(p_i^k)$ as the number of positive integer $u$ among $0, 1, 2, \dots, p_i^{\alpha_i} - 1$ satisfying $p_i^k | u(c - u)$. Then by Chinese Remainder Theorem, $$g_{2015}(l) = h(2^{\alpha_1 - 5}) h(3^{\alpha_2 - 2}) h(7^{\alpha_3 - 1}) h(5^{\alpha_4}) h(13^{\alpha_5}) h(31^{\alpha_6}) \prod\limits_{i=7}^s h(p_i^{\alpha_i}),$$$$g_{2016}(l) = h(2^{\alpha_1}) h(3^{\alpha_2}) h(7^{\alpha_3}) h(5^{\alpha_4 - 1}) h(13^{\alpha_5 - 1}) h(31^{\alpha_6 - 1}) \prod\limits_{i=7}^s h(p_i^{\alpha_i}),$$where $h(x) \neq 0$. Therefore it suffices to show that $$\frac{h(2^{\alpha_1})h(3^{\alpha_2})h(7^{\alpha_3})h(5^{\alpha_4 - 1})h(13^{\alpha_5 - 1})h(31^{\alpha_6 - 1})}{h(2^{\alpha_1 - 5})h(3^{\alpha_2 - 2})h(7^{\alpha_3 - 1})h(5^{\alpha_4})h(13^{\alpha_5})h(31^{\alpha_6})} \le \frac{2015}{6}. \ (*)$$ Now evaluate the value of $h(p_i^k)$ for each $p_i^k | 2015 \times 2016 ab$. Let $p_i^d \| c$, and let $\lceil x \rceil$ denote the ceiling of $x$. If $k \le 2d$, $p_i^{\lceil \frac{k}{2} \rceil}$ must divide $u$, then $h(p_i^k) = p_i^{\alpha_i - \lceil \frac{k}{2} \rceil}$; If $k > 2d$, $p_i^{k-d}$ must divide either $u$ or $c - u$, then $h(p_i^k) = 2p_i^{\alpha_i - k + d}$. Thus, $1, \frac{p}{2}, p$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+1})}$; $\frac{p}{2}, p, \frac{p^2}{2}, p^2$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+2})}$; and $p^2, \frac{p^3}{2}, p^3, \frac{p^4}{2}, \frac{p^5}{2}, p^5$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+5})}$. Therefore, \begin{align*} \frac{h(2^{\alpha_1})h(3^{\alpha_2})h(7^{\alpha_3})h(5^{\alpha_4 - 1})h(13^{\alpha_5 - 1})h(31^{\alpha_6 - 1})}{h(2^{\alpha_1 - 5})h(3^{\alpha_2 - 2})h(7^{\alpha_3 - 1})h(5^{\alpha_4})h(13^{\alpha_5})h(31^{\alpha_6})} & \\ \le \frac{1}{4} \times \frac{2}{3} \times 1 \times 5 \times 13 \times 31 = \frac{2015}{6}. \end{align*} Now we show that $\lambda = \frac{2015}{6}$ is the minimal value; and for that, we just need the equality case in $(*)$ to be achieved. Let $ab = 21, c= 4 \times 3 \times 7 \times 5 \times 13 \times 31 = 84 \times 2015$, and let $l$ be $x + 21y = 84 \times 2015$, and the equality case is achieved. That completes the proof.
28.07.2017 20:25
The question (or even the CGMO itself) is pretty bashy and requires a lot of case work. We transform the question to studying the roots of $x (x + t) \equiv 0 \pmod{p^l}$ then do case work on every prime divisor.
01.08.2017 05:40
CQYIMO42 wrote: Claim: $\min \{\lambda\} = \frac{2015}{6}$. Proof: We first show that $\lambda = \frac{2015}{6}$ satisfies the problem statement. Define rational points as the points on the plane with both rational horizontal and vertical coordinates. First consider the special cases: $\text{(i)}$ If there is at most one rational point on the line $l$, then it suffices to let $\beta(l) = 1$; $\text{(ii)}$ If $l$ is a coordinate axis, then there is not any point from the set $A_m$ on it, and it suffices to let $\beta(l) = 0$; $\text{(iii)}$ If $l$ is parallel to a coordinate axis, by symmetry, let $l$ be $x = r (r \in \mathbb{R_+})$. When $r \notin \mathbb{Q}$, it becomes case $\text{(i)}$; When $r \in \mathbb{Q}$, for any $M(r, m)$, $N(r, n) (m < n)$, $f_{2016}(MN)$ is the number of multipliers of $2016$ in the interval $[mr, nr]$, $f_{2015}(MN)$ is the number of multipliers of $2015$ in the interval $[mr, nr]$. Since there must always be a multiplier of $2015$ between two consecutive multipliers of $2016$, $$f_{2016}(MN) \le f_{2015}(MN) + 1 \le \lambda f_{2015}(MN) + 1,$$then it suffices to choose $\beta(l) = 1$. Now consider the general cases: Let $l$ not be parallel to or on the coordinate axes and let there be at least two rational points on it. We can then let $l$ be $ax + by = c (a, b, c \in \mathbb{Q}, ab \neq 0)$. WLOG, assume that $a, b, c \in \mathbb{Z}, ab \neq 0$. Then by symmetry, we can let $a, b \in \mathbb{Z_+}$. For any positive integer $m$, consider the points $(x, y) \in A_m$ on $l$. Since $ax + by = c$, $ax \cdot by = ab \cdot xy$ are both multipliers of $abm$, and $ax, by \in \mathbb{Q}$, it follows that $ax, by \in \mathbb{Z}$. Therefore the point $(x, y)$ must satisfy that $ax, by$ are integers with their sum being equal to $c$ and their product being a multiplier of $abm$. So adding $2015 \times 2016 ab$ to or subtracting $2015 \times 2016 ab$ from $ax, by$ will not change whether $(x, y) \in A_m$ or not. (i.e. $(x,y)$ and $(x + k 2015 \times 2016b, y - k 2015 \times 2016a) (k \in \mathbb{Z})$ share the common property with respect to $A_m$.) Therefore we can let $\beta(l)$ be the number of points in the set $A_{2016}$ in the period $0 \le x < 2015 \times 2016b$, and it suffices to consider the number of points in the sets $A_{2015}, A_{2016}$ in a period ($0 \le x < 2015 \times 2016b$). Now let $$g_{2015}(l) = \left| \{ u | 0 \le u < 2015 \times 2016 ab, u \in \mathbb{Z}, 2015ab | u(c - u)\} \right|,$$$$g_{2016}(l) = \left| \{ u | 0 \le u < 2015 \times 2016 ab, u \in \mathbb Z, 2016ab | u(c - u)\} \right|.$$ Here we consider $u$ as $ax$, then there are $g_i(l)$ points in the set $A_i (i=2015, 2016)$ in a period. Now if suffices to show that $$g_{2016}(l) \le \frac{2015}{6} g_{2015}(l).$$ Let $2015 \times 2016 ab = 2^{\alpha_1} \cdot 3^{\alpha_2} \cdot 7^{\alpha_3} \cdot 5^{\alpha_4} \cdot 13^{\alpha_5} \cdot 31^{\alpha_6} \cdot p_7^{\alpha_7} \cdots p_s^{\alpha_s}$. For any $p_i^k | 2015 \times 2016 ab$, define $h(p_i^k)$ as the number of positive integer $u$ among $0, 1, 2, \dots, p_i^{\alpha_i} - 1$ satisfying $p_i^k | u(c - u)$. Then by Chinese Remainder Theorem, $$g_{2015}(l) = h(2^{\alpha_1 - 5}) h(3^{\alpha_2 - 2}) h(7^{\alpha_3 - 1}) h(5^{\alpha_4}) h(13^{\alpha_5}) h(31^{\alpha_6}) \prod\limits_{i=7}^s h(p_i^{\alpha_i}),$$$$g_{2016}(l) = h(2^{\alpha_1}) h(3^{\alpha_2}) h(7^{\alpha_3}) h(5^{\alpha_4 - 1}) h(13^{\alpha_5 - 1}) h(31^{\alpha_6 - 1}) \prod\limits_{i=7}^s h(p_i^{\alpha_i}),$$where $h(x) \neq 0$. Therefore it suffices to show that $$\frac{h(2^{\alpha_1})h(3^{\alpha_2})h(7^{\alpha_3})h(5^{\alpha_4 - 1})h(13^{\alpha_5 - 1})h(31^{\alpha_6 - 1})}{h(2^{\alpha_1 - 5})h(3^{\alpha_2 - 2})h(7^{\alpha_3 - 1})h(5^{\alpha_4})h(13^{\alpha_5})h(31^{\alpha_6})} \le \frac{2015}{6}. \ (*)$$ Now evaluate the value of $h(p_i^k)$ for each $p_i^k | 2015 \times 2016 ab$. Let $p_i^d \| c$, and let $\lceil x \rceil$ denote the ceiling of $x$. If $k \le 2d$, $p_i^{\lceil \frac{k}{2} \rceil}$ must divide $u$, then $h(p_i^k) = p_i^{\alpha_i - \lceil \frac{k}{2} \rceil}$; If $k > 2d$, $p_i^{k-d}$ must divide either $u$ or $c - u$, then $h(p_i^k) = 2p_i^{\alpha_i - k + d}$. Thus, $1, \frac{p}{2}, p$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+1})}$; $\frac{p}{2}, p, \frac{p^2}{2}, p^2$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+2})}$; and $p^2, \frac{p^3}{2}, p^3, \frac{p^4}{2}, \frac{p^5}{2}, p^5$ are the only possible values of $\frac{h(p_i^k)}{h(p_i^{k+5})}$. Therefore, \begin{align*} \frac{h(2^{\alpha_1})h(3^{\alpha_2})h(7^{\alpha_3})h(5^{\alpha_4 - 1})h(13^{\alpha_5 - 1})h(31^{\alpha_6 - 1})}{h(2^{\alpha_1 - 5})h(3^{\alpha_2 - 2})h(7^{\alpha_3 - 1})h(5^{\alpha_4})h(13^{\alpha_5})h(31^{\alpha_6})} & \\ \le \frac{1}{4} \times \frac{2}{3} \times 1 \times 5 \times 13 \times 31 = \frac{2015}{6}. \end{align*} Now we show that $\lambda = \frac{2015}{6}$ is the minimal value; and for that, we just need the equality case in $(*)$ to be achieved. Let $ab = 21, c= 4 \times 3 \times 7 \times 5 \times 13 \times 31 = 84 \times 2015$, and let $l$ be $x + 21y = 84 \times 2015$, and the equality case is achieved. That completes the proof. this is an offical solution,but thank you!
19.01.2020 05:14
I claim that the answer is $\frac{2015}{6}$. We will only consider lines which pass through at least $2$ rational points. All such lines can be written in the form $Ax+By=C$ where $A,B,C\in\mathbb{Z}$. Now, given such a line, if we have a point $(x,y)$ on it such that $xy=2015m$, then $$Ax^2-Cx+2015Bm=0\implies x=\frac{C\pm\sqrt{C^2-8060ABm}}{2A}$$Of course, we need $C^2-8060ABm=M^2$ for such $M$. The set of all such $M$ are those which satisfy the modular equivalence $$C^2\equiv M^2\pmod{8060AB}$$In particular, $M^2\equiv C^2\pmod{8060AB}\iff x=\frac{C+M}{2A}$ produces a point in $A_{2015}$. Similarly, we get that $N^2\equiv C^2\pmod{8064AB}\iff x=\frac{C+N}{2A}$ produces a point in $A_{2016}$. If we define $g(x)$ to be the number of solutions to $M^2\equiv C^2\pmod x$, then the ratio $\frac{f_{2016}(PQ)}{f_{2015}(PQ)}$ over segments $\overline{PQ}\in Ax+By=C$ is always $\frac{g(8064AB)}{g(8060AB)}\cdot\frac{2015}{2016}+o(1)\implies \lambda\ge \frac{g(8064AB)}{g(8060AB)}$. In fact, it is not hard to see that we should have $\lambda=\max\left(\frac{g(8064AB)}{g(8060AB)}\right)$ over all triples $(A,B,C)$, so it remains to maximize $\frac{g(8064AB)}{g(8060AB)}$. Of course, by CRT, we have that $g(p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k})=g(p_1^{\alpha_1})\cdot\ldots\cdot g(p_k^{\alpha_k})$, so we maximize $\frac{g(p^{\nu_p(8064AB)})}{g(p^{\nu_p(8060AB)})}$ independently over primes $p$ such that $\nu_p(8064AB)\neq\nu_p(8060AB)$. This means we only need to consider $p|\text{lcm}(8064,8060)$. Consider $g(p^a)$ for some prime $p$. Also, suppose that $\nu_p(C)=k$. We need that $x^2\equiv C^2\pmod{p^a}$. If $k\ge a/2$, then $g(p^a)=p^{\lfloor a/2\rfloor}$, since we need $p^a|x^2\implies p^{\lceil a/2\rceil}|x$. If $k<a/2$, then we need $p^{2k}|x^2$, so define $x'=x/p^k$. We have $x'^2\equiv (C/p^k)^2\pmod{p^{a-2k}}$. For odd $p$, this means that $x\equiv\pm C/p^k \pmod{p^{a-2k}}$, so $x$ can have $2$ possible residues mod $p^{a-2k}$, so $2p^k$ residues mod $p^a\implies g(p^a)=2p^k$. So, for odd primes, if $a>b$, we have $\frac{g(p^a)}{g(p^b)}=1$ if $k<b/2$, $\frac{g(p^a)}{g(p^b)}=2p^{k-\lfloor b/2\rfloor}$ if $b/2\le k<a/2$, and $\frac{g(p^a)}{g(p^b)}=p^{\lfloor a/2\rfloor -\lfloor b/2\rfloor}$ if $k\ge a/2$. For $p=2$, we have a similar result. $x^2\equiv (C/2^k)^2 \pmod {2^{a-2k}}$ has $1$ solution if $a-2k=1$, it has $2$ solutions if $a-2k=2$, and it has $4$ if $a-2k>2$. So, $\frac{g(p^a)}{g(p^b)}\le 4$ when $k<b/2$, $\frac{g(p^a)}{g(p^b)}\le 4p^{k-\lfloor b/2\rfloor}$ when $b/2\le k<a/2$, and $\frac{g(p^a)}{g(p^b)}=p^{\lfloor a/2\rfloor-\lfloor b/2\rfloor}$ if $k\ge a/2$. However, for the 2nd case, note that $\frac{g(p^a)}{g(p^b)}=4p^{k-\lfloor b/2\rfloor}$ only when $k<a/2-1$, and $\frac{g(p^a)}{g(p^b)}=2p^{k-\lfloor b/2\rfloor}$ only when $k=a/2-1$. So, our answer is actually capped at $2^{\lceil a/2\rceil -\lfloor b/2\rfloor}$ Now we put this all together, starting with $p=2$. Note that $\nu_2(8064AB)-\nu_2(8060AB)=5$. For each of the three cases, the maximum value of $\frac{g(p^{\nu_p(8064AB)})}{ g(p^{\nu_p(8060AB)})}$ is $4,2^3,2^3$. So, $p=2$ contributes at most a factor of $8$ to the ratio, which is achievable when $\nu_2(AB)=1$, $\nu_2(C)=2020$. For $p=3$, we have that $\nu_3(8064AB)-\nu_3(8060AB)=2$. Of course, our maximum occurs in the second case, which yields $6$ when $\nu_3(AB)=\nu_3(C)=1$. For $p=7$, we have that $\nu_7(8064AB)-\nu_7(8060AB)=1$, so our maximum occurs in the third case, where we get $\frac{g(7^{\nu_7(8064AB)})}{g(7^{\nu_7(8060AB)})}=7$. This is achievable with $\nu_7(AB)=1$, $\nu_7(C)=420$. Finally, for $p=5,13,31$, note that we have $\nu_p(8064AB)=\nu_p(8060AB)-1$, so the quotient is always at most $1$. However, this is achieivable with $\nu_p(AB)=0$, $\nu_p(C)=65537$. So, in total, we end up with $\frac{g(8064AB)}{g(8060AB)}\le 8*7*6=336$, which is achievable by using CRT to combine all of the aforementioned equality cases. Hence, we get that $\lambda=\frac{2015}{2016}\cdot 336=\frac{2015}{6}$, as desired. Note that we haven't yet considered the case where $AB=0$. Suppose that we have $l$ is $y=C$ for some rational $C$. Then, the $x$ coordinates of points in $A_m$ are just $\frac{mk}{C}$ for any integer $k$, which of course makes $\lambda=\frac{2015}{2016}<\frac{2015}{6}$. Hence, our answer is still correct.
19.01.2020 06:23
Solved with Th3Numb3rThr33. The answer is $2015/6$. It is easy to take care of horizontal and vertical lines, so we ignore them. Let $\ell$ be the line $ax+by=c$, where $a$, $b$, $c$ are integers. Then the product $ax\cdot by$ is an integer by definition of $A_m$, and $ax+by=c$ is an integer. It follows that $u=ax$ and $v=by$ are both integers. Let $g_m(n)$ be the number of integers in $(0,n]$ such that $mab\mid u(c-u)$. If $M$ has $x$-coordinate $an_1$ and $N$ has $x$-coordinate $an_2$, $f_m(MN)=g_m(n_2)-g_m(n_1)+O(1)$, so we just want to maximize \[\lambda:=\lim_{n\to\infty}\frac{g_{2016}(n)}{g_{2015}(n)}.\]The pith of this computation is this lemma: Lemma (Looking at each prime divisor). If $\nu_p(c)=k$, then the number of residues $u$ modulo $p^e$ with $p^e\mid u(c-u)$ is $2p^k$ when $2k<e$, and $p^{\lfloor e/2\rfloor}$ when $2k\ge e$. Proof of lemma for $\color{red}2k<e$. Let $c=p^k\cdot t$, where $p\nmid t$. Then I claim all such $u$ are either $0\pmod{p^{e-k}}$ or $c\pmod{p^{e-k}}$. It is obvious that these $u$ work, since both are divisible by $p^k$ and at least one is divisible by $p^{e-k}$. If $\nu_p(u)\ne k$, then $e-\nu_p(u)\le\nu_p(c-u)=\min(k,\nu_p(u))$. If $k\le\nu_p(u)$, then $\nu_p(u)\ge e-k$, as desired. Otherwise $\nu_p(u)\le k$ and $\nu_p(u)\ge e/2>k$, contradiction. Now we only need to consider the case $\nu_p(u)=k$. Here, we need $\nu_p(c-u)\ge e-k$, so $u\equiv c\pmod{p^{e-k}}$, as claimed. It follows that there are $2\cdot p^e/p^{e-k}=2p^k$ such $u$. $\blacksquare$ Proof of lemma for $\color{red}2k\ge e$. Let $c=p^k\cdot t$, where $p\nmid t$. Then I claim all such $u$ are $0\pmod{p^{\lceil e/2\rceil}}$. Since for such $u$, $k\ge\lceil e/2\rceil$, it is clear $p^e\mid u(c-u)$. If $\nu_p(u)\ne k$, then $e-\nu_p(u)\le\nu_p(c-u)=\min(k,\nu_p(u))$. If $\nu_p(u)\le k$, then $\nu_p(u)\ge e/2$ (and thus $\nu_p(u)\ge\lceil e/2\rceil$), as desired. Otherwise $\nu_p(u)\ge k\ge e/2$ already. Finally comes the case $\nu_p(u)=k$, which works since $k\ge e/2$. It follows that there are $p^e/p^{\lceil e/2\rceil}=p^{\lfloor e/2\rfloor}$ such $u$. $\blacksquare$ Now recall $2016=2^5\cdot3^2\cdot7$ and $2015=5\cdot13\cdot31$. If $ab$ has a prime factor $p$ not among $\{2,3,7,5,13,31\}$, then $g_{2016}(n)$ and $g_{2015}(n)$ increase by the same factor (either $2p^k$ or $p^{\lfloor\nu_p(ab)/2\rfloor}$), so we may ignore them. Assume $ab=2^{e_1}3^{e_2}7^{e_3}\cdot5^{f_1}13^{f_2}31^{f_3}$. Let $w_m(n)$ be the number of residues modulo $n$ with $n\mid u(c-u)$. It is easy to see that \[\lambda=\frac{w_{2016}(n)/2016}{w_{2015}(n)/2015}=\frac{w_{2016}(n)}{w_{2015}(n)}\cdot\frac{2015}{2016}.\]We will compute $w_m(n)$ via Chinese Remainder theorem by looking at each prime factor independently. Let $h(p)$ be the factor that selecting the exponent of the prime $p$ in $ab$ contributes to $w_{2016}(n)/w_{2015}(n)$. Thus $\lambda=h(2)h(3)h(7)h(5)h(11)h(13)$. Claim 1. We have $h(2)\le8$, $h(3)\le6$, $h(7)\le7$, and equality holds. Proof. Let $e=\nu_p(ab)$. Note that $h(p)=p$ is possible, since we can take $e>2k$. If we choose $e$ such that $e\le 2k<e+\nu_p(2016)$, then \[h(p)=\frac{2p^k}{p^{\lfloor e/2\rfloor}}\le2p^{\left\lfloor\tfrac{e+\nu_p(2016)}2\right\rfloor-\left\lfloor\tfrac e2\right\rfloor},\]which equals $8$ and $6$ for $p=2$ and $p=3$ respectively, with equality easily achievable. For $p=7$, we must have $e=2k$, so $e$ is even and $h(7)=2$. Finally if $e>2k$, then $h(p)=2p^k/(2p^k)=1$, so the maximum possible $h(p)$ are $8$, $6$, $7$ for $p=2$, $p=3$, $p=7$, respectively. $\blacksquare$ Claim 2. We have $h(5)\le1$, $h(13)\le1$, $h(31)\le1$, and equality holds. Proof. For $p\in\{5,13,31\}$, by the same argument as Claim 1, $1/p$ and $1$ are achievable. Otherwise $e\le2k<e+\nu_p(2015)$, and \[h(p)=\frac{p^{\lfloor e/2\rfloor}}{2p^k}<1,\]so the maximum possible value of $h(p)$ is $1$. $\blacksquare$ Finally, by Chinese Remainder theorem \[\lambda\le8\cdot6\cdot7\cdot\frac{2015}{2016}=\frac{2015}6.\]To achieve equality, take $a=1$, $b=21$, $c=84\cdot2015$. It is easy to see that all our bounds are now equalities, so we are done.