gcdA

Mathlib.Data.Int.GCD

URI: https://scilib.ai/kg/mathlib#Int.gcdA

← MathLib Explorer

English

There exist integers a and b such that gcd x y = x·a + y·b (the extended gcd).

Русский

Существуют целые a и b такие, что gcd(x,y) = x·a + y·b (расширенный НОД).

LaTeX

$$$$\\gcd(x,y) = x \\cdot \\gcdA(x,y) + y \\cdot \\gcdB(x,y).$$$$

Lean4

/-- The extended GCD `a` value in the equation `gcd x y = x * a + y * b`. -/
def gcdA : ℤ → ℤ → ℤ
  | ofNat m, n => m.gcdA n.natAbs
  | -[m+1], n => -m.succ.gcdA n.natAbs

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

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

Разделы

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

Аффилиация

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