Modular Arithmetic and the Greatest Common Divisor

Modular arithmetic is a fascinating part of math (also discussed in super math tips). You do it all the time: if I tell you that the time is now 9 o'clock and ask what will be the time 5 hours from now, you'll tell me 2 o'clock without hesitation. You are using modular arithmetic here.

Here is a nice question regarding modular arithmetic and the greatest common divisor. Apparently, they are both tightly related:

Given that a ≡ b (mod m), prove that gcd(a, m) = gcd(b, m)

To find the greatest common divisor you can use a nice little trick. Factor out the number completely and take the lowest degree of each factor. For example, gcd(24, 32):
24 = 2^3 * 3
32 = 2^5

The lowest degree of 2 is 3 and the lowest degree of 3 is 0 (3^0 = 1, so it does not count as a factor). This means gcd(24, 32) = 2^3 = 8.

Since a ≡ b (mod m) (read as "a is congruent to b modulo m"), the difference between a and b must be a whole multiple of m:
a - b = km (k is an integer)
a = b + km
Since k can be any integer, we can also write this as:
a = b - km

Let's use the GCD trick on a and m:
a = 2^n1 * 3^n2 * 5^n3 * ...
m = 2^x1 * 3^x2 * 5^x3 * ...

When we add km to a, we don't lower any exponent of any factor, we can just raise it, so:
gcd(a, m) = gcd(a + km, m)

But if you look at the identity written earlier, we can see that:
a = b - km
a + km = b

So:
gcd(a, m) = gcd(a + km, m) = gcd(b, m)

Q.E.D.

Nadav

nadavs