Extended Greatest Common Divisor
Description
The command xgcd(a, b)) returns the greatest common divisor $d$ of $a$ and $b$ and integers $r$ and $s$ such that $d = ra + sb$.
Sage Cell
Code
a = 633
b = 331
extended = xgcd(a, b)
d = extended[0]
r = extended[1]
s = extended[2]
d == r*a + s*b
Options
None
Tags
Primary Tags: number theory
Secondary Tags: greatest common divisor
Related Cells
- The Modulus Operator
- The Quotient-Remainder Method
- The Divides Method
- The Greatest Common Divisor Command
- The Is-Prime Method
- The Random Prime Command
- The Prime Range Command
- The Next Prime Command
- The Previous Prime Command
- The Factor Command
Attribute
Permalink: http://abstract.ups.edu/aata/integers-sage.html
Author: R. Beezer
Date: 15 Jul 2017 08:23
Submitted by: Tom Judson