ExtendedGreatestCommonDivisorL function
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 ExtendedGreatestCommonDivisorL (a : BigInt, b : BigInt) : (BigInt, BigInt)
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 : BigInt
the first number of which extended greatest common divisor is being computed
b : BigInt
the second number of which extended greatest common divisor is being computed
Output : (BigInt,BigInt)
Tuple $(u,v)$ with the property $u \cdot a + v \cdot b = \operatorname{GCD}(a, b)$.
References
- This implementation is according to https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Feedback
https://aka.ms/ContentUserFeedback.
Coming soon: Throughout 2024 we will be phasing out GitHub Issues as the feedback mechanism for content and replacing it with a new feedback system. For more information see:Submit and view feedback for