Skip to main content
calcu
.lol
Search
Ctrl K
Language
EN
English
English
EN
简体中文
ZH
Español
ES
العربية
AR
Português (Brasil)
PT
日本語
JA
Français
FR
Deutsch
DE
Home
›
Math & Algebra
›
Extended Euclidean Algorithm
Extended Euclidean Algorithm
GCD with Bézout coefficients
Favorite
Print
Integer a
Integer b
a · x + b · y = gcd(a, b)
Greatest common divisor
6
Bézout coefficients
x (coefficient of a)
2
y (coefficient of b)
-3
Bézout identity
(48)·(2) + (30)·(-3) = 6
Coprime
No
Copy link
Extended Euclidean Algorithm
Step-by-step Euclidean division reducing a and b to their greatest common divisor, then the Bézout identity a·x + b·y = gcd.
Euclidean division steps
48 = 1 × 30 + 18
30 = 1 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0
gcd = 6
(48)·(2) + (30)·(-3) = 6
