# Given two coprime integers, find multiples of them that differ by 1

I'll describe the problem with an example.

Find integers $n$ and $m$ such that $n\cdot13 + m\cdot101 = 1$.

This is the same as solving the equation $n\cdot13 \equiv 1 \pmod {101}$

I'm revising for a maths exam in a few days and it seems like a lot of the questions and examples rely on an ability to solve this type of problem. I can't seem to find a method in my notes, the solutions just get plucked out of thin air!

What is a neat way of doing it on pen and paper with a calculator?

-
Run Euclid's algorithm. Then reverse it. See here: en.wikipedia.org/wiki/… –  Matt May 22 '12 at 21:24
In fact, with careful bookkeeping you can keep track of things as you go and not need to run in reverse; this is widely known as the Extended Euclidean algorithm and there are a ton of references for it out on the web (e.g., en.wikipedia.org/wiki/Extended_Euclidean_algorithm ). –  Steven Stadnicki May 22 '12 at 23:17
add comment

## 3 Answers

One way is the extended Euclidean algorithm. This can be done in analogy to Gaussian elimination or triangularization, except that, since the coefficient ring is not a field, one has to use the division / Euclidean algorithm to to iteratively descrease the coefficients till zero. Augmenting (appending) an identity matrix will accumulate the effect of the elementary operations, hence yielding the sought Bezout equation. Below is an example from one of my old posts. It computes the Bezout representation for $\rm\:gcd(80,62) = 2\$ viz. $\ 7\cdot 80\: -\: 9\cdot 62\ =\ 2\:.\:$

For example, to solve  m x + n y = gcd(m,n) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

in equation form   | in row form
---------------------+------------
80 =   1(80) + 0(62) | 80   1   0
62 =   0(80) + 1(62) | 62   0   1
row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
row4 - 4 row5  ->   0 = -31(80) -40(62) |  0 -31  40

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
|    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.


In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as 1, and is multiplied by each elementary row operation,
hence it accumulates the product of all the row operations, namely:


$$\left[ \begin{array}{ccc} 7 & -9\\ -31 & 40\end{array}\right ] \left[ \begin{array}{ccc} 80 & 1 & 0\\ 62 & 0 & 1\end{array}\right ] \ =\ \left[ \begin{array}{ccc} 2 & 7 & -9\\ 0 & -31 & 40\end{array}\right ]\qquad\qquad\$$

Notice row 1 is the particular  solution  2 =   7(80) -  9(62)
Notice row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

-
add comment

NOTE: This is exactly the same as the Extended Euclidean algorithm. I wouldn't lie to you. Look me up on Facebook, I have a trustworthy face. Dogs love me.

What I do is write the simple continued fraction, in this case for $\frac{101}{13}.$ The convergents, including the fake one $\frac{1}{0}$ that always goes in the second position, are $$\frac{0}{1}, \; \frac{1}{0}, \; ((7)), \; \frac{7}{1}, \; ((1)), \; \frac{8}{1}, \; ((3)), \; \frac{31}{4}, \; ((3)), \; \frac{101}{13}.$$ I put the "digits" in double parentheses.

The crossed product of two consecutive convergents, a little 2 by 2 determinant, is always $\pm 1,$ as you can see from $8 \cdot 4 - 31 \cdot 1 = 1,$ then $31 \cdot 13 - 101 \cdot 4 = -1.$

So $$-31 \cdot 13 + 4 \cdot 101 = 1.$$

See FRAC and the rest of the article, really. This method is the same information as the Euclidean algorithm but, after practice, takes little room to write. Anyway, I'm accustomed to it.

-
I'd missed the pencil-and-paper aspect of the original question; I usually think of extended Euclid as a computer algorithm, but this looks like a great way of handling it on paper. –  Steven Stadnicki May 22 '12 at 23:29
@Steven, right. Unless the numbers are huge, I just have the calculator take the fractional part and then reciprocal. If doing it with decimal numbers on a calculator, you just need to realize that at some point either 2.999999 or 3.000001 will show up, and either way make 3 the final "digit." Also, this is exactly how I do extended Euclid in my own C++ programs. Instead of decimal, it is integer arithmetic at every step. –  Will Jagy May 22 '12 at 23:36
add comment

Here is the "Gaussian elimination" method of obtaining the result. Begin with three columns, the first columns and two lines, representing your two numbers:

 101    1    0
13    0    1


Now, adding $-7$ times the second row to the first row we get:

 101    1    0
13    0    1
10    1   -7


Now you can subtract 10 times the third row from the first to get a $1$ in the first column

101     1    0
13     0    1
10     1   -7
1    -9   70


So we obtain that $1 = -9(101) + 70(13)$. Indeed, $70(13) - 9(101) = 910 - 909 = 1$.

-
add comment