IRAN national math olympiad(3rd round)-2010-NT exam-p6

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IRAN national math olympiad(3rd round)-2010-NT exam-p6

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

#1 h Aug 9, 2010, 9:41 AM • 2 Y

Y by Adventure10, Mango247

$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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

204 posts

mmaht

#2 h Jul 5, 2014, 8:50 PM • 2 Y

Y by Adventure10, Mango247

still no solution?!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#5 h Aug 30, 2020, 1:59 AM • 7 Y

Y by Mathematicsislovely, mijail, v4913, Mango247, Mango247, Mango247, Tastymooncake2

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#6 h Dec 28, 2023, 9:02 PM

Y by

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.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 28, 2023, 9:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4175 posts

#8 h Mar 27, 2025, 5:25 AM

Y by

Let $r$ be the order of $g$ mod $n$ . For the rest of the solution, we let $a\pmod{b}$ denote the remainder when $a$ is divided by $b$ . We wish to find
$\sum_{i=0}^{r-1} \lfloor (g^i\pmod{n})\cdot\frac{g}{n}\rfloor$ $\sum_{i=0}^{r-1} \frac{g\cdot (g^i\pmod{n})-(g\cdot (g^i\pmod{n}))\pmod{n}}{n}$ $\sum_{i=0}^{r-1} \frac{g\cdot (g^i\pmod{n})-g^{i+1}\pmod{n}}{n}.$ This becomes a telescoping sum:
$\frac{g(g^0\pmod{n})+(g-1)(g^1\pmod{n}+g^2\pmod{n}+\dots+g^{r-1}\pmod n)-g^r\pmod{n}}{n}.$ Since $g(g^0\pmod n)-g^r\pmod n=g-1$ , the numerator is divisible by $g-1$ , and since $n$ is also relatively prime to $g-1$ , we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a