Fungrim home page

Fungrim entry: 5daceb

Symbol: XGCD xgcd ⁣(a,b)\operatorname{xgcd}\!\left(a, b\right) Extended greatest common divisor
Domain Codomain
aZ  and  bZa \in \mathbb{Z} \;\mathbin{\operatorname{and}}\; b \in \mathbb{Z} dZ0  and  uZ  and  vZ   where (d,u,v)=xgcd ⁣(a,b)d \in \mathbb{Z}_{\ge 0} \;\mathbin{\operatorname{and}}\; u \in \mathbb{Z} \;\mathbin{\operatorname{and}}\; v \in \mathbb{Z}\; \text{ where } \left(d, u, v\right) = \operatorname{xgcd}\!\left(a, b\right)
Table data: (P,Q)\left(P, Q\right) such that (P)    (Q)\left(P\right) \implies \left(Q\right)
Fungrim symbol Notation Short description
XGCDxgcd ⁣(a,b)\operatorname{xgcd}\!\left(a, b\right) Extended greatest common divisor
ZZZ\mathbb{Z} Integers
ZZGreaterEqualZn\mathbb{Z}_{\ge n} Integers greater than or equal to n
Source code for this entry:
    SymbolDefinition(XGCD, XGCD(a, b), "Extended greatest common divisor"),
    Table(TableRelation(Tuple(P, Q), Implies(P, Q)), TableHeadings(Description("Domain"), Description("Codomain")), List(Tuple(And(Element(a, ZZ), Element(b, ZZ)), Where(And(Element(d, ZZGreaterEqual(0)), Element(u, ZZ), Element(v, ZZ)), Equal(Tuple(d, u, v), XGCD(a, b)))))))

Topics using this entry

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2020-04-08 16:14:44.404316 UTC