Euclid's Algorithm in C

Overview

This C implementation calculates the Greatest Common Divisor (GCD) of two integers using Euclid's Algorithm. Euclid's Algorithm is a highly efficient method for finding the GCD, which is the largest positive integer that divides both numbers without a remainder.

Mathematical Formula

Euclid's Algorithm is based on the following principle:

• GCD(a, b) = GCD(b, a mod b) where 'a mod b' is the remainder when 'a' is divided by 'b'.
• GCD(a, 0) = a

The algorithm repeatedly applies this formula until the second number becomes 0. At that point, the first number is the GCD.

Description of Euclid's Algorithm

Euclid's Algorithm is an iterative process. Here's a breakdown:

1. Input: Two non-negative integers, a and b.
2. Iteration:
   • Calculate the remainder r when a is divided by b ( r = a % b ).
   • If r is 0, then b is the GCD. Return b.
   • Otherwise, set a = b and b = r.
   • Repeat the iteration.
3. Output: The GCD of a and b.

Uses of Euclid's Algorithm

Euclid's Algorithm has numerous applications in mathematics and computer science, including:

• Finding the Greatest Common Divisor (GCD): The primary use, as demonstrated by this implementation.
• Simplifying Fractions: Dividing both the numerator and denominator of a fraction by their GCD reduces the fraction to its simplest form.
• Cryptography: Used in various cryptographic algorithms, such as RSA.
• Modular Arithmetic: Essential for calculations involving modular inverses and congruences.
• Computer Science: Used in hashing algorithms and other data structures.

Code Implementation

The C code provides a function euclid(int m, int b) that implements Euclid's Algorithm iteratively.

#include <stdio.h>
#include <stdlib.h>

int euclid(int m, int n) {
  int remainder;

  remainder = m % n;
  while(remainder != 0) {
    m = n;
    n = remainder;
    remainder = m % n;
  }
  return(n);
}

Usage

To use the euclid function

#include <stdio.h>

int euclid(int m, int n); // Declare the function

int main() {
  int num1 = 48;
  int num2 = 18;
  int result = euclid(num1, num2);
  printf("GCD of %d and %d is %d\n", num1, num2, result); // Output: GCD of 48 and 18 is 6
  return 0;
}

Author

Koree A. Smith koree@koree.net