## Modular Arithmetic

• Greatest Common Divisor
15 pts · 5777 Solves

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

For `a = 12, b = 8` we can calculate the divisors of a: `{1,2,3,4,6,12}` and the divisors of b: `{1,2,4,8}`. Comparing these two, we see that `gcd(a,b) = 4`.

Now imagine we take `a = 11, b = 17`. Both `a` and `b` are prime numbers. As a prime number has only itself and `1` as divisors, `gcd(a,b) = 1`.

We say that for any two integers `a,b`, if `gcd(a,b) = 1` then `a` and `b` are coprime integers.

If `a` and `b` are prime, they are also coprime. If `a` is prime and `b < a` then `a` and `b` are coprime.

Think about the case for `a` prime and `b > a`, why are these not necessarily coprime?

There are many tools to calculate the GCD of two integers, but for this task we recommend looking up Euclid's Algorithm.

Try coding it up; it's only a couple of lines. Use `a = 12, b = 8` to test it.

Now calculate `gcd(a,b)` for `a = 66528, b = 52920` and enter it below.

You must be logged in to submit your flag. ### Level Up You are now level Current level