# Linear diophantine equation

a) $$130x + 143y = 5957$$
b) $$44x + 19y = 75$$

the theorem says ax + by = c has solution if and only if d | c

however I work out both question with no solution as

a)

$$143 = 130 . 1 + 13$$
$$130 = 13 . 10 + 0$$

and 5957 is unable to be divided by 13 therefore no solution exists.

b)

$$44 = 19 . 2 + 6$$
$$19 = 6 . 3 + 1$$
$$6 = 3 . 2 + 0$$

for b) I am unsure if there are any solution exists?

-
Can you try to clean up your question please? It is hard for me to tell exactly what you are doing and what you are asking, without simply assuming that you are trying to apply Bezout's identity and getting stuck somewhere. – Alex Becker May 1 '11 at 6:31

Your first problem is correct.

Your second one, however, is not. When doing the Euclidean Algorithm, you mess up between your second and third steps. From $19 = 6*3 + 1$, you should go on the next next step $6 = 1*6 + 0$, indicating that 1 is the gcd of 19 and 44.

Let's also consider for a moment what your solution said: it said that either 2 or 3 divided both 44 and 19 (neither of which are correct). We also know that 19 is prime, so unless 44 is a multiple of 19 (which it isn't), they share no factors.

With that, it turns out that there are infinitely many solutions.

-
ops. mistake in b) for my euclidean algorithm. if 1 is the common divisor which means there are no common divisor? – optimus May 1 '11 at 6:38
@liangteh: No, it means that 1 is the common divisor. – mixedmath May 1 '11 at 6:43
in this case, for gcd = 1 how do I derive the general solution and particular solution? – optimus May 1 '11 at 6:46
@Liangteh: I will not do your homework for you, but I will do a quick example. Consider the numbers 3 and 8. $8 = 3*2 + 2$, and $3 = 2 * 1 + 1$. So 1 is the gcd. But then, by reversing my equations, I get that $1 = 3 - 2(1) = 3 - (8 - 3(2)) = 3*(3) - 8*(1)$. So I have a solution. – mixedmath May 1 '11 at 6:52