$g$ and $n$ are natural numbers such that $gcd(g^2-g,n)=1$ and $A=\{g^i|i \in \mathbb N\}$ and $B=\{x\equiv (n)|x\in A\}$(by $x\equiv (n)$ we mean a number from the set $\{0,1,...,n-1\}$ which is congruent with $x$ modulo $n$). if for $0\le i\le g-1$ $a_i=|[\frac{ni}{g},\frac{n(i+1)}{g})\cap B|$ prove that $g-1|\sum_{i=0}^{g-1}ia_i$.( the symbol $|$ $|$ means the number of elements of the set)($\frac{100}{6}$ points) the exam time was 4 hours
Problem
Source:
Tags: number theory proposed, number theory, Hi
05.07.2014 23:50
still no solution?!
30.08.2020 04:59
Solution from Twitch Solves ISL: Let $e > 0$ denote the order of $g$ modulo $n$. Also, by $a \% n$ we mean the remainder when $a$ is divided by $n$. The main observation is that an element $b \in B$ will fall in the $\left\lfloor \frac{g \cdot b}{n} \right\rfloor$'th interval, and contribute that amount to the sum given in the problem. This gives the first equality in the following calculation: \begin{align*} \sum i a_i &= \sum_{b \in B} \left\lfloor \frac{g \cdot b}{n} \right\rfloor \\ &= \sum_{k=0}^{e-1} \left\lfloor \frac{g \cdot (g^k \% n)}{n} \right\rfloor \\ &= \sum_{k=0}^{e-1} \frac{g \cdot (g^k \% n) - \left( g \cdot (g^k \% n) \right) \% n}{n} \ \end{align*}We may now take modulo $g-1$, noting that $g \equiv 1 \pmod{g-1}$ and $n$ is relatively prime to $g-1$, hence \begin{align*} \sum i a_i &= \sum_{k=0}^{e-1} \frac{(g^k \% n) - \left( g^{k+1} \% n \right)}{n} \pmod{g-1} \\ &= 0 \end{align*}as desired, with the sum telescoping.
29.12.2023 00:02
The idea is to do a kind of double counting: every residue $g^k \bmod n$ contributes a weight of $$w_k = \left \lfloor \frac{\left(g^k - n\left \lfloor \frac{g^k}n\right \rfloor\right)g}n \right \rfloor.$$(This corresponds to the contribution to the $ia_i$-term in the interval which $g^k$ is present.) Let $r$ be the order of $g$ modulo $n$. Hence the sum we are looking for is \begin{align*} S& = \sum_{k=1}^r \left \lfloor \frac{g^{k+1}}n \right \rfloor - g \left \lfloor \frac{g^k}n \right \rfloor\\ &= \frac 1n \sum_{k=1}^r (g^{k+1} - g^{k+1} \bmod n) - (g^{k+1} - g \cdot g^k \bmod n) \\ &\equiv \sum_{k=1}^r g^k \bmod n - g^{k+1} \bmod n \pmod {g-1} \\ &\equiv g^r \bmod n - g^1 \bmod n \\ &\equiv 1-g \equiv 0 \pmod {g-1}. \end{align*}This finishes the proof.