Linear diophantine equation $100x - 23y = -19$ I need help with this equation: $$100x - 23y = -19.$$  When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem to figure out how they got to that answer.
 A: If you take the equation mod $23$, you find $8x \equiv 4 \pmod{23}$ and by inspection, this is satisfied by $x \equiv 12 \pmod{23}$.  To find this, you use the Extended Euclidean algorithm
A: $100x -23y = -19$ if and only if $23y = 100x+19$, if and only if $100x+19$ is divisible by $23$. Using modular arithmetic, you have
$$\begin{align*}
100x + 19\equiv 0\pmod{23}&\Longleftrightarrow 100x\equiv -19\pmod{23}\\
&\Longleftrightarrow 8x \equiv 4\pmod{23}\\
&\Longleftrightarrow 2x\equiv 1\pmod{23}\\
&\Longleftrightarrow x\equiv 12\pmod{23}.
\end{align*}$$
so $x=12+23n$ for some integer $n$. 
A: I find this version of the Euclid-Wallis Algoritmn a bit more user friendly.
robjohn did a great job of explaining how it works so I offer this with no further explaination. Please note that I put the multiplier next to the row
that gets multiplied by it. Also note that I multiply and then add, so my multipliers have a different sign than his. It's really the same thing, I just think this way is a bit more transparent. I also omitted the $``0"$ row. I don't think it's worth the effort used to calculate it.
                   interpretation
   |100   1    0   100 =  1(100) +  0(23)
-4 | 23   0    1    23 =  0(100) +  1(23)
-3 |  8   1   -4     8 =  1(100) -  4(23)
   | -1  -3   13    -1 = -3(100) + 13(23)
   |  1   3  -13     1 =  3(100) - 13(23)

and we conclude that 3(100)-13(23) = 1
Hence a solution to $100x - 23y = 1$ is $(x,y)=(3, -13)$
Myltiply through by $-19$ and you get
$$ 100(-57) + 23(247) = -19$$
Not pretty, but it's a start.
To find a general solution to $100x + 23y = -19$, you need to solve
$100x + 23y = 100(-57) + 23(247)$
$100(x+57) = 23(247-y)$
Because $100$ and $23$ are relatively prime, we must have
$x + 57 = 23k$ and $247-y = 100k$ for any $k \in \mathbb Z$
so $x = 23k-57$ and $y=247 - 100k$
If you think that $-57$ and $247$ are too ugly, you can mess with the equation some.
I would try substituting $k = s + 2$ to change the $247$ to a $47$.
$x = 23(s+2)-57$ and $y=247 - 100(s+2)$
which simplifies to
$x = 23s-11$ and $y=47 - 100s$
A: The continued fraction solution goes as follows:
Expand 100/23 into a continued fraction (I'm essentially using the GCD algorithm):
\begin{align*}
\frac{100}{23} & = 4 + \frac{8}{23}\\
               & = 4 + \frac{1}{\frac{23}{8}}\\
               & = 4 + \cfrac{1}{2 + \cfrac{7}{8}}\\
               & = 4 + \cfrac{1}{2 + \cfrac{1}{\frac{8}{7}}}\\
               & = 4 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{7}}}
\end{align*} 
Now that all the numerators are $1$, you're done getting the continued fraction, often written as the list of partial quotients like this:
$100/23 = [4,2,1,7]$
You can of course check: $4 + 1/(2 + 1/(1 + 1/7)) = 100/23$, the last equation above.  You can change the $7$ at the end to $6 + 1/1$ to get an odd number of partial quotients but you don't have to.
Now if you look at $[4,2,1]$, which is the next to last convergent (the last being $[4,2,1,7]=100/23$) you get
$$4 + \frac{1}{2 + \frac{1}{1}} = \frac{13}{3}$$
The difference of cross product of the numerators and denominators of successive convergents is always $+1$ or $-1$, i.e:
$$100 \cdot 3 - 13 \cdot 23 = 1$$
If we multiply though by $-19$ we get:
$$100 \cdot (3 \cdot -19) - 23 \cdot (13 \cdot -19) = -19$$
so a particular solution $x_0,y_0$ is
\begin{align*}
x_0 & = 3 \cdot -19 = -57\\
y_0 & = 13 \cdot -19 = -247
\end{align*}
Since for all integer $t$
$$100 \cdot 23t  -  23 \cdot 100t = 0$$
we can add that equation to
$$100 \cdot -57   -  23 \cdot -247 = -19$$
and get
$$100(23t-57) - 23(100t-247) = -19$$
so the general solution is
\begin{align*}
x & = 23t - 57\\
y & = 100t - 247
\end{align*}
To get the exact Wolfram answer change variables to $n = t-3$
$$x = 23(n+3)-57 = 23n+69-57 = 23n + 12$$
A: [For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]
The manipulations performed from steps (0) to (16) were designed to create the linear system of equations (0a), (5a), (11a) and (16a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (16a)).
Equation (0a) is given. It is possible to infer equations (5a), (11a) and (16a) from (5), (11) and (16) respectively without performing manipulations (0) to (16) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor. Stop when the absolute value of a coefficient of the latest equation added is 1.
Then proceed to solve the linear system of equations.

A: $\!\overbrace{\bmod  23\!:\ 100x\equiv -19}^{\textstyle\ \ \ \ {-}23y+100x = -19}\!\iff\! x \equiv \dfrac{\!-19}{100} \equiv \dfrac{4}{100} \equiv \dfrac{1}{25} \equiv\dfrac{24}{2}\equiv 12,\ $ i.e. $\ x = 12 + 23 n$
Just as above, using modular fraction arithmetic often greatly simplifies solving  linear congruences, e.g.  see here, and here and here for circa $20$ motley worked examples via a handful of methods (and see the sidebar "Linked" questions lists there for many more).
A: if you put $x=23n+12 $ into equation $100x-23y=-19$ you will have $y$ as a linear function of $n$ 
  then you can put various n and find (x,y) such that x,y are solution of equation 
$$ x=23n+12 \\100(23n+12)-23y=-19\\100(23n)+1200-23y=-19\\23y=100(23n)+1219$$ divide by $23$  $$y=100n+53$$ so $$n\in \mathbb{Z}\\\left\{\begin{matrix}
x=23n+12\\ 
y=100n+53
\end{matrix}\right.$$
A: For equation $100x - 23y = -19$, I use scaling method.
GCD(100,79) calculation numbers, in reversed order:  
1
7  → -floor(1/7*8) = -1 = inverse of 7 (mod 8)
8 → -floor(-1/8*23) = 3 = inverse of 8 (mod 23)
23 → -floor(3/23*100) = -13 = inverse of 23 (mod 100)
100
Mod    23 : $ 100x ≡ -19 → x≡ (-19)(100^{-1})≡ (4)(8^{-1})≡ (4)(3)≡ 12 $
Mod 100 : $ -23y≡ -19 → y≡ (19)(23^{-1})≡ (19)(-13)≡ -247≡ 53 $ 

Another way is by guessing a multiplier.  This work best for prime modulo.
For composite modulo, multiplier had to confirm co-prime to the modulo.  
$100x ≡ -19 \text{ (mod 23)}$ 
${100 \over 23} ≈ 4.3478 ≈ {13 \over 3}$.  Multiply both side by 3, we get:
$$300x ≡ x ≡ -19\times 3 ≡ 12 \text{ (mod 23)}$$
