Communities

The Great Outdoors

Photography & Video

Scientific Speculation

Electrical Engineering

Languages & Linguistics

Software Development

Community Proposals

tag:snake search within a tag

answers:0 unanswered questions

user:xxxx search by author id

score:0.5 posts with 0.5+ score

"snake oil" exact phrase

votes:4 posts with 4+ votes

created:<1w created < 1 week ago

post_type:xxxx type of post

Notifications

Mark all as read See all your notifications »

Q&A

Posts Tags Edits

Review Suggested Edit

You can't approve or reject suggested edits because you haven't yet earned the Edit Posts ability.

Closed-form expression for sum of Modulo Arithmetic Progression

~~Is there any closed-form expression or atleast an efficient way to calculate this sum?~~
$$ \sum_{i=1}^{N} (a \cdot i) \bmod{M} $$
we can assume $N$, $a$, and $M$ are large enough such that simple looping is not feasible and that period of the progression is also large.
I am aware of the way to calculate sum of first $N$ modulo natural numbers, but I am not able to extend that idea to this series.

Is there any closed-form expression or at least an efficient way to calculate this sum?
$$ \sum_{i=1}^{N} (a \cdot i) \bmod{M} $$
we can assume $N$, $a$, and $M$ are large enough such that simple looping is not feasible and that period of the progression is also large.
I am aware of the way to calculate sum of first $N$ modulo natural numbers, but I am not able to extend that idea to this series.

formula summation sequence modular-arithmetic

formula summation sequence modular-arithmetic