13.1 GCD (Greatest Common Divisor)

The GCD of two integers is the largest positive integer that divides both numbers without remainder.

• For example, the GCD of 42 and 28 is 14. (It’s the largest integer that divide both 42 and 28)
• The GCD of 25 and 55 is 5.
• The GCD of 42 and 23 is 1.

The integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1. With the precedent example, 42 and 23 are relatively prime.