0
$\begingroup$

In order to solve the diophantine equation:

$$100x + (-23)y = -19$$

(from here)

we could use the theorem that :

The diophantine equation $ax+by=c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.

Well, $gcd(100,-23)=1$, therefore this equation couldn't have integer solutions. However, I used the euclidean algorithm and arrived at:

$$100 = 23*4 + 8 \\ 23 = 8*2 + 7\\ 8 = 7*1 + 1\\ 7 = 7*1 + 0$$ From this, we have that:

$$1 = 8 - 7\\ 7 = 23 - 8*2\\ 8 = 100 - 23*4$$

Therefore, substituting back in the GCD process we get:

$$1 = 8 - (23 - 8*2)\\ 1 = 100 - 23*4 - (23 - (100 - 23*4)*2)\\ 1 = 100 - 23*4 - 23 + 2*(100 - 23*4)\\ 1 = 100 - 23*4 - 23 + 2*100 - 2*23*4\\ 1 = 100*(1 + 2) + 23*(-4 - 1 - 8)\\ 1 = 100*3 + 23 (-13)\\ 1 = 100*3 - 23*13$$

Multiplying both sides by $-19$ get us to:

$$-19 = 100*(-3*19) - 23 (-13*19)\\ -19 = 100*(-57) - 23*(-247)$$

So (-57,-247) are a solution to the equation. However, $gcd(100,-23)$ does not divide $19$. Also, this made me think that in general:

if $gcd(a,b)=1$, then there exists integers $m,n$ such that:

$$am+bn=1\implies a(cm)+b(cn)=c$$

So, always in the equation:

$ax+by=c$

when $gcd(a,b)=1$ I can get the form:

$ax+by=1$

and then multiply by $c$ to find the integer solutions.

I think i'm doing something terribly wrong.

OH NO, WAIT! $GCD(100,-23)$ DIVIDES $19$, RIGHT??? :O

(i'm gonna leave this here to help someone since I typed all this)

$\endgroup$
1
$\begingroup$

As you seem to have noticed, $1$ does divide $-19$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.