A Generalization Euclidean Algorithm Approach for Solving Multi-Variable Linear Diophantine Equations - Ikhsan Abdul Ro'uf; Hery Susanto; I Made Sulandra (Mathematics Department, Maulana Malik Ibrahim State Islamic University of Malang, 2026)
Multi-variable linear Diophantine equations of the form a1x1 + a2x2 + + anxn = b, where ai, 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(a1, a2, , an) 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(a1, a2, , an), followed by a back-substitution process through the algorithm's steps to express the greatest common divisor as a linear combination of a1, a2, , an. This linear combination is then multiplied by b/gcd(a1, a2, , an) to obtain a particular solution of the equation. Finally, the general solution is constructed from the resulting particular solution.