Description
Find the greatest common divisor g of two positive integers a and b, and coefficients h, j such that g = ha + jb (Bézout's identity). Initialize r,s,t = a,1,0 and r',s',t' = b,0,1. While r' ≠ 0: compute quotient q, then update (r,s,t) and (r',s',t') using the Euclidean step. Output gcd and Bézout coefficients. Used for modular inverses. Time O(log min(a,b)).
Algorithm Flowchart
graph TD
A1["Positive integers\na, b"]
B1["Initialize r s t = a 1 0\nr' s' t' = b 0 1"]
D1{"r' equals 0?"}
C1["q = r div r'\nUpdate r s t and r' s' t'"]
F1["Return gcd = r\nBézout coeffs s t"]
A1 --> B1
B1 --> D1
D1 -->|Yes| F1
D1 -->|No| C1
C1 --> D1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1 green
class F1 violet
class D1 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 5
- Edges: 5
- OR gates: 1
- Loops: 1
- AND gates: 0
- Complexity: O(log min(a,b))
Keywords
- extended Euclidean
- GCD
- Bézout coefficients
- modular inverse
- NIST DADS
- number theory