How to calculate a Modulo?
I really can't get my head around this "modulo" thing.
Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5.
Also, what does this mean: 1/17 = 113 modulo 120 ?
Because when I calculate(using a calculator) 113 modulo 120, the result is 113. But what is the 1/17 standing for then?
THANK YOU!
$\endgroup$ 36 Answers
$\begingroup$When you see "modulo", especially if you are using a calculator, think of it as the remainder term when you do division.
Examples:
The result of 10 modulo 5 is 0 because the remainder of 10 / 5 is 0.
The result of 7 modulo 5 is 2 because the remainder of 7 / 5 is 2.
The reason your calculator says 113 modulo 120 = 113 is because 113 < 120, so it isn't doing any division.
More generally, the idea is that two numbers are congruent if they are the same modulo a given number (or modulus)
For example, as above, $7 \equiv 2 \mod 5$ where $5$ is our modulus.
Another issue is that of inverses, which is where the confusion of $1/17$ comes in.
We say that $a$ and $b$ are inverses modulo $n$, if $ab \equiv 1 \mod n$, and we might write $b = a^{-1}$.
For example $17\cdot 113 = 1921 = 120\cdot 16 +1 \equiv 1 \mod 120$, so $17^{-1} = 113$ modulo $120$.
$\endgroup$ 3 $\begingroup$There are ways to calculate it, modulo is remainder counting basically. $$7 = 2 \mod 5$$ because $7=5*1+2$ $$12 = 2 \mod 5$$ because $12=5*2+2$ and so on, so if you want to calculate for example $73 = a \mod 7$ you can do this, that is want to get $a$, take 73 and continue subtracting 7 until you no longer can. $73-7=66$, $66-7=59$ etc until we get $10-7=3$ which gives us that $a=3$ in it's simplest form (any of the results along the way can technically be a).
As for what $1/17=113 \mod 120$ the question is simply what times 17 gives remainder 1 when divided by 120? $113\cdot 17 = 1921 = 120\cdot 16+1$
$\endgroup$ 1 $\begingroup$The "mod" operator in computer languages is simply the remainder. For example,
17 mod 3 = 2because
17 / 3 = 5 rem 2which in turn means
17 = 3 * 5 + 2A simple way to understand this "modulo" operation. Consider the positive integers $7,12,17,22,27,32,...$ All these integers leave $5$ as the remainder when divided by $5$. In other words, if we subtract $2$ from each integer, the resulting set is a set multiples of $5$. We can travel on the other direction also. The integers $2,-3,-8,...$ also have that property, i.e., if we subtract $2$ from each integer, the resulting set is a set of multiples of $5$. Thus the set $\{...-8,-3,2,7,12,17,22,...\}$ will become a set of multiples of $5$ if we subtract $2$ from each. We call this set as $2$ modulo $5$. So, whenever we say $2$ modulo $5$, we mean a number which leaves $2$ as the remainder when divided by $5$. If $x \equiv 2 \pmod 5$, then $x -2$ is a multiple of $5$.
$\endgroup$ $\begingroup$Modulo is counting when knowing only a limited amount of numbers. E.g. modulo three, instead of counting
$$0,1,2,3,4,5,6,7,8,9,10,11,...$$
you count
$$ \underset{\color{lightgray}0}0, \underset{\color{lightgray}1}1, \underset{\color{lightgray}2}2,\;\; \underset{\color{lightgray}3}0, \underset{\color{lightgray}4}1, \underset{\color{lightgray}5}2,\;\; \underset{\color{lightgray}6}0, \underset{\color{lightgray}7}1, \underset{\color{lightgray}8}2,\;\; \underset{\color{lightgray}9}0, \underset{\color{lightgray}{10}}1, \underset{\color{lightgray}{11}}2,...$$
As you can see, you will end up at zero whenever the actual number is divisible by three. So finding the nearest multiples of three will help you to find its value moldulo three.
Example. $362$ is close to $360=3\times 120$. Since it is two larger than $360$, it is equivalent to $2$ modulo three. As explained in the other answers you could have found this using division with rest.
The "$1/17$ modulo $120$" is just a short form of the question "what number $x\in\{1,...,119\}$ do I have to multiply by $17$ so that the result $17x$ is equivalent to $1$ modulo $120$?". In this case, it is $113$.
$\endgroup$ 1 $\begingroup$A better understanding/formula of modulo is:
X / Y = Z (int) * Y = A | X - A = B | X %% Y = BThree calculations to be made
16 %% 6 = 4 ???Explanation:
X = 16, Y = 6
16/6=2.67Remove .67 since its integer/floor division removing decimals so it's 2.
2 * 6 = 12
16 - 12 = 4Modulo = 4 Or even better explanations in bottom of
$\endgroup$ 0
