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?

  • $\begingroup$ See stackoverflow.com/questions/4917003/…. $\endgroup$ – user122283 Mar 22 '14 at 22:50
  • $\begingroup$ @SanathDevalapurkar, Wow, thanks. Guess I didn't look hard enough. Is it considered a duplicate if it's asked on a different branch of stack exchange? If so, I'll gladly vote to close. $\endgroup$ – recursive recursion Mar 22 '14 at 22:54
  • $\begingroup$ No, it isn't considered a duplicate if it's asked on a different branch of stack exchange. $\endgroup$ – user122283 Mar 22 '14 at 22:55
  • $\begingroup$ @SanathDevalapurkar, Great! In any case, I'd kind of like 3 or 4 algorithms so that I can test them out and see which one is more efficient, though I know that's asking for a bit much. $\endgroup$ – recursive recursion Mar 22 '14 at 22:57
  • $\begingroup$ Are you really a middle-schooler? I am just curious, because I am 13, and in middle-school, too. $\endgroup$ – user122283 Mar 22 '14 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.