GCD

GCD, or Greatest Common Divisor, is a mathematical concept that refers to the largest positive integer that divides two or more numbers without leaving a remainder.

In class we will derive Euclid’s algorithm, an efficient way of computing GCD, as well as explore some of the properties of GCD you will want to know when solving competitve programming problems.

Materials

• GCD Handout