https://github.com/cran/pracma
Tip revision: 71455748623ef69836470c75c5f9384f6e872d45 authored by HwB on 28 June 2011, 00:00:00 UTC
version 0.6-3
version 0.6-3
Tip revision: 7145574
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 }