Linear diophantine equation

155 Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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.