Differences
This shows you the differences between two versions of the page.
— |
modular:modular_arithmetics_draft [2015/03/19 19:57] (current) aleksei imported from previous wiki |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== Modular arithmetics ===== | ||
+ | $\renewcommand{\mod}{\operatorname{mod}}$ | ||
+ | Sometimes when you want to calculate something | ||
+ | you might only require the remainder of the answer when divided by some natural number $n$. With help of modular arithmetics finding the required remainder usually happens to be much easier than evaluating the original expression. | ||
+ | |||
+ | Before we start off with examples, let us introduce a handy notation. | ||
+ | |||
+ | <WRAP def> | ||
+ | For integers $a, b$ and a natural number $n$ let | ||
+ | $a \equiv b \ (\mod n)$ | ||
+ | denote that $a$ and $b$ have the same remainder when divided by $n$, i.e., that $a \mod n = b \mod n$ holds. | ||
+ | </WRAP> | ||
+ | |||
+ | In essence, modular arithmetics means counting in a circle. There are many real-world examples: | ||
+ | clock: 19:00 + 7 hours = 02:00, | ||
+ | |||
+ | weekdays: friday (5th day) + 4 days = tuesday (2nd day), | ||
+ | |||
+ | counting-out games, etc. | ||
+ | |||
+ | {{url>../illustrations/modular.html 300px, 250px noscroll noborder}} | ||
+ | |||
+ | Let us consider a bit more technical example: Let's say someone asks you to check whether $5638 \times 7891 + 2731 \times 3124$ is divisible by $17$. | ||
+ | |||
+ | One way to do this is to go ahead and calculate the expression: | ||
+ | |||
+ | $5638 \times 7891 + 2731 \times 3124 = 44489458 + 8531644 = 53021102$, | ||
+ | |||
+ | then check if $17$ divides the answer... yawn. Ok, done. | ||
+ | |||
+ | On the other hand, a modular arithmetic approach would be to note that $\mod 17$ we have: | ||
+ | |||
+ | $10 = 17 - 7 \equiv -7$, | ||
+ | |||
+ | $100 = 10^2 \equiv (-7)^2 = 49 = 51 - 2 \equiv -2$, | ||
+ | |||
+ | $5638 = (51+5) \cdot 100 + (34 + 4) \equiv 5 \cdot (-2) + 4 = -6$, | ||
+ | |||
+ | $7891 = (85-7)\cdot 100 + (85+6) \equiv (-7)\cdot(-2) + 6 = 20 \equiv 3$, | ||
+ | |||
+ | $2731 \equiv (-7)\cdot(-2) - 3 = 11 \equiv -6$, | ||
+ | |||
+ | $3124 \equiv (-3)\cdot(-2) + 7 = 13 \equiv -4$, | ||
+ | |||
+ | and | ||
+ | |||
+ | $5638 \times 7891 + 2731 \times 3124 | ||
+ | \equiv (-6) \cdot 3 + (-6) \cdot (-4) = (-6) \cdot (-1) = 6$. | ||
+ | |||
+ | So the answer is: no, it is not, as the remainder is $6$, not $0$. | ||
+ | |||
+ | Note that in the above example in the arithmetic expressions following the equivalenvce $\equiv$, we allowed ourselves to replace any number with a number having the same remainder modulo $17$. | ||
+ | This is because the **“equivalence modulo | ||
+ | $n$”** behaves very nicely with respect to arithmetic operations. (Why not try to prove the following bit of theory yourself?) | ||
+ | <WRAP thtask> | ||
+ | If $a \equiv b \ (\mod n)$ and $c \equiv d \ (\mod n)$ then | ||
+ | |||
+ | (1) $a+c \equiv b+d \ (\mod n)$ | ||
+ | |||
+ | and | ||
+ | (2) $ac \equiv bd \ (\mod n)$. | ||
+ | ++++Proof| | ||
+ | Let us denote the quotient and the remainder when dividing $a$ by $n$ by $q_a$ and $r_a$, i.e., | ||
+ | $a = q_a n + r_a$, and similarly for $b$, $c$, and $d$. By assumption, we have $r_a = r_b$ and $r_c = r_d$. Then | ||
+ | |||
+ | $(a+c) \mod n = \big((q_a+q_c)n + r_a + r_c \big) \mod n = (r_a + r_c) \mod n$ | ||
+ | |||
+ | and | ||
+ | |||
+ | $(b+d) \mod n = \big((q_b+q_d)n + r_b + r_d \big) \mod n = (r_b + r_d) \mod n = (r_a + r_c) \mod n$. | ||
+ | |||
+ | Similarly, | ||
+ | |||
+ | $ac \mod n = (q_a n q_c n + q_a n r_c + q_c n r_a + r_a r_b) \mod n = r_a r_b \mod n = r_b r_d \mod n = bd \mod n$. | ||
+ | ++++ | ||
+ | </WRAP> | ||
+ | |||
+ | When we say that an arithmetic expression has to be computed modulo $n$, we mean | ||
+ | that we are interested in the remainder of the value of this expression when divided by | ||
+ | $n$. For example, $(2 + 5) \cdot (8 + 6)$ is equal to $10$ modulo $11$, or | ||
+ | $(2 + 5) \cdot (8 + 6) \equiv 10 \ (\mod 11)$. | ||
+ | |||
+ | The proposition above allows us to perform computations modulo $n$, such that the intermediate | ||
+ | values do not become much larger than $n$. | ||
+ | |||
+ | Actually, when the operations that we’re | ||
+ | applying are only addition, subtraction and multiplication, then no intermediate value | ||
+ | has to be larger than $n^2$ . Namely, we can compute the remainder (by $n$) after each step | ||
+ | of the computation. Thus, we could perform the previous computation by | ||
+ | *$2+5=7$ | ||
+ | *$8 + 6 = 14 \equiv 3 \ (\mod 11)$ | ||
+ | *$7 \cdot 3 = 21 \equiv 10 \ (\mod 11)$. | ||
+ | |||
+ | In fact, we can do even more simple operations with this equivalence. | ||
+ | |||
+ | Let us look more closely at the proposition. | ||
+ | Note that part (1) is reversible in the sense that | ||
+ | if $a+c \equiv b+d \ (\mod n)$ and | ||
+ | $c \equiv d \ (\mod n)$ then $a \equiv b \ (\mod n)$. ++Because| then $-c \equiv -d \ (\mod n)$ | ||
+ | and $a+c-c \equiv b+d-d \ (\mod n)$.++ | ||
+ | |||
+ | You may use this observation to check the exercise: | ||
+ | <WRAP thtask> | ||
+ | Show that $a \equiv b \ (\mod n)$ if and only if | ||
+ | $n \mid (a-b)$. | ||
+ | |||
+ | ++++Solution| | ||
+ | Since $-b \equiv -b (\mod n)$, we have | ||
+ | |||
+ | $a \equiv b \ (\mod n) \Longleftrightarrow | ||
+ | a -b \equiv b - b = 0 (\mod n) \Longleftrightarrow n \mid (a-b)$. | ||
+ | ++++ | ||
+ | </WRAP> | ||
+ | |||
+ | Part (2), on the other hand, is not reversible in general: $4 \cdot 2 \equiv 2 \cdot 2 (\mod 4)$ | ||
+ | but $4 \not \equiv 2 (\mod 4)$. | ||
+ | |||
+ | The following exercise explains what we should do when trying to do the reverse of part (2). | ||
+ | |||
+ | <WRAP thtask> | ||
+ | Let $k \in \mathbb N$. Show that | ||
+ | * $a \equiv b \ (\mod n)$ if and only if $ak \equiv bk \ (\mod nk)$. | ||
+ | * If $ka \equiv kb \ (\mod n)$, then $a \equiv b \ (\mod \frac{n}{\gcd(k,n)} )$. | ||
+ | ++++Solution| | ||
+ | The assertions follow from the previous exercise and the facts that $nk \mid ak$ is equivalent to $a \mid n$ and $n \mid ka$ implies $\frac{n}{\gcd(k,n)} \mid a$. The former is obvious and for the latter consider the equation $ka = qn$. Dividing by $\gcd(k,n)$, we get | ||
+ | $\frac{k}{\gcd(k,n)} a = q \frac{n}{\gcd(k,n)}$. Since $\frac{k}{\gcd(k,n)}$ and $\frac{n}{\gcd(k,n)}$ have no common divisors, all the divisors of $\frac{n}{\gcd(k,n)}$ must also divide $a$, i.e., $\frac{n}{\gcd(k,n)} \mid a$. | ||
+ | ++++ | ||
+ | </WRAP> | ||
+ | |||
+ | In particular, if $k$ and $n$ are coprime, then | ||
+ | we essentially get the inverse of part (2): | ||
+ | $ka \equiv kb \ (\mod n)$ implies $a \equiv b \ (\mod n)$. | ||
+ | |||
+ | In a short while, we will see a deeper algebraic meaning of this | ||
+ | cancelability. | ||
+ | |||
+ | TODO: Examples on the last exercise. | ||
+ | |||
+ | <WRAP task> | ||
+ | Perform the following computations: | ||
+ | *$(5 \cdot 8 − 3 \cdot 6) \cdot (8 + 4) \ (\mod 9)$, | ||
+ | *$7 \cdot 7 \cdots 7 \ (\mod 11)$ (here $7$ is taken 15 times), | ||
+ | *$1 \cdot 2 \cdots 10 \ (\mod 25)$. | ||
+ | </WRAP> | ||
+ | [[Residue classes]] |