Modular Arithmetic
The set of integers in mathematics are denoted with double struck Z.
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmQMcgsJUwnR2WP9SWHYhpq4aekXAqFFBTHaCGtyxFjBbS/image.png)
It stands for "zahlen" which means numbers in German. In , counting from 0 to 10 are simply
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmRPeDxVaPuJJjzFGcamiPFxfEjtgAf2ZXMHZLwGGXo9Y8/image.png)
Meanwhile the set of integers modulo is denoted by
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmSccLxTqQrUmWrRyNof4zS9tkrvftbuMfrHpdRN8anR8w/image.png)
and counting 1 to 10 in works as follows
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmefD7ks1VJ8uGaxACptHo4VHHK5Vdert8uqtmcnvUpj3m/image.png)
This sequence repeats every 6 numbers starting from 0. The modulo operator
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmVYekTm7ayDxwE317mBMBqtZzQNXEnTwehvEYXEcajL53/image.png)
while returns the remainder of divided by
, also yields the
-th number in the sequence of integers modulo
(
). The 10th number in the sequence of integers modulo 6
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmPYtt3J3SvreG7YfBk5Muhnaby9GiNi5ZvKxMM4HPjPMj/image.png)
is also the remainder of 10 divided by 6.
Periodicity
Two integers a,b are in the same equivalence class modulo n if both integers returns the same remainder after division by n. The -th and
-th number in the sequence of
will be the same.
Take 10 and 16 modulo 6 for example
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmWLFGXMkkPV1N3fvmM75urGar7tp3QGWXh3kYCPNdBTNL/image.png)
In the sequence of , integers within the same equivalence class are the same.
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmT7Yxdiuuotd2ySvFkiTGtJzWzEqgKufSLq8U5StHfkn2/image.png)
In congruence relations, this can be written as follows
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmSuX5ofGx5oco1MpLfgxcsmVDwDyJJ85CTMLe7NAJAJy4/image.png)
stating that a is congruent to b modulo n. Two integers are said to be congruent modulo n if they returns the same remainder when divided by n. With modulo operator, this will be
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmTPcpBnXxE8RRPHxF23adYNmwKKh8boph1h583vbP9ZtJ/image.png)
Notice the repeating nature of sequence. For example n=6
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmWEBBtHGaesMQppHRpedPDurEVFaFa29jwssv9ht71zr1/image.png)
Any term is the same as the n-th next term.
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmWLvcV5M76My4vw5s3Pn9e8AS7dtjhLF2j4jDcbBwuf8c/image.png)
This can be generalized further given any integer q
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmeWzM5Cu136yh7C2TPWyENkUfeMXgq79MoCqfcgTFtRsE/image.png)
showing that and
are congruent modulo
.
Compare it to sequence
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmQka1Y6owcrsQBTwQ8XY3PpKuWFgsAcYnLLh8zbjn82Ny/image.png)
The only scenario where
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmPnTxb8SCCimh2FSYMZL3a2pnzDWQ8ZT7k4vw793uuig8/image.png)
is when (if and only if?) .
Quotient Remainder Theorem
Division between any two integers does not always yield another integer. Division between 22 and 7
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmQVBi9te36TQbarFDr5zGP7RLSE8DW58TNYnoahPNaR6N/image.png)
left a remainder of 1. Quotient Remainder Theorem states that given any integer a and a natural number n, there exist another two integers q and r such that
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmYkh54gQ5crdPnxLRo974bcu3oSqACRgfu4H9b4vmJTW1/image.png)
this can be rewritten with modulo operator into
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmPSrNFdJmoCE3KfKbriTv3ygrvEhgzKXtnAo6D5VFsaxK/image.png)
and the division above can be rewritten algebraically into
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmSyjihFDw8DC8tRr5m9bdLFSGwo99dJrzAr7L25pitBxL/image.png)
or with modulo operator
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmdFCnZo5Ag5y31Uy4thqZJWPP7sGyn5G8RCzegJFkA8Je/image.png)
This is used to better demonstrate
Modular Addition
Given two integers and
, a positive integer n, and
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmYzo6WPC27JwF8uKDFenN8ST5HrdA8K5TGdrNhjWegXNy/image.png)
This can be algebraically written into
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmW2BHKmqjbEL1ADb4KitPvfqeD2vXDWe8ythXsHu9PKba/image.png)
with integers and
. Add together
and
gives
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmU1CfecJ5dHEspzXLLTFmYKywGyve5Rc7JvEKQ3iPnGKD/image.png)
Take modulo on both sides
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmPMLY7JS5ZNUuosgxeMeyqbEyQn1DmrjFLEVqVK5VNkCJ/image.png)
Because
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmetAWU2pphY5Taray1xq3WsPmEHg26o2aE1ud7NzauRMt/image.png)
and
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmRFdLh45Xqnh72yVPWaFsVgbq9jdToq8C4YGUSQEcQtaJ/image.png)
we can drop out from the equation which results into a more tidy equation
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmcVJwtLNfpKfSEzqGdc9jLrptt9PcY4mnzUVr5PZDSK2W/image.png)
Plugging back the definitions of and
gives
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmedvhYJK5TpgrwxRfPGgXD78dFU2b7me8KkaYoruoJkRL/image.png)
The equation above can be used as a tool to simplify additions under modulo operator. For example
Substituting gives similar equation for subtraction
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmVdNByG32YooqmAx8Gkuyy9NF9iwC7YqJCPso2TXGfFZ9/image.png)
In case of negative integers inside modulo operator,
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmaC8s3232tzQEcxyu6DRfnCdXKBNUctkWrHDA743kfoHv/image.png)
Modular Multiplication
Similar to addition, start with two integers and
, a positive integer n, and
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmYzo6WPC27JwF8uKDFenN8ST5HrdA8K5TGdrNhjWegXNy/image.png)
This can be algebraically written into
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmW2BHKmqjbEL1ADb4KitPvfqeD2vXDWe8ythXsHu9PKba/image.png)
multiplying and
gives
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmTGy64FAEEhBHiAkPxMe8f46vFe3yfXyaMb1degMQUgdX/image.png)
take modulo on both sides
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmaKWYogqcitSArc5QimmBwWit6tTjMVLXhao1QJwR38CE/image.png)
removing inside the modulo gives
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmQ317qypzvgfRnsF4npQ9QTDpKwxSAywP2JcdpK5spXVB/image.png)
Plugging back the definitions of and
gives
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmaYseZwuXhyAbz4SVGXX13C2f7RPg7jszEpGqVd6vn2L5/image.png)
The equation above can be used as a tool to simplify multiplications under modulo operator similar to additions under modulo operator. For example 190 squared divided by 7
which is easier to evaluate this way. It would've taken longer to first find out that
![image.png](https://steemitimages.com/640x0/https://cdn.steemitimages.com/DQmUrpCCpa3s5Tn2WDZ7PDdrLrfV6chgdAhcox32LAkG1DX/image.png)
Sidenote :
-Some programming language like Python uses percent sign (%) for modulo operator. In excel, modulo operator is written with '=mod([number];[divisor])'
-I am very sorry for night mode readers as the latex rendered are transparent.
-There's more to modular arithmetic but i'm going to leave it here. I might add more on my next posts.