Where does modulus take place

Question

I know bedmas (brackets, exponents, division, multiplication, addition, subtraction), but there isn't a modulus in there. If I wanted to calculate a question with mod, when would I do it?

Answer 1

Short answer: The modulus comes last technically.

A short disclaimer before I go into it. Division is weird with the modulus, so I'm not going to try that here. You will probably see the multiplicative inverse more than you will division, so just treat division as multiplying by the multiplicative inverse.

The majority of the time if it is not meant to be last, you will see $\mod n$ in brackets. As such: $(a \mod n)$, therefore everything you do inside the brackets comes first, and then you perform the modulus. So the modulus is always last, unless in brackets.

However, here are some more interesting properties. We can actually perform the modulus anytime after all the exponents leading up the the modulus have been performed. It can be done anytime after "BED". It can even be done before brackets, as long as there is once again, no divisions or exponents inside the brackets.

The reason we can do the modulus anytime after is because of this basic properties (MAS in BEDMAS):

• A: $a+b \mod n = (a \mod n)+(b\mod n) \mod n$
• S: $a-b \mod n = (a \mod n)-(b\mod n) \mod n$
• M: $a*b \mod n = (a \mod n)*(b\mod n) \mod n$
• E: $a^b \mod n = (a \mod n)^b \mod n $

In other words we do it anytime before its needed, (except before division and exponents). However, the modulus still needs to be done last even after. The reason is $ (n-1)+(n-1) = 2n - 2 > n$ and $ (n-1)*(n-1) = n^2 - 2n + 1> n$ worst case conditions, and the modulus is always smaller than $n$.

The final rule for the exponentiation is that you cannot mod the exponent value, however you can mod the base. For division You can only mod the numerator, not the denominator. So in a way you can also apply the rule to division and exponentiation, making the modulus first and last. But you have to be careful of these exceptions. Thus these properties are false (not true, most of time):

• D: ${a\over b }\mod n\not=(a \mod n) / (b \mod n) \mod n$
• D: ${a\over b }\mod n\not=(a \mod n) / b \mod n$
• E: $a^b \mod n \not= (a \mod n)^{(b \mod n)} \mod n $

The property of modulus to be first and last is really important when we need to calculate quickly because it makes all the numbers smaller than $n$.

If you are talking about the % (the modulus) operation in programming, most of the time it happens with the same priority as multiplication or division, thus whatever operation that is the modulus, division, or multiplication, and comes first, is operated first.