Euclidean Algorithm

One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.First, we need a simple definition: Two integers are relatively prime if their only common positive integer factor is 1.

Greatest Common Divisor

Recall that a  nonzero $b$ is defined to be a divisor of $a$  if $a=mb$ for some $m$, where $a , b,$  and $m$ are integers.We will use the notation $gcd(a , b)$ or $(a,b)$ to mean the greatest common divisor of $a$ and $b$. The greatest common divisor of $a$ and $b$  is the largest integer that divides both $a$ and $b$ .We also define $gcd(0, 0) = 0$.

More formally, the positive integer $c$ is said to be the greatest common divisor of $a$ and $b$ if

1.$c$ is a divisor of $a$ and $b$ .

2. Any divisor of $a$  and $b$ is a divisor of  $c$.

An equivalent definition is the following:

$gcd(a, b) = max[k, $such that $k | a$ and $k | b]$

Because we require that the greatest common divisor be positive,$gcd(a,b)=gcd(a-b)=gcd(-a,b)=gcd(-a,-b)$. In general $gcd(a,b)=gcd(|a|,|b|)$

Example:

$gcd(60,24)=gcd(60,-24)=12$

Also, because all nonzero integers divide 0, we have $gcd(a,0)=|a|$.

Two integers $a$ and $b$ are relatively prime if their only common positive integer factor is 1. This is equivalent to saying that $a$ and $b$ are relatively prime if $gcd(a, b) = 1$.

Finding the greatest common divisor

Lets describe the Euclids algorithm for finding the greatest common divisors of two integers.

Suppose we have integers $a, b$ such that $d = gcd(a, b)$. Assume $a \ge b \gt 0$. Now dividing $a$ by $b$ and applying the division algorithm, we can state

$$a=q_1b+r_1 \quad 0 \le r_1 \lt b$$

If it happens that $r_1=0$, then $b|a$  and $d=gcd(a,b)=b$. But if  $r_1 \ne 0$, we can state that $d|r_1$. This is due to the basic properties of divisibility: the relations $d|a$ and $d|b$ together imply that $d|(a-q_1b)$, which is the same as $d|r_1$. Before proceeding with the Euclidian algorithm, we need to answer the question:What is the $gcd(b,r_1)$? We know that $d|b$ and $d|r_1$ . Now take any arbitrary integer $c$ that divides both $b$ and $r_1$ . Therefore, $c|(q_1b+r_1)=a$ . Because $c$ divides both $a$ and $b$ , we must have $c \le d$ , which is the greatest common divisor of $a$ and $b$.Therefore $d=gcd(b,r_1)$.

Lets now assume that $r_1 \ne 0$. Because $b \gt r_1$, we can divide $b$ by $r_1$and apply the division algorithm to obtain:

     $$b=q_2r_1 + r_2 \quad 0 \le r_2 \lt r_1$$

We can define the Euclidean algorithm concisely as the following recursive function.( where % is the mod operator)

Euclid(a,b)

if (b=0) then 

        return a;

else 

        return Euclid(b, a % b);

Example:

gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11

gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

gcd(11, 10) = gcd(10, 1) = gcd(1, 0) = 1

Time Complexity: O(log(min(a, b))) since the algorithm reduces the values quickly by taking the modulus.

Python Code:

def euclidean_gcd(a, b):

    while b != 0:

        a, b = b, a % b

    return a

# Example usage:

a = 48

b = 18

gcd = euclidean_gcd(a, b)

print("GCD of", a, "and", b, "is:", gcd)

We can also use built in function gcd() from math module

Example:

import math

print(math.gcd(10,100))