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 likes feedback and relevant comments; to get an answer give an email (not published). It is thanks to you that dCode has the best Extended GCD Algorithm tool. Thank you.

# Extended GCD Algorithm

## 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 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$$

### How to code the Extended GCD algorithm?

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

### How does Extended GCD algorithm work with negative numbers?

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$$

## 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, Matlab, etc.) which dCode owns rights will not be given 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 !

## Questions / Comments

Team dCode likes feedback and relevant comments; to get an answer give 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
© 2018 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode
Feedback