Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is the modulus $\%$ commutative, associative, or etc? For example, can I do this:

Here is an equation I'm using: $$h_1 = (a \cdot a \cdot c_1 + a \cdot c_2 + c_3) \bmod a$$

I put aside the modulus, so I can easily rearrange the equation: $$a \cdot c_2 + c_3 = h_1 - a \cdot a \cdot c_1$$

Here's another equation: $$h_2 = (a\cdot a \cdot c_2 + a \cdot c_3 + c_4) \bmod a = ( a \cdot (a \cdot c_2 + c_3) + c_4 ) \bmod a$$

This is what I get after substitution: $$h_2 = (a \cdot ( h_1 - a \cdot a \cdot c_1) + c_4 ) \bmod a$$

Any problems?

share|improve this question
3  
In mathematics "modulus" % is not a well-defined arithmetic operation. At best it might be considered a function that returns an equivalence class rather than a number. Mathematics treats "mod" as an equivalence relation. Even in a computer programming context you can easily verify the operation is not commutative, e.g. 2 % 4 is not 4 % 2. –  hardmath May 19 '12 at 20:18
    
Do you mean C-style %, or Python-style %, which behave differently for negative numbers? –  Dan May 19 '12 at 21:51
add comment

2 Answers 2

up vote 5 down vote accepted

The modulus operation as you have it is certainly not commutative: the output is dictated by the second term. E.g., $ 7\% 3 = 1$ (because the remainder when dividing $7$ by $3$ is $1$), but $3\%7 = 3$ (because the remainder when dividing $3$ by $7$ is $3$).

It is also not associative: $(7\%5)\%3 = 2\%3 = 2$, but $7\%(5\%3) = 7\%2 = 1$.

It does not really distribute either, but it does have a similar property. Namely, $$(x+y)\% a = \Bigl((x\%a)+(y\%a)\Bigr) \%a.$$ (For example, $(2+2)\%3 = 4\%3 = 1$, but $(2\%3)+(2\%3) = 2+2 = 4$, so you need to take the modulus operation again to get equality.

You can make substitutions. If $x\%a = b$, then for any polynomial expression with integer coefficients, $p(x)$ on $x$, we have that $p(x)\%a = p(b)\%a$.

The modulus operation is clumsy in general. What you really want to use is congruences (also known as modular arithmetic) instead, which are much better behaved and allow for much (but not all) of the usual manipulations that we are used to.

share|improve this answer
add comment

Yes. Assume $\rm\ \ h_1 = (a^2 c_1 + a c_2 + c_3\ mod\ a)\ $

then $\rm\: mod\ a\!:\:$ $\rm\: h_1 \equiv a^2 c_1 + a c_2 + c_3\:$

thus $\rm\ \ \ a c_2 + c_3\equiv h_1 - a^2 c_1\:$

thus $\rm\ \ \ a(a c_2 + c_2) + c_4 \equiv a ( h_1 - a^2 c_1) + c_4$

thus $\rm\ \ \ ((a c_2 + c_2) + c_4\ mod\ a) = (( h_1 - a^2 c_1) + c_4\ mod\ a)$

Generally, as here, it is inconvenient to perform arithmetic using only normal forms (such as least equivalence class reps). Instead, convert to general equivalence classes, use general modular arithmetic and, if need be, convert back to normal forms reps only at the end of the computation. For example, to compute $\rm\:1/2\:\ mod\:\ 2n\!+\!1\:$ it is easier to choose any even rep of $1,\:$ for example $\rm\:2n\!+\!2\equiv 1,\:$ hence $\rm\:1/2\equiv (2n\!+\!2)/2\equiv n\!+\!1.$

This is familiar from fraction arithmetic. It'd be inconvenient to have to do all fraction arithmetic only with fractions in normal form (= lowest terms). For example, when adding fractions it is convenient to scale them to have a common denominator, then do the addition on these non-lowest term fractions, then, if need be, normalize the result to lowest terms.

The reason that equivalence class arithmetic proves smoother is that congruence mod m is not only an equivalence relation but is, additionally, an arithmetic congruence relation, i.e. it respects the arithmetic operations. This implies that all of the integer arithmetic laws (ring structure) are preserved in modular arithmetic. Thus we can apply all of our well-honed arithmetical intuition when performing congruence arithmetic, e.g. using identities such as the binomial theorem, differences of squares factorization, etc.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.