ExtendedGreatestCommonDivisorI function

  • Article

Warning

This documentation refers to the Classic QDK, which has been replaced by the Modern QDK.

Please see https://aka.ms/qdk.api for the API documentation for the Modern QDK.

Namespace: Microsoft.Quantum.Math

Package: Microsoft.Quantum.Standard

Returns the GCD of two integers, decomposed into a linear combination.

function ExtendedGreatestCommonDivisorI (a : Int, b : Int) : (Int, Int)

Description

Computes a tuple $(u,v)$ such that $u \cdot a + v \cdot b = \operatorname{GCD}(a, b)$, where $\operatorname{GCD}$ is $a$ greatest common divisor of $a$ and $b$. The GCD is always positive.

Input

a : Int

the first number of which extended greatest common divisor is being computed

b : Int

the second number of which extended greatest common divisor is being computed

Output : (Int,Int)

Tuple $(u,v)$ with the property $u \cdot a + v \cdot b = \operatorname{GCD}(a, b)$.

References