Essential Number Theory and Linear Algebra Algorithms
Number Theory Fundamentals Extended Euclidean Algorithm and Linear Diophantine Equations For integers a and b, the equation ax + by = d has integer solutions if and only if the greatest common divisor gcd(a, b) divides d. This is known as Bézout's Identity. The extended Euclidean algorithm alows us...