Extended Eucledian Algorithm


The Extended Euclidean Algorithm is an essential algorithm in number theory. For given integers $a$ and $b$, the extended Euclidean algorithm not only calculate the greatest common divisor $d$ but also two additional integers $x$ and $y$ that satisfy the following equation.
$$ax + by =d= gcd(a, b)$$

The existence of such integers is guaranteed by Bézout’s lemma. 

Here’s how it works:

Problem Statement: Given integers $a$ and $b$, find integers $x$ and $y$ such that $ax + by = gcd(a, b)$.

Algorithm Steps:
Start with the GCD of  $a$ and $b$.
Reverse the steps in the Euclidean algorithm to find $x$ and $y$.
Treat the numbers as variables and work our way backward to express the GCD as a linear combination of  $a$ and $b$

Example: 
Given $a = 11$ and $b = 3$.
We start with the GCD:
$$11=3.3 + 2$$
$$3=1.2+1$$
$$2=2.1+0$$
So GCD=gcd(11,3)=1

Now we can reverse the process. Repeatedly replace terms until we get the final result.We have to consider the coefficient of  $a$ and $b$ as variables.

$$1=3- 1.2$$
$$1=3-1.(11-3.3)$$
$$1= (-1) 11+(4).3$$

Thus $x=-1$ and $y=4$

The extended Euclidean algorithm is useful for solving modular equations, finding modular inverses, and cryptographic applications

Example:

Given $a = 30$ and $b = 20$, we want to find integers $x$ and $y$ such that:
$$ax + by = gcd(a, b)$$
Step 1: 
Apply the Euclidean Algorithm and Calculate the GCD of 30 and 20 using the Euclidean algorithm:
$$30 = 1 \cdot 20 + 10$$
$$20 = 2 \cdot 10 + 0$$
The GCD is 10.

Step 2: Work Backward to Find Bézout Coefficients
$$10 = 30 - 1 \cdot 20$$
Substitute the value of 20 from the previous row:
$$10 = 30 - 1 \cdot (30 - 1 \cdot 20)$$
Simplify:
$$10 = 2 \cdot 30 - 1 \cdot 20$$
Now we have the desired expression:
$$10 = 2 \cdot 30 - 1 \cdot 20$$

Result:The Bézout coefficients are $x = 2 $and $y = -1$.
The GCD of 30 and 20 can be expressed as:$10=30 \cdot 2 + 20 \cdot (-1) $

Therefore, in this example, the Extended Euclidean Algorithm gives us the Bézout coefficients and expresses the GCD as a linear combination of 30 and 20.

Note that this process is tedious when we have to perform large number of steps to compute GCD.A better mathematical approach can be used to find $x$ and $y$ as described below.

Now let us show how to extend the Euclidean algorithm to determine $(x,y,d)$ given $a$ and $b$.



We assumed that  $$r_i=ax_i+by_i$$
Therefore $x_i=x_{i-2}-q_ix_{i-1}$ and $y_i=y_{i-2}-q_iy_{i-1}$


Example:

let us use $a=1759$ and $b=550$
The results are shown in Table below.Thus, we have 
1759 × (–111) + 550 × 355 = –195249 + 195250 = 1.


Example:

Find gcd $d$ of $x=525$ and $y=231$ and express $d$ as $ax + by$ where $a$ and $b$ are integers.

 

gcd=21=(4)*525+(-9)*231

Find gcd $d$ of $a:299$ and $b:221$ and express $d$ as $ax +by$ where $x$ and $y$ are integers.

gcd=13=(3)*299+(-4)*221

Python code

def  extendedEuclid(a, b):
    if b == 0:
        return a, 1, 0
    
    gcd, x1, y1 = extendedEuclid(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return gcd, x, y
gcd,x,y=extendedEuclid(4076,1024)
print(gcd,x,y)

Using sympy library
from sympy import gcdex

# Example usage
a = 30
b = 50

# gcdex returns a tuple (x, y, gcd)
x, y, gcd = gcdex(a, b)

print(f"GCD of {a} and {b} is {gcd}")
print(f"Coefficients x and y are {x} and {y}, respectively.")
print(f"This means {a}*{x} + {b}*{y} = {gcd}")

Output:
GCD of 30 and 50 is 10 
Coefficients x and y are 2 and -1, respectively. 
This means 30*2 + 50*-1 = 10

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more