Euclidean Algorithm

This algorithm finds gcd by performing repeated division starting from the two numbers we want to find the gcd of until we get a remainder of .

• If then , since the , and we can stop
• If then , since the , and we can stop
• Write in quotient remainder form
• Find , using the Euclidean Algorithm since

Example

C++

int gcd(int a,int b) {
  int swap;
  while ((a % b) > 0)  {
    swap = a % b;
    a = b;
    b = swap;
  }
  return b;
}