A typescript implementation of the **gcd** and **Extended Euclidean** algorithm.
- gcd: The Greatest Common Divisor.
- Extended Euclidean algorithm: For solving the smallest integer solution (|x| + |y| smallest) of
the equation `Ax + By = gcd(x,y)`.
## Install
- npm
```bash
npm install --save @algorithm.ts/gcd
```
- pnpm
```bash
pnpm add @algorithm.ts/gcd
```
## Usage
- gcd
```typescript
import { gcd, gcdBigint } from '@algorithm.ts/gcd'
gcd(3, 4) // => 1
gcdBigint(3n, 6n) // => 3n
```
- Extended Euclidean algorithm
```typescript
import { euclidean, euclideanBigint } from '@algorithm.ts/gcd'
// 3x + 4y = gcd(3, 4)
euclidean(3, 4) // => [-1, 1, 1]
euclidean(3, 8) // => [3, -1, 1]
euclideanBigint(6, 8) // => [-1n, 1n, 2n]
```
## Related
- [数论基础之模方程初步][gcd]
[homepage]:
https://github.com/guanghechen/algorithm.ts/tree/@algorithm.ts/gcd@4.0.4/packages/gcd#readme
[gcd]: https://me.guanghechen.com/post/math/number-theory/%E6%A8%A1%E6%96%B9%E7%A8%8B/basic/
