Solve a linear Diophantine equation ax + by = c

Solvable iff \(\gcd(a,b) \mid c\). The extended Euclidean algorithm gives one solution; every other is \(x_0 + t b/g,\ y_0 - t a/g\), so the steps are returned too.

Usage

Diophs(a, b, c)

Arguments

a, b, c

Integer coefficients; a and b not both zero.

Value

Named list with estimate, solvable, x, y, gcd, x_step, y_step, method.

References

Classical number theory; no single owning source.

Examples

Diophs(6, 9, 21)
#> $estimate
#> [1] 1
#> 
#> $solvable
#> [1] TRUE
#> 
#> $x
#> [1] -7
#> 
#> $y
#> [1] 7
#> 
#> $gcd
#> [1] 3
#> 
#> $x_step
#> [1] 3
#> 
#> $y_step
#> [1] -2
#> 
#> $method
#> [1] "linear Diophantine equation (extended Euclid)"
#>