## Identification numbers with check digit algorithms

### Modular Arithmetic

One of the most important tools in number theory is modular arithmetic, which involves the congruence relation. A congruence is the relationship between two numbers, that divided by a third number - called the modulus of the congruence relation - have the same remander. For example, $$32$$ is congruent with $$8$$ modulus $$12$$ since $$32 = 2 \times 12 + 8$$ and $$8 = 0 \times 12 + 8$$. This relation is usually represented in the following way: $32=8\,(\mbox{mod }12)$

In several situations it might be helpful to ignore the multiples of a given number in computations. Think e.g. about the days of the week or the time of the day; in the first case we ignore multiples of $$7$$, in the latter, multiples of $$24$$ (or multiples of $$12$$). These are examples of "modular arithmetic of modulus $$n$$".

The "12-hour clock arithmetic" is an example of modular arithmetic with modulus $$n=12$$. If the time is 7:00am now, then 10 hours later it will be 5:00pm. Usual addition would suggest that the later time should be 7 + 10 = 17, but this is not the answer because clock time "wraps around" every 12 hours (so $$7 + 10$$ is equal to $$5$$ modulus $$12$$); in 12-hour time, there is no "17 o'clock". Likewise, if the clock starts at 7:00am and 88 hours elapse, then the time will be 11:00 $$(7 + 88$$ is equal to $$11$$ modulus $$12).$$ three days latter $$(88=3\times 24+16)$$. Modular arithmetic is the extension to any $$n$$ of the 12-hour clock arithmetic.

Try your ability with clock arithmetic in this clock: