g and n are natural numbers such that gcd(g2−g,n)=1 and A={gi|i∈N} and B={x≡(n)|x∈A}(by x≡(n) we mean a number from the set {0,1,...,n−1} which is congruent with x modulo n). if for 0≤i≤g−1 ai=|[nig,n(i+1)g)∩B| prove that g−1|∑g−1i=0iai.( the symbol | | means the number of elements of the set)(1006 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∈B will fall in the ⌊g⋅bn⌋'th interval, and contribute that amount to the sum given in the problem. This gives the first equality in the following calculation: ∑iai=∑b∈B⌊g⋅bn⌋=e−1∑k=0⌊g⋅(gk%n)n⌋=e−1∑k=0g⋅(gk%n)−(g⋅(gk%n))%nn 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.