xgcd

Mathlib.Data.Int.GCD

URI: https://scilib.ai/kg/mathlib#Nat.xgcd

← MathLib Explorer

English

The extended gcd xgcd(x,y) yields a pair (a,b) such that gcd(x,y) = x·a + y·b.

Русский

Расширенный НОД xgcd(x,y) дает пару (a,b), такая что gcd(x,y) = x·a + y·b.

LaTeX

$$$xgcd(x,y) = (a,b) \quad\text{and}\quad \gcd(x,y) = x\cdot a + y\cdot b$$$

Lean4

/-- Use the extended GCD algorithm to generate the `a` and `b` values
  satisfying `gcd x y = x * a + y * b`. -/
def xgcd (x y : ℕ) : ℤ × ℤ :=
  (xgcdAux x 1 0 y 0 1).2

Похожие утверждения

Научная платформа российской исследовательской школы.

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru