Extended Euclidean Algorithm with Example

In this class, We discuss the Extended Euclidean Algorithm with Examples.

The reader should have prior knowledge of the basics of discrete mathematics. Click Here.

To find the GCD(a, b), we used the equation x = x1 – qx2. x1 = x2 and x2 = x.

The above process is repeated until the reminder value is zero.

GCD(a, b) can be written as S * a + T * b.

Example: GCD(161, 28) = 7

7 = -1 * 161 + 6 * 28

S = -1 and T = 6

The extended Euclidean algorithm is used to identify the S and T values.

The equations are shown below.

S = S1 – q*S2

S1 = S2 and S2 = S

T = T1 – q*T2

T1 = T2 and T2 = T

The below table shows you the extended Euclidean algorithm for the GCD(161, 28).

The last row shows the S and T values.