Modular Arithmetic for Beginners

Правка en3, от Spheniscine, 2019-12-27 15:04:10

Introduction

If you're new to the world of competitive programming, you may have noticed that some questions have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $$$10^9 + 7$$$". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction $$$\frac pq$$$ and ask you to output $$$r$$$ where $$$r \cdot q = p \text{ mod } n$$$... not only do you have to calculate a fraction with huge numbers, how in the world are you going to find $$$r$$$?

Actually, the modulo is there to make the calculation easier, not harder. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see that it's easier than it may seem at first.

Terminology and notation

For convenience, I will define the notation $$$n \text{ mod } m$$$ to mean $$$n - \lfloor \dfrac nm \rfloor \cdot m$$$, where $$$\lfloor x \rfloor$$$ is the largest integer that doesn't exceed $$$x$$$. This may or may not correspond to the expression n % m in your programming language (% is often called the "modulo operator" but in some instances, it's more correct to call it the "remainder operator"). If -8 % 7 == 6, you're fine, but if it is -1, you'll need to adjust it by adding $$$m$$$ to any negative results.

Also for convenience, I will also define the $$$\text{ mod }$$$ operator to have lower precedence than addition or subtraction, thus $$$ax + b\ \text{ mod } m \Rightarrow (ax + b) \text{ mod } m$$$.

Теги modulo, modular arithmetic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en33 Английский Spheniscine 2020-10-24 18:50:23 20
en32 Английский Spheniscine 2020-04-18 06:33:00 319
en31 Английский Spheniscine 2020-02-12 04:43:04 101
en30 Английский Spheniscine 2020-02-12 04:39:24 214 Tiny change: 'efined as $1$](https://' -> 'efined as 1](https://'
en29 Английский Spheniscine 2020-01-16 12:01:55 73 Tiny change: ' produce a number between' -> ' produce an integer between'
en28 Английский Spheniscine 2020-01-16 11:40:32 252
en27 Английский Spheniscine 2020-01-07 15:14:50 14 Tiny change: '$0 \cdot x \text{ mo' -> '$0 \cdot x\ \text{ mo'
en26 Английский Spheniscine 2020-01-06 22:33:32 8
en25 Английский Spheniscine 2019-12-29 14:18:37 66
en24 Английский Spheniscine 2019-12-29 01:11:18 2 Tiny change: 'v p \pmod n$... not o' -> 'v p \pmod m$... not o'
en23 Английский Spheniscine 2019-12-29 01:10:14 218 Tiny change: ' \equiv p \text{ mod } n$... not o' -> ' \equiv p (\pmod n)$... not o'
en22 Английский Spheniscine 2019-12-28 13:56:37 90 Tiny change: 'ession $n mod m$ is kno' -> 'ession $n \text{ mod } m$ is kno'
en21 Английский Spheniscine 2019-12-28 05:46:39 3 Tiny change: 'minator isn't coprime t' -> 'minator is coprime t'
en20 Английский Spheniscine 2019-12-28 05:16:04 2 Tiny change: 'a fraction, we want a' -> 'a fraction; we want a'
en19 Английский Spheniscine 2019-12-28 05:15:21 181
en18 Английский Spheniscine 2019-12-28 04:34:30 32
en17 Английский Spheniscine 2019-12-28 04:30:00 7 Tiny change: 'r \cdot q = p \text{ ' -> 'r \cdot q \equiv p \text{ '
en16 Английский Spheniscine 2019-12-28 04:22:39 111
en15 Английский Spheniscine 2019-12-28 04:21:05 37
en14 Английский Spheniscine 2019-12-28 04:18:50 325
en13 Английский Spheniscine 2019-12-28 03:57:50 55
en12 Английский Spheniscine 2019-12-28 03:44:37 2 Tiny change: 'xt{ mod } 0 = 1$\n\nM' -> 'xt{ mod } m = 1$\n\nM'
en11 Английский Spheniscine 2019-12-28 03:44:15 174
en10 Английский Spheniscine 2019-12-27 17:41:43 36 Tiny change: 'orces.com/problemset/problem/935/D)' -> 'orces.com/contest/935/problem/D)'
en9 Английский Spheniscine 2019-12-27 17:37:21 8 Tiny change: 'division) in a way ' -> 'division) defined in a way '
en8 Английский Spheniscine 2019-12-27 17:26:44 344 Tiny change: 'actorials are too big ' -> 'actorials can be too big ' (published)
en7 Английский Spheniscine 2019-12-27 17:06:35 4705 Tiny change: 'method is often more popu' -> 'method is more popu'
en6 Английский Spheniscine 2019-12-27 15:56:03 270 Tiny change: 'd } m = 1$' -> 'd } m = 1$, therefore the number we need is $a^{m-2} \text{ mod } m$'
en5 Английский Spheniscine 2019-12-27 15:51:41 790 Tiny change: 'll see why. Soon you' -> 'll see why too. Soon you'
en4 Английский Spheniscine 2019-12-27 15:29:05 1601 Tiny change: 't{ mod } m' -> 't{ mod } m$'
en3 Английский Spheniscine 2019-12-27 15:04:10 518 Tiny change: ' b \text{ mod } m \' -> ' b \text{ mod } m \'
en2 Английский Spheniscine 2019-12-27 14:56:23 257
en1 Английский Spheniscine 2019-12-27 14:50:55 987 Initial revision (saved to drafts)