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

Attribute

Permalink: http://abstract.ups.edu/aata/integers-sage.html

Author: R. Beezer

Date: 15 Jul 2017 08:23

Submitted by: Tom Judson

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License