How do you do algebra with a modulo operator?

Factual Questions
#1

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

#2

45 % 11 = 1
d * 1 = d

#3

The grouping is arbitrary?

Rob

#4

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.

#5

I think it’s associative. So (d45)%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 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.

#6

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.

#7

(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<d<10 either.

#8

nm

#9

This was supposed to be in GQ, btw. My bad.

#10

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.

#11

This is really a General Question rather than Great Debate.
I’m sending it over there in case anyone wishes to add info.

#12

Wikipedia has a decent description of 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.

#13

Since d is restricted to [0…9] you can just check all ten cases individually instead of coming up with a general rule.

#14

You’re excused, dear Aunt Sally.

#15

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.

#16

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.