ExtendedGCD

ExtendedGCD[n1,n2,]
gives the extended greatest common divisor of the integers ni.

DetailsDetails

  • Integer mathematical function, suitable for both symbolic and numerical manipulation.
  • ExtendedGCD[n1,n2,] returns a list {g,{r_(1),r_(2),...}} where g is GCD[n1,n2,] and g=r_(1)n_(1)+r_(2)n_(2)+....
  • ExtendedGCD automatically threads over lists.

ExamplesExamplesopen allclose all

Basic Examples  (2)Basic Examples  (2)

The extended greatest common divisor of 2 and 3:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

Compute the extended GCD of several integers:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
Introduced in 1988
(1.0)
| Updated in 2003
(5.0)