Tool to apply the extended GCD algorithm (Euclidean method) in order to find the values of the Bezout coefficients and the value of the GCD of 2 numbers.

Extended GCD Algorithm - dCode

Tag(s) : Arithmetics

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!

A suggestion ? a feedback ? a bug ? an idea ? *Write to dCode*!

Tool to apply the extended GCD algorithm (Euclidean method) in order to find the values of the Bezout coefficients and the value of the GCD of 2 numbers.

The **extended Euclidean** algorithm is a modification of the classical GCD algorithm. From 2 natural inegers a and b, its steps allow to calculate their GCD and their Bézout coefficients (see the identity of Bezout).

__Example:__ $ a=12 $ and $ b=30 $, thus $ gcd(12, 30) = 6 $

$$ 12 \times -10 + 30 \times 3 = 6 \\ 12 \times -3 + 30 \times 1 = 6 \\ 12 \times 4 + 30 \times -1 = 6 \\ 12 \times 11 + 30 \times -3 = 6 \\ 12 \times 18 + 30 \times -5 = 6 \ 12 \times −2+30 \times 1 = 6 $$

Here is an eGCD implementation of the pseudo-code algorithm:

function **extended_gcd**(a, b) {// a, b natural integers

r1 = a, r2 = b, u1 = 1, v1 = 0, u2 = 0, v2 = 1

while (r2! = 0) do

q = r1 ÷ r2 (integer division)

r3 = r1, u3 = u1, v3 = v1,

r1 = r2, u1 = u2, v1 = v2,

r2 = r3 - q * r2, u2 = u3 - q * u2, v2 = v3 - q * v2

end while

return (r1, u1, v1) (r1 natural integer and u1, v1 rational integers)

The values are such that r1 = pgcd(a, b) = a * u1 + b * v1

Using the absolute values for a and b, the rest of the calculation is identical thanks to the property: $$ a(\text{sign}(a)\cdot x)+b(\text{sign}(b)\cdot y)=1 $$

dCode retains ownership of the source code of the script Extended GCD Algorithm online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be released for free. To download the online Extended GCD Algorithm script for offline use on PC, iPhone or Android, ask for price quote on contact page !

extended,gcd,egcd,identity,bezout,coefficient

Source : https://www.dcode.fr/extended-gcd

© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲