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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 '15 at 21:29
up vote 21 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|cite|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

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|cite|improve this answer

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|cite|improve this answer
1  
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 '15 at 14:53

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|cite|improve this answer
3  
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 '15 at 15:02

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|cite|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|cite|improve this answer

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

share|cite|improve this answer
    
Please see this tutorial on how to typeset mathematics on this site. – N. F. Taussig Sep 28 '15 at 18:40
    
You made a typographical error in your final line. $23n + 69 - 57 = 23n \color{red}{+} 12$. – N. F. Taussig Sep 28 '15 at 18:41
    
Thanks for the note -- hopefully things are ok now – The Headless Mathematician Sep 28 '15 at 18:44
    
Thanks for the formatting help too. I think you and I tried to add formatting at the same time, but it seems to have ended up ok. – The Headless Mathematician Sep 28 '15 at 18:53

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

enter image description here

share|cite|improve this answer

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.