Search for a tool
Extended GCD Algorithm

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.

Results

Extended GCD Algorithm -

Tag(s) : Mathematics

dCode and you

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!


Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Extended GCD Algorithm tool. Thank you.

dCode is now secured over HTTPS, thank you for reporting any issue

Extended GCD Algorithm

Sponsored ads

This script has been updated, please report any problems.

Extended GCD Calculator



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.

Answers to Questions

What is Extended GCD algorithm?

The extended Euclidean algorithm is a modification of the classical GCDhref algorithm. From 2 natural inegers a and b, its steps allow to calculate their GCDhref 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 $$

How to code the Extended GCD algorithm?

Here is an implementation of the pseudo-code algorithm:
function extended_gcd(a, b) {// a, b natural integershref
r1 = a, r2 = b, u1 = 1, v1 = 0, u2 = 0, v2 = 1
while (r2! = 0) do
q = r1 ÷ r2 (integer divisionhref)
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 integerhref and u1, v1 rational integers)

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

Ask a new question

Source code

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, etc.) which dCode owns rights can be transferred after sales quote. So if you need to download the online Extended GCD Algorithm script for offline use, for you, your company or association, see you on contact page !

Questions / Comments


Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Extended GCD Algorithm tool. Thank you.


Source : https://www.dcode.fr/extended-gcd
© 2017 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode