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

4 Answers 4

up vote 14 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
2  
$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
1  
Remark $\:$ This is a special case of general methods (Hermite / Smith) for triangularizing or diagonalizing matrices to normal form over Euclidean domains - see my answer here. –  Bill Dubuque Mar 25 '12 at 18:00
1  
Rob, this is an awesome reference. Thank you. –  Pedro Tamaroff May 17 '13 at 17:45

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

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
    
Applying EEA here is akin to opening chestnuts with a sledghammer! –  Bill Dubuque Sep 27 '11 at 18:25

Your Answer

 
discard

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.