– Vanshika Paharia
I am sorry if you are hungry but Mod is not Mad Over Donuts. Sounds like such a disappointment right? What if it doesn’t have to be? What if you leave this space after learning something interesting instead?
Mod is actually Modulus. Mod is the short form used for Modulus in all computer languages. Now, most of us know modulus to be the symbol name for two vertical bars which give you the absolute value of a number. It looks something like this- |x| where x is your number.
But, but, I don’t know if you have heard of this other modulus. This modulus is a very unique number. Modular arithmetic is a system of arithmetic for numbers where these numbers “wrap around” or end when reaching a certain value. This certain value is called a modulus. Modular Arithmetic is an important part of Number Theory. And today, I am going to dissect this interesting concept in an easy peazy way.
Cannot wrap your head around this system? Worry not, this example will help you a bit more. It is a very common everyday application in fact. A clock!
The easiest way to understand this is using the face of a clock.
The numbers go from 1 to 12. When you go to “13 o’clock” according to the 24 hour system of time or military time, it is actually 1 o’clock again. Here, the numbers “wrap around” 12.
This can go on forever. When it hits the 25 hour mark, it is 1 o’clock again. 1, 13, 25, 37…. are basically the same. This is because, on dividing by 12, we will get the same remainder.
12 is the Modulus here.
Depths of Modular Arithmetic:
Now that you understand the basics of what modular arithmetic is, here are a few in depth details on it.
We consider x and y to be the same if x and y differ by a multiple of n, and we write this as x ≡ y (mod n) and say that x and y are congruent modulo. Here, 1 ≡ 13 (mod 12) when we consider the clock example. Other than that, given an integer n>1 called a modulus, two integers are congruent modulo n if n is a divisor of their difference. (I.e. if there is an integer k such that a-b=k*n)
e.g. 1. If 38 ≡ 14 (mod 12) where the symbol ≡ reads “is congruent to”.
2. 38-14 is 24. Which is a multiple of 12. Other than that, 38 and 14 both have the remainder of 2 when divided by 12.
B. The Reset
Modulus Arithmetic is also called clock arithmetic. In its simplest form, it is an arithmetic done with a count that resets itself to 0 every time a certain whole number N is reached. N is also called as modulus. This can also be seen in a protractor marked in 360 degrees.
C. Residues Modulo:
Under modulus arithmetic with mod N, the only numbers are 0, 1, 2, …., N-1. They are known as residues modulo N. Residues are added by taking the usual arithmetic sum. After which, we subtract the modulus N as many times as necessary till the sum becomes a number M between 0 to N-1 only. This M is called the sum of the numbers with modulus N.
E.g. 2+4+3+7 ≡ 6 (mod 10). Here, if we subtract N i.e. 10, we get 6 which is between 0-9.
Funny story, congruence modulo n is a congruence relation, meaning that it is an equivalence relation that is compatible with multiplication, addition as well as subtraction.
1.a ≡ b (mod n) and c ≡ d (mod n) will be (a+c)≡(b+d) (mod n)
e.g. 10 ≡ 18 (mod 8) and 18 ≡ 42 (mod 8) with remainder 2 then 28 ≡ 60 (mod 8) with remainder 4
2. a ≡ b (mod n) and c ≡ d (mod n) will be (a-c) ≡ (b-d) (mod n)
e.g. 10 ≡ 18 (mod 8) and 18 ≡ 42 (mod 8) with remainder 2 then -8 ≡ -24 (mod 8) with remainder 0
3. a ≡ b (mod n) and c ≡ d (mod n) will be ac ≡ bd (mod n)
e.g. 10 ≡ 18 (mod 8) and 18 ≡ 42 (mod 8) with remainder 2 then 180 ≡ 756 (mod 8) with remainder 4
4. a ≡ b (mod n) then a/c ≡ b/c (mod n/c)
e.g. 10 ≡ 18 (mod 8) then 5 ≡ 9 (mod 4) [I divided by 2 throughout. Thus, c=2]
Apart from our famous time system, these are some other applications:
1. It is used in musical arts because obviously, it uses bars that repeat themselves. Other than that, it is used in computer algebra, computer science, cryptography and chemistry.
2. One very practical application is to calculate checksums within serial number identifiers. E.g. ISBN, which is a barcode and number at the back of every novel, uses modulo 11 for a 10 digit ISBN and modulo 10 for a 13 digit ISBN for error detection.
3. Arithmetic modulo 7 is used in algorithms that determine the day of the week for a given date. In particular, the doomsday algorithm make heavy use of this.
4. Generally, Modular Arithmetic also has application is disciplines as law where apportionment is done and economics (e.g. game theory). Wherever proportional division and allocation play a central part of analysis, modular arithmetic plays a big role.
Now, Modular Arithmetic and Modulus has a lot of other applications and properties. You can read up more in your own time using my references. But today, this is all from us!
References: https://brilliant.org/wiki/modular-arithmetic , https://en.wikipedia.org/wiki/Modular_arithmetic, https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic, https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html, https://nrich.maths.org/4350 , https://www.britannica.com/science/modular-arithmetic