# Greatest Common Divisor

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

## How to calculate ?

There is several methods to obtain a GCD :

### Divisors listing

The first method consist, as this names sounds for, list every divisor for each integers.

For `a = 12, b = 8` , the divisors of a: `{1,2,3,4,6,12}` and the divisors of b: `{1,2,4,8}`. Comparing these two, then `gcd(a,b) = 4`.

This method is easy and can be quickly done for small integer but if the integers are `a= 54213214, b=32541548` this can take a while.

### Euclid's algorithm

This is a two step algorithm :

1. Do an Euclid's Division on the bigger integer (A) by the lower (B), keep the rest and B
2. If the rest = 0 then `gcd = B` else, do the step 1 again with A = B and B = rest.

```python
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a, a)
```

## Extended Euclid's Algorithm

The extended Euclidean algorithm is an algorithm for finding the greatest common divisor (GCD) of two integers and finding the coefficients of the linear combination of the two integers that give the GCD.

The coefficients are often represented as the [Bezout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout's_identity) and they satisfy the equation:

$$
GCD(a,b) = a*u + b*v
$$

The extended Euclidean algorithm can be used to solve Diophantine equations, which are equations with integer solutions, and is also used in public key cryptography, such as the RSA algorithm, to find the modular inverse of an integer.

### How it works ?

The extended Euclidean algorithm works by keeping track of the intermediate remainders and division results within the Euclid's algorithm and using them to calculate the coefficients.

At each step of the algorithm, the previous remainders and division results are used to calculate the new coefficients. The algorithm continues until the final remainder is zero.

```python
def egcd(a,b):
    if b == 0:
        return a,0,1

    gcd, u1, v1 = egcd(b, a%b)

    u = v1 - (a//b) * u1
    v = u1

    return gcd, u, v
```

## Resources

{% embed url="<https://www.dcode.fr/pgcd>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/greatest-common-divisor.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.