For positive integers $x, y, $ $r_x(y)$ to represent the smallest positive integer $ r $ such that $ r \equiv y(\text{mod x})$ .For any positive integers $a, b, n ,$ Prove that $$\sum_{i=1}^{n} r_b(a i)\leq \frac{n(a+b)}{2}$$
Problem
Source: China Western Mathematical Olympiad 2023 Day 2 P3
Tags: number theory, algebra, China, Inequality, number theory proposed
21.08.2023 10:29
sqing wrote: For positive integers $x, y, $ $r_x(y)$ to represent the smallest positive integer $ r $ such that $x\equiv y(\text{mod x})$ .For any positive integers $a, b, n ,$ Prove that $$\sum_{i=1}^{n} r_b(a i)\leq \frac{n(a+b)}{2}$$ Um, I dont see the notion of $r$ here, do you mean that it is the remainder when $y$ is divided by $x$?
22.08.2023 02:09
The original question stated that $r_{y}(x)$ is the smallest positive integer $r$ such that $r$ is congruent to $x mod y$.
22.08.2023 07:02
eulerleonhardfan wrote: The original question stated that $r_{x}(y)$ is the smallest positive integer $r$ such that $r$ is congruent to $x mod y$. Wait really? Many times the input of the function is the dividend and the subscript is the divisor, can someone please write the full correct problem?
22.08.2023 09:00
I made a typo, please refer to the correct one above.
10.12.2023 18:28
For $k\in\mathbb N$ let $I_k=\{i\in\{1,\ldots,n\}:(k-1)b<ai\le kb\}$. The goal is to prove that the average of $r_b(ai)$ for $i\in\{1,\ldots,n\}$ is at most $(a+b)/2$, so we'll be done if we prove that for every $k\in\mathbb N$ such that $I_k\ne\emptyset$ the average of $r_b(ai)$ for $i\in I_k$ is at most $(a+b)/2$. Such $r_b(ai)$ form an arithmetic sequence, so their average equals the average of the first and last term. Since the first term is $\le a$ and the last term is $\le b$, the result follows. Furthermore we have an equality iff $a\mid b$ and $b\mid an$.