# Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem:

Find integers $m$ and $n$ such that $14m+13n=7$.

Where I Am:

I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and $n$ in terms of some arbitrary integer through modular arithmetic, like so:

$$14m-7 \equiv 0 \pmod {13} \iff 14m \equiv 7 \pmod {13}$$ $$\iff m \equiv 7 \pmod {13}$$ $$\iff m=7+13k \text{, for some integer }k.$$

And repeating the same process for $n$, yielding

$$n=-7(2k+1) \text{, for some integer } k.$$

I then tried plugging these in to the original equation, thinking that I only have one variable, $k$, to solve for, but they just ended up canceling. The only way I can think to proceed from here is brute force, but I imagine there's a more elegant way to go about this. Any help would be appreciated here.

• Your values statistify for all $k$. – wythagoras May 7 '15 at 17:44

If $14x+13y=1$ then multiplying by $7$ gives $14(7x)+13(7y)=7.$

• Note that for an initial solution of $14x+13y=1$ you can use simply $(x,y)=(1,-1).$ Then the general solution is $x=1+13t,y=-1-14t$ using the usual method of completely solving linear two variable equations. – coffeemath May 7 '15 at 18:25
• The previous comment was for the general solution to $14x+13y=1.$ After the multiplication to get $7$ on the right side, the general solution to $14x+13y=7$ becomes $x=7+13u, y=-7-14u.$ – coffeemath May 7 '15 at 18:31

How about, find integers $p,q$ with $14p+13q=1$ and then choose $m=7p, n=7q$, which method shows that the general problem of this kind can be solved.

Find $m$ and $n$ such that $14m + 13n = 1$ and then multiply them both by $7$.

• Such that $14m + 13n = 1$? – Brian Tung May 7 '15 at 17:49

If you can solve for $1$, how can you use this to now solve for $7$ ?

Hint $\$ The set $S$ of integers of the form $\,14m+13n,\ m,n\in\Bbb Z$ are closed under $\color{#c00}{\rm subtraction}$ and closed under $\color{#0a0}{\rm multiplication}$ by any integer. Thus $\,14,13\in S\,\color{#c00}{\Rightarrow \_\_\in S}$ $\,\color{#0a0}{\Rightarrow\ \_\_ \in S}$

Remark $\$ This is the key idea behind the use of the Extended Euclidean Algorithm to compute the Bezout identity for the gcd (see here).

You can use Extended Euclidean Algorithm (EEA) to find integers $x,y$ such that $14x+13y=1$, which exist by Bezout because $(14,13)=1$. I use EEA here as shown in this answer.

$\begin{array}{l|r}&14&14(1)& 13(0)\\\hline &13 & 14(0)& 13(1)\\\hline 14-13(1)& 1&14(1)&13(-1)\end{array}$

So $1\!=\!14(1)\!+\!13(-1)$. Now multiply by $7$ to get $7\!=\!14(7)\!+\!13(-7)$.

It is obvious here without any algorithms that $(x,y)=(1,\!-1)$ works, but it is better to generalize.

you can find $m_0$ and $n_0$ such that: $$14m+13n=0$$
By using the Extended Euclidean table ($m_0=-13$ and $n_0=14$)

Then, using the same method you can find $m_1$ and $n_1$ such that: $$14m+13n=1$$ Giving ($m_1=1$ and $n_1=-1$)

Finally, you can find the set of solutions to $14m+13n=7$ by selecting:
$$m=7m_1+km_0$$ $$n=7n_1+kn_0$$for some k $\in \Bbb R$

This is all the solutions because the values $7m_1$ and $7n_1$ give the solution to $$14m+13n=7$$ and $m_0$ and $n_0$ give the solution to $$14m+13n=0$$ and the addition of these two will always be $7$

$14m+13n=7\iff13(m+n)+m=7=13-6\iff m_0=-6$, and $m+n=1\iff$ $n_0=1-m_0=1+6=7$. Now that you have an initial solution, I'm sure that you can find out the others. :-$)$