Inputs
Example Data
| a | b | gcd(a,b) | Action |
|---|---|---|---|
| 240 | 46 | 2 | |
| 252 | 198 | 18 | |
| 414 | 662 | 2 | |
| 123456 | 7890 | 6 |
Actions
CSV contains forward divisions, coefficients, and quotients. PDF captures the result section.
Results
awaiting inputUse either the a, b inputs or the Quotient stream tab. Then press Compute to see divisions, back-substitution, and the continued-fraction view.
Formula Used
The method computes the greatest common divisor while maintaining coefficients s, t such that for each remainder ri, we have ri = si·a + ti·b. Starting from (s0,t0)=(1,0) and (s1,t1)=(0,1), the recurrence for each division ri-2 = qi-1·ri-1 + ri gives:
- si = si-2 − qi-1·si-1
- ti = ti-2 − qi-1·ti-1
Quotient streams correspond directly to continued fractions of |a|/|b|. Finite streams define rationals; scaling by g multiplies the gcd by g.
How to Use
- Choose a, b or Quotient stream on the input tabs.
- For quotient mode, enter positive integers like 5,2,3. Optional g scales both terms.
- Press Compute to run divisions, back-substitution, and show the continued fraction.
- Read the Bézout identity and, if applicable, modular inverses.
- Export the steps as CSV or save the results as a PDF.
FAQs
It refers to the back-substitution phase that expresses the gcd as a·x + b·y by reversing the forward divisions. This yields Bézout coefficients and, when coprime, modular inverses.
Enter Euclidean quotients q₁,…,qₖ. They define the continued fraction of |a|/|b|. The final convergent gives a coprime ratio; scaling by g sets the gcd.
Yes for a, b mode. Quotient streams produce positive ratios; you may add signs after reconstruction by negating a or b before computing.
A modular inverse exists only when the numbers are coprime. If gcd(a,b) ≠ 1, neither a modulo b nor b modulo a will have an inverse.
It is derived directly from the coefficient recurrences. Each row’s si, ti satisfies ri = si·a + ti·b, culminating in the gcd line.