# How do you do algebra with a modulo operator? **URL:** \ **Category:** Factual Questions\ **Created:** [November 28, 2012, 8:34pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403 "2012-11-28T20:34:30Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![sweeteviljesus](https://avatars.discourse-cdn.com/v4/letter/s/898d66/32.png) [@sweeteviljesus](https://boards.straightdope.com/u/sweeteviljesus)\ **Post date:** [November 28, 2012, 8:34pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/1 "2012-11-28T20:34:30Z")
I was implementing an algorithm to do a checksum on a foreign id number. A report came back that if you typed the same number for all 11 digits, it would pass the check sum. I was checking it out and, sure enough, it’s true. The last two digits of the id are the checksum and if the first nine are all the same digit, the 10 digit is equal to d \* 45 % 11 which is curiously always equal to d, but I don’t know how to reduce the equation to prove that. How do you do algebra with the modulo operator? The equation is d \* 45 % 11 = d where d belongs to [0…9]. Thanks, Rob ---
**Author:** ![DrCube](https://avatars.discourse-cdn.com/v4/letter/d/a3d4f5/32.png) [@DrCube](https://boards.straightdope.com/u/DrCube)\ **Post date:** [November 28, 2012, 8:57pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/2 "2012-11-28T20:57:05Z")
45 % 11 = 1 d \* 1 = d ---
**Author:** ![sweeteviljesus](https://avatars.discourse-cdn.com/v4/letter/s/898d66/32.png) [@sweeteviljesus](https://boards.straightdope.com/u/sweeteviljesus)\ **Post date:** [November 28, 2012, 8:59pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/3 "2012-11-28T20:59:26Z")
The grouping is arbitrary? Rob ---
**Author:** ![Jas09](https://avatars.discourse-cdn.com/v4/letter/j/d07c76/32.png) [@Jas09](https://boards.straightdope.com/u/Jas09)\ **Post date:** [November 28, 2012, 9:12pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/4 "2012-11-28T21:12:07Z")
b % n = a iff n divides b - a. So, (45 \* d) % 11 = d would be true if 11 divides (45 \* d) - d. Well, 45d - d = 44d, which clearly divides evenly by 11. ---
**Author:** ![DrCube](https://avatars.discourse-cdn.com/v4/letter/d/a3d4f5/32.png) [@DrCube](https://boards.straightdope.com/u/DrCube)\ **Post date:** [November 28, 2012, 9:17pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/5 "2012-11-28T21:17:29Z")
I think it’s associative. So (d_45)%11=d_(45%11) . And looking at it like division, it makes sense. 2\*(5%4) is the same as (2\*5)%4. I know that’s not a proof. Perhaps somebody can come along and back me up. [This link](http://www.proofwiki.org/wiki/Modulo_Addition_is_Associative) says that modulo addition is associative, which isn’t quite the same thing. Anyway, I think I’m right, but I can’t prove it. Sorry. ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [November 28, 2012, 9:36pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/6 "2012-11-28T21:36:24Z")
Assume r % t = p and s%t = q (rs) % t = [(mt+p)(nt+q)] % t = [t(mnt+m+n) + pq] % t = pq r (s%t) = (mt + p) (q) = mqt + pq Note that mqt+pq % t = pq so I would say yes it is associative. ---
**Author:** ![Jas09](https://avatars.discourse-cdn.com/v4/letter/j/d07c76/32.png) [@Jas09](https://boards.straightdope.com/u/Jas09)\ **Post date:** [November 28, 2012, 9:37pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/7 "2012-11-28T21:37:28Z")
(11 \* 45 ) % 11 = 0 11 \* (45 % 11) = 11 So it doesn’t hold for any arbitrary value d. I think the key is that 45 mod 11 = 1 and d is less than 10, so no matter how big d is you won’t “wrap around” the modulo (that is, d \* r \< 11). If you increase 45 to, say, 50, your relation no longer holds for all 0\ **Author:** ![sweeteviljesus](https://avatars.discourse-cdn.com/v4/letter/s/898d66/32.png) [@sweeteviljesus](https://boards.straightdope.com/u/sweeteviljesus)\ **Post date:** [November 28, 2012, 10:27pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/8 "2012-11-28T22:27:59Z") nm ---
**Author:** ![sweeteviljesus](https://avatars.discourse-cdn.com/v4/letter/s/898d66/32.png) [@sweeteviljesus](https://boards.straightdope.com/u/sweeteviljesus)\ **Post date:** [November 28, 2012, 10:29pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/9 "2012-11-28T22:29:49Z")
This was supposed to be in GQ, btw. My bad. ---
**Author:** ![Jas09](https://avatars.discourse-cdn.com/v4/letter/j/d07c76/32.png) [@Jas09](https://boards.straightdope.com/u/Jas09)\ **Post date:** [November 28, 2012, 10:30pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/10 "2012-11-28T22:30:10Z")
Right, and that is what makes your conclusion hold. Another short proof: If a1 = b1 mod n and a2 = b2 mod n, then a1 \* a2 = (b1 \* b2) mod n. In this case, take n = 11, b1 = 45, and b2 = d. 45 mod 11 = 1 = a1. d mod 11 = d = a2 (true since d \< 11 as defined). Therefore, a1 \* a2 = d = (45 \* d) mod 11. ---
**Author:** ![tomndebb](https://avatars.discourse-cdn.com/v4/letter/t/b9e5f3/32.png) [@tomndebb](https://boards.straightdope.com/u/tomndebb)\ **Post date:** [November 28, 2012, 10:33pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/11 "2012-11-28T22:33:29Z")
This is really a General Question rather than Great Debate. I’m sending it over there in case anyone wishes to add info. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [November 28, 2012, 10:38pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/12 "2012-11-28T22:38:27Z")
Wikipedia has a decent description of [modular arithmetic](http://en.wikipedia.org/wiki/Modular_arithmetic). The things you’re adding there are cosets x + nZ {…, -n + x, x, n + x, …} for a fixed modulus n; the % operator just chooses the unique element of that set in [0, …, n-1]. The upside is that you’re working with integers rather than sets, which is convenient if you’re a computer and don’t want to deal with infinite sets; the downside is the operation isn’t linear: (a + b) % n is no longer necessarily a % n + b % n. The two values are equal modulo n, but the latter sum can wrap over the boundary: (7 + 5) % 11 = 12 % 11 = 1, but 7 % 11 + 5 % 11 = 12. It’s also no longer true that a \* (b % n) = (a \* b) % n for a similar reason, though we still have (a \* (b % n)) % b = (a \* b) % n. If you find this sort of thing interesting, he’s a more [general case](http://en.wikipedia.org/wiki/Quotient_group). ---
**Author:** ![Manduck](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/manduck/32/256_2.png) [@Manduck](https://boards.straightdope.com/u/Manduck)\ **Post date:** [November 28, 2012, 10:44pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/13 "2012-11-28T22:44:57Z")
Since d is restricted to [0…9] you can just check all ten cases individually instead of coming up with a general rule. ---
**Author:** ![robert\_columbia](https://avatars.discourse-cdn.com/v4/letter/r/e79b87/32.png) [@robert\_columbia](https://boards.straightdope.com/u/robert_columbia)\ **Post date:** [November 28, 2012, 11:25pm UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/14 "2012-11-28T23:25:41Z")
> [@sweeteviljesus](#): > > This was supposed to be in GQ, btw. My bad. You’re excused, dear Aunt Sally. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 29, 2012, 12:19am UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/15 "2012-11-29T00:19:44Z")
> [@DrCube](#): > > I think it’s associative. So (d_45)%11=d_(45%11) . And looking at it like division, it makes sense. 2\*(5%4) is the same as (2\*5)%4. I know that’s not a proof. The % operator very much is not associative, neither in the typical sense of associativity ( (3 % 6) % 4 = 3 % 4 = 3, while 3 % (6 % 4) = 3 % 2 = 1 ), nor in the sense you apparently intend ( (3 \* 6) % 4 = 18 % 4 = 2, while 3 \* (6 % 4) = 3 \* 2 = 6 ). What IS true is that (d \* b) % c = (d \* (b % c)) % c. So (d \* 45) % 11 = (d \* (45 % 11)) % 11 = (d \* 1) % 11 = d % 11. This would only actually equal d, mind you, if d is in the range [0, 11). But this suffices for the OP’s purposes. ---
**Author:** ![tim314](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tim314/32/3468_2.png) [@tim314](https://boards.straightdope.com/u/tim314)\ **Post date:** [November 29, 2012, 4:37am UTC](https://boards.straightdope.com/t/how-do-you-do-algebra-with-a-modulo-operator/642403/16 "2012-11-29T04:37:59Z")
There’s lots of ways to get this result, but the way I see it is you know the part of d \* 45 that divides evenly by 11 won’t change the result of d \* 45 % 11. In general terms, if x = a \* b + c, then x % b = c % b. (For integer x, a, b, c) Thus, since d \* 45 = 4 d \* 11 + d, it follows that d \* 45 % 11 = d % 11.