diophantine

Documentation

Index

• func ComputeLinearDiophantine[T constraints.Integer](a, b, c T) (hasSolutions bool, gcd T, x, y int)
• func ExtendedEuclideanAlgorithm[T constraints.Integer](a, b T) (gcd T, x, y int)

Functions

func ComputeLinearDiophantine

func ComputeLinearDiophantine[T constraints.Integer](a, b, c T) (hasSolutions bool, gcd T, x, y int)

See https://cp-algorithms.com/algebra/linear-diophantine-equation.html#algorithmic-solution Given ax+by=c returns: - if it has solutions (zero or infinite) - gcd(a,b) - one solution

func ExtendedEuclideanAlgorithm

func ExtendedEuclideanAlgorithm[T constraints.Integer](a, b T) (gcd T, x, y int)

gcd can be negative source: https://cp-algorithms.com/algebra/extended-euclid-algorithm.html#algorithm Assumptions: - At least one != 0