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].

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.

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.

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.

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.

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.