Modular arithmetic, gcd and primes

Modular arithmetic is arithmetic that wraps round, like the hours on a clock. After 12 comes 1 again.

Computers use it everywhere. A hash table picks a slot with it, and a check digit catches a typing mistake with it. This lesson covers remainders, the greatest common divisor (gcd) and prime numbers.

Divide 15 by 12. It goes in once, with 3 left over. That 3 is the remainder, and the operation that finds it is called modulo. Python writes it as %.

So 15 % 12 is 3, which is why 10 o'clock plus 5 hours is 3 o'clock. Days of the week work the same way, with 7 in place of 12.

python3 -c "print([n % 7 for n in (0, 7, 8, 15, 100)], (10 + 5) % 12)"

Many codes end with a check digit. Multiply the digits by weights 3, 1, 3, 1 and so on, and add them up. The check digit is the number that brings the total up to a multiple of 10.

If a person swaps two digits, the total changes and the check digit no longer fits. The program sees the mistake.

python3 -c "w = [3, 1, 3, 1, 3]; print([sum(int(d) * x for d, x in zip(c, w)) for c in ('12345', '12354')])"

The greatest common divisor, or gcd, of 48 and 18 is the biggest number that divides both. Here it is 6.

Euclid's method finds it by repeating one step. Replace the pair (a, b) with (b, a % b). Stop when the second number is 0. The first number is then the gcd.

a = 48
b = 18
while b != 0:
    remainder = a % b
    print(a, "mod", b, "is", remainder)
    a = b
    b = remainder
print("gcd is", a)
# Change a and b to 35 and 12. What is the gcd now?

Two numbers are coprime when their gcd is 1. Working mod 7, find x so that 3 times x leaves remainder 1. Here x is 5, because 15 % 7 is 1. We call 5 the modular inverse of 3 mod 7.

An inverse exists only when the number and the modulus are coprime. Mod 6, the number 4 has no inverse, because gcd(4, 6) is 2.

python3 -c "print([3 * x % 7 for x in range(1, 7)], [4 * x % 6 for x in range(1, 6)])"

A prime has exactly two divisors: 1 and itself. 13 is prime. 12 is not, because 2, 3, 4 and 6 divide it.

To test a number n, try dividing by 2, 3, 4 and on up. You can stop when the divisor squared passes n, because a divisor above that has a partner below it. If none divides n, it is prime.

python3 -c "print([n for n in range(2, 21) if all(n % d for d in range(2, n))])"