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) : Mathematics

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

You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? *Contact-me*!

Sponsored ads

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 \( \mbox{pgcd}(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 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 given for free. So if you need to download the online Extended GCD Algorithm script for offline use, check contact page !

extended,gcd,identity,bezout,coefficient

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

© 2018 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode