https://github.com/cran/pracma
Tip revision: 9683335bbee02d0e5a569a07826d458ca55d5370 authored by HwB on 06 June 2012, 00:00:00 UTC
version 1.1.0
version 1.1.0
Tip revision: 9683335
extgcd.Rd
\name{extGCD}
\alias{extGCD}
\title{Extended Euclidean Algorithm}
\description{
The extended Euclidean algorithm computes the greatest common divisor and
solves Bezout's identity.
}
\usage{
extGCD(a, b)
}
\arguments{
\item{a, b}{integer scalars}
}
\details{
The extended Euclidean algorithm not only computes the greatest common
divisor \eqn{d} of \eqn{a} and \eqn{b}, but also two numbers \eqn{n} and
\eqn{m} such that \eqn{d = n a + m b}.
This algorithm provides an easy approach to computing the modular inverse.
}
\value{
a numeric vector of length three, \code{c(d, n, m)}, where \code{d} is the
greatest common divisor of \code{a} and \code{b}, and \code{n} and \code{m}
are integers such that \code{d = n*a + m*b}.
}
\note{
There is also a shorter, more elegant recursive version for the extended
Euclidean algorithm. For R the procedure suggested by Blankinship appeared
more appropriate.
}
\seealso{
\code{\link{modinv}}
}
\references{
Blankinship, W. A. ``A New Version of the Euclidean Algorithm."
Amer. Math. Monthly 70, 742-745, 1963.
}
\examples{
extGCD(12, 10)
extGCD(46368, 75025) # Fibonacci numbers are relatively prime to each other
}
\keyword{ arith }