What are the different methods for solving a linear equation with integral Solutions? Which one is preferred over other? What is the best method?
For example, 3x + 5y = 12309834576, How do I find solutions to this equation? (Integral Solutions).
I have tried many google searches and pretty many documents and different methods like benzier etc. However couldn't decide which one is better.
I'm a computer science student, hence comparisons in terms of Order of Algorithms makes great sense to me.
On
$$ 3x + 5y = 12309834567 \Rightarrow x = \frac{12309834567 - 5y}{3} $$
but $$ x \in \Bbb Z \Rightarrow 1230983467 - 5y \equiv 0 \pmod 3 $$
$ 1230983467 \equiv 1 \pmod 3 $ and $ 5y \equiv -y \pmod 3 $
$$ \Rightarrow 1 + y \equiv 0 \pmod 3 \Rightarrow y \equiv -1 \equiv 2 \pmod 3 \Rightarrow y = 3n + 2 \Rightarrow x = 4103278186 - 5n $$
$$ 3(4103278186 - 5n) + 5(3n + 2 ) = 12309834567 $$
$$ x ,y \in \Bbb Z \Rightarrow n \in \mathbb{ Z} $$
$$ 3x + 5y = 12309834576=12309834576(3\cdot2-5)$$
$$\implies 3(x-12309834576\cdot2)=-5(y+12309834576)$$
$$\implies \frac{5(y+12309834576)}3=12309834576\cdot2-x(\text{ which is an integer as }x \text{ is})$$
$$\implies 3|5(y+12309834576)$$
$$\implies 3|(y+12309834576)\text{ as }(3,5)=1$$
$$\implies y+12309834576=3z$$ where $z$ is any integer