# Existence of solution for the diophantine equation $100x - 23y = -19$

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)

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