I am entering an interesting team based math contest called the purple comet, and quite a lot of questions on this contest involve Diophantine equations. For this contest, you are given a computer, and I was thinking of making a program that solved a linear Diophantine equation. The issue with this is that I can barely solve one by hand, much less make a rigorous algorithm to solve one. I am aware of Euclid's algorithm, but when the numbers get big, this method gets pretty inefficient, not to mention that it would be kind of a nasty thing to program. Are there any other smart algorithms out there for solving a linear Diophantine equation?