A Generalization Euclidean Algorithm Approach for Solving Multi-Variable Linear Diophantine Equations

Abstract

Multi-variable linear Diophantine equations of the form a₁x₁ + a₂x₂ + ··· + a_nx_n = b, where a_i, b ∈ Z, have various applications in many fields, including cryptography, chemistry, and statistics, where they can be used to determine public and private keys, balance chemical equations, and model scheduling problems, respectively. The equation has infinitely many integer solutions if gcd(a₁, a₂, …, a_n) divides b. Two well-known algorithms for finding solutions are the Smith normal form and integer lattice methods. This paper presents an alternative approach for obtaining the general solution of the equation. The proposed method applies the generalized Euclidean algorithm to compute gcd(a₁, a₂, …, a_n), followed by a back-substitution process through the algorithm's steps to express the greatest common divisor as a linear combination of a₁, a₂, …, a_n. This linear combination is then multiplied by b/gcd(a₁, a₂, …, a_n) to obtain a particular solution of the equation. Finally, the general solution is constructed from the resulting particular solution.