Proof of a practical method of a natural number's equation

Question

Example Question :
$3m + 4n = 70$, $m,n$ are natural numbers. How many values can $m$ have?

I learned a method to solve this kind of problem, but I've never thought about that before.

for
n=1 => m=22
n=4 => m=18
.
.
n=16 => m=2

So n increase 3 by 3 and m decrease 4 by 4
How do we proof this works everytime?

Answer 1

You have the equation $3m + 4n = 70$ and you have an "initial" solution $(m_0, n_0) = (22, 1)$. How do we characterize all of the other solutions.

Subtract $3m_0 + 4n_0 = 70$ from $3m + 4n = 70$

\begin{array}{c} 3m &+ &4n &= &70 \\ 3m_0 &+ &4n_0 &= &70 \\ \hline 3(m-m_0) &+ &4(n-n_0) &= &0 \end{array}

So $3(m-m_0) = -4(n-n_0)$.

Since $3$ divides $3(m-m_0)$, then $3$ divides $-4(n-n_0)$.

Since $3$ and $4$ are relatively prime to each other, it follows that $3$ divides $n - n_0$

So, for some integer, $t$, $n-n_0 = 3t$.

Hence $n = n_0 + 3t$.

Substituting $n = n_0 + 3t$ into $3(m-m_0) = -4(n-n_0)$, we get

\begin{align} 3(m-m_0) &= -4(n-n_0) \\ 3(m-m_0) &= -4(n_0 + 3t -n_0) \\ 3(m-m_0) &= -12t \\ m - m_0 &= 4t \\ m &= m_0 - 4t \end{align}

So, in general, $(m, n) = (m_0 - 4t, n_0 + 3t)$.

To check that this works every time, you can substitute $(m, n) = (m_0 - 4t, n_0 + 3t)$ into $3m + 4n = 70$.

\begin{align} 3m + 4n &= 70 \\ 3(m_0 - 4t) + 4(n_0 + 3t) &= 70 \\ 3m_0 - 12t + 4n_0 + 12t &= 70 \\ 3m_0 + 4n_0 &= 70 \\ 70 &= 70 \end{align}

Answer 2

Once you have an initial solution, say $(m_0, n_0)$ such that

$3m_0 + 4n_0 = 70$

then you can add (or subtract) any multiple of $3$ to $n_0$ as long as you subtract (or add) the same multiple of $4$ from $m_0$. This is because

$3(m_0-4k) + 4(n_0+3k) = 3m_0-12k + 4n_0+12k = 3m_0 + 4n_0=70$