Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
If you type in ExtendedGCD[100, 23], Wolfram Alpha will respond $\{1, \{3, -13\}\}$ Which means that the GCD of $100$ and $23$ is $1$ and that $3(100)-13(23) = 1$ Multiply both sides by -19 and you get a particular solution. Don't abuse this function! You still need to learn how to do it correctly. –  Steven Gregory May 15 at 21:29

6 Answers 6

up vote 20 down vote accepted

$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$.

share|improve this answer
Wow, thanks for the fast response! I followed you all the way up until '100x = -19 (mod 23)' went to '8x = 4 (mod 23)'. Can you explain that a little more? –  Mike Sep 27 '11 at 18:11
$100=4\cdot 23+8$ and $-19=4+(-1)\cdot 23$ –  Ross Millikan Sep 27 '11 at 18:18

Using the Euclid-Wallis algorithm (described below) $$ \begin{array}{r} &&4&2&1&7\\\hline 1&0&1&-2&3&-23\\ 0&1&-4&9&-13&100\\ 100&23&8&7&1&0\\ &&&&{\uparrow}&{\star} \end{array} $$ lookng below the horizotal line, the top row times $100$ plus the middle row times $23$ equals the bottom row. Therefore, the arrow column says that $$ 3\cdot100-13\cdot23=1 $$ Furthermore, the top and middle numbers in each column are relatively prime. Therefore, the star column gives the smallest combination of $100$ and $23$ that equals $0$. Add arbitrary multiples of the star column to a particular multiple of the arrow column to get all solutions for a particular problem. Since we want a result of $-19$, add arbitrary multiples of the star column to $-19$ times the arrow column: $$ \begin{align} -19&=(-19\cdot3-23k)100+(-19\cdot-13+100k)23\\ &=(-57-23k)100+(247+100k)23 \end{align} $$ This gives all the integer solutions. Thus, $x=-57-23k=12-23(k+3)=12+23n$ where $n=-k-3$.

Euclid-Wallis Algorithm

This algorithm computes $\gcd(m,n)$, solves the Diophantine equation $mx + ny = \gcd(m,n)$, and yields the continued fraction for $m/n$.

Start with the two columns $$ \begin{array}{r} 1&0\\ 0&1\\ m&n\\ \end{array}\tag{1} $$ Above each successive column write down the floor of the quotient of the base of the previous column divided into the base of the column before that, then compute the next column by subtracting that number times the previous column from the column before that.

Let us work an example; $m = 17, n = 23$: $$ \newcommand{\nextq}[2]{\leftarrow\lfloor\color{##00A000}{#1}/\color{##0000FF}{#2}\rfloor} \newcommand{\euclid}[3]{{\leftarrow}\color{##00A000}{#1}-\color{orange}{#3}\cdot\color{##0000FF}{#2}} \begin{array}{rcl} \begin{array}{l} \color{#C00000}{\text{Above each successive column}}\\ \text{write down the floor of the}\\ \text{quotient of }\color{#0000FF}{\text{the base of the}}\\ \color{#0000FF}{\text{previous column}}\text{ divided into }\color{#00A000}{\text{the}}\\ \color{#00A000}{\text{base of the column before that}} \end{array} && \begin{array}{l} \text{Compute }\color{#C00000}{\text{the next column}}\text{ by}\\ \text{subtracting }\color{orange}{\text{that number}}\text{ times}\\ \color{#0000FF}{\text{the previous column}}\text{ from }\color{#00A000}{\text{the}}\\ \color{#00A000}{\text{column before that}}\\ \text{} \end{array}\\ \begin{array}{rrrl} & & \color{#C00000}{0} & \nextq{17}{23}\\ \hline 1 & 0 \\ 0 & 1 \\ \color{#00A000}{17} & \color{#0000FF}{23} \end{array} &\rightarrow& \begin{array}{rrrl} & & \color{orange}{0}\\ \hline \color{#00A000}{1} & \color{#0000FF}{0} & \color{#C00000}{1} & \euclid{1}{0}{0} \\ \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{0} & \euclid{0}{1}{0} \\ \color{#00A000}{17} & \color{#0000FF}{23} & \color{#C00000}{17} & \euclid{17}{23}{0} \end{array}\\ &\swarrow&\\ \begin{array}{rrrrl} & & 0 & \color{#C00000}{1} & \nextq{23}{17} \\ \hline 1 & 0 & 1 \\ 0 & 1 & 0 \\ 17 & \color{#00A000}{23} & \color{#0000FF}{17} \end{array} &\rightarrow& \begin{array}{rrrrl} & & 0 & \color{orange}{1} \\ \hline 1 & \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{-1} & \euclid{0}{1}{1} \\ 0 & \color{#00A000}{1} & \color{#0000FF}{0} & \color{#C00000}{1} & \euclid{1}{0}{1} \\ 17 & \color{#00A000}{23} & \color{#0000FF}{17} & \color{#C00000}{6} & \euclid{23}{17}{1} \end{array}\\ &\swarrow&\\ \begin{array}{rrrrrl} & & 0 & 1 & \color{#C00000}{2} &\nextq{17}{6} \\ \hline 1 & 0 & 1 & -1 \\ 0 & 1 & 0 & 1 \\ 17 & 23 & \color{#00A000}{17} & \color{#0000FF}{6} \end{array} &\rightarrow& \begin{array}{rrrrrl} & & 0 & 1 & \color{orange}{2} \\ \hline 1 & 0 & \color{#00A000}{1} & \color{#0000FF}{-1} & \color{#C00000}{3} & \euclid{1}{-1}{2} \\ 0 & 1 & \color{#00A000}{0} & \color{#0000FF}{1} & \color{#C00000}{-2} & \euclid{0}{1}{2} \\ 17 & 23 & \color{#00A000}{17} & \color{#0000FF}{6} & \color{#C00000}{5} & \euclid{17}{6}{2} \end{array} \end{array}\\ \vdots $$ $$ \begin{array}{rrrrrrr} &&\color{orange}{0}&\color{orange}{1}&\color{orange}{2}&\color{orange}{1}&\color{orange}{5}\\ \hline \color{#00A000}{1}&\color{#00A000}{0}& 1&-1& 3&\color{#C00000}{-4}&\color{#0000FF}{23}\\ \color{#00A000}{0}& \color{#00A000}{1}& 0&1&-2&\color{#C00000}{3}&\color{#0000FF}{-17}\\ \color{#00A000}{17}&\color{#00A000}{23}&17& 6& 5& \color{#C00000}{1}&\color{#0000FF}{0} \end{array}\tag{2} $$ The red column (preceding the blue one with $0$ at its base) has $\gcd(m,n)$ at its base. Also, $m$ times the top row plus $n$ times the middle row equals the bottom row. Thus, the red column (with $\gcd(m,n)$ at its base) has the coefficients for $mx + ny = \gcd(m,n)$ in the top two rows.

Also, the blue column (with $0$ at its base) has the smallest non-zero solution to $mx + ny = 0$. Multiples of this solution can be added to a particular solution of $mx + ny = k$ to get all solutions.

The orange quotients above the columns yield the continued fraction for $m/n$.

Thus, $$\gcd(\color{#00A000}{17},\color{#00A000}{23}) = \color{#C00000}{1}\\ (\color{#C00000}{-4}\color{#0000FF}{+23}k)\color{#00A000}{17} + (\color{#C00000}{3}\color{#0000FF}{-17}k)\color{#00A000}{23} = \color{#C00000}{1}$$ and the continued fraction for $\color{#00A000}{17}/\color{#00A000}{23}$ is $[\color{orange}{0},\color{orange}{1},\color{orange}{2},\color{orange}{1},\color{orange}{5}]$.

Euclidean Algorithm (plus bookkeeping)

The algorithm above is simply the Euclidean algorithm in the top and bottom rows, with some bookkeeping in the two middle rows. The quotients are in the top row and the remainders (which, as dictated by the Euclidean Algorithm, later become divisors and then dividends) are in the bottom row.

In $(2)$, the first dividend is $17$ and the first divisor is $23$. The first quotient is $0$ and the remainder is $17$. In the next pass, the dividend is $23$ (which was the previous divisor) and the divisor is $17$ (which was the previous remainder). The second quotient is $1$ and the remainder is $6$. In the third pass the dividend is $17$ and the divisor is $6$, which yields a quotient of $2$ and a remainder of $5$. This proceeds until a remainder of $0$ appears. The algorithm has to stop here since the next divisor would be $0$.

The bookkeeping in the middle two rows mimics the computation performed in the bottom row. That is, below the line, the third column is first column minus $0$ times the second column. The fourth column is the second column minus $1$ times the third column. The fifth column is the third column minus two times the fourth column. This bookkeeping assures that the first row below the line times $17$ plus the second row times $23$ equals the bottom row. This allows us to back out the Euclidean algorithm at the same time we are performing it.

share|improve this answer
Rob, this is an awesome reference. Thank you. –  Pedro Tamaroff May 17 '13 at 17:45
See here for a natural viewpoint as elimination by row-reduction. This is a special case of general methods (Hermite / Smith) for triangularizing or diagonalizing matrices to normal form over Euclidean domains. –  Bill Dubuque Mar 4 at 15:02

HINT $\displaystyle\rm\ \ mod\ 23:\ x\: \equiv\: \frac{-19}{100}\: \equiv\: \frac{4}{100}\: \equiv\: \frac{1}{25}\: \equiv\: \frac{24}{2}\: \equiv\: 12\:,\ $ i.e. $\rm\ x\: =\: 12 + 23\ n\:.$

share|improve this answer
Beware $ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion. –  Bill Dubuque Mar 4 at 14:53

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

share|improve this answer

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.

   |100   1    0
-4 | 23   0    1
-3 |  8   1   -4
   | -1  -3   13
   |  1   3  -13

and we conclude that 3(100)-13(23) = 1

share|improve this answer

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.$$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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