# 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.

```c
#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

```c
#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>