gcd

@algorithm.ts/gcd

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

  npm install --save @algorithm.ts/gcd

• yarn

  yarn add @algorithm.ts/gcd

Usage

• gcd

  import { gcd, gcdBigint } from '@algorithm.ts/gcd'
  
  gcd(3, 4) // => 1
  gcdBigint(3n, 6n) // => 3n

• Extended Euclidean algorithm

  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

• 数论基础之模方程初步