3
$\begingroup$

I was dealing with a childish problem, which eventually led to this:

Find integer $n$ and $m$ to fit the equation $6n=7m+1$

I immediately found first numbers by simple enumeration ($n=6$, $m=5$). But later I spent half of the day to figure out whether it's possible to have some general solution to the problem or at least any solution without manual enumeration.. I found nothing. So is it possible? Thanks!

$\endgroup$
  • $\begingroup$ anything is possible $\endgroup$ – john Jul 25 '15 at 15:55
  • 2
    $\begingroup$ If $(n_0,m_0)$ is a solution, then $(n_0+7,m_0+6)$ is also a solution. $\endgroup$ – Arthur Jul 25 '15 at 15:56
  • 2
    $\begingroup$ $6n - 7m = 1$ is linear diophantine equation. All solutions of these are $n=6 + 7t$, $y=5 + 6t$, $t\in\mathbb Z$ $\endgroup$ – Michael Galuza Jul 25 '15 at 15:57
  • $\begingroup$ $$6(n-m)=m+1$$ $$\frac{m+1}{(n-m)}=6$$ chek: $$if \ \ m,n \ \ odd$$ $$if \ \ m,n \ \ even$$ $$...$$ $\endgroup$ – Cardinal Jul 25 '15 at 15:59
  • 2
    $\begingroup$ $n=m=-1$ is the obvious solution from $7-6=1$ and getting the signs right. $\endgroup$ – Mark Bennet Jul 25 '15 at 16:02
12
$\begingroup$

The extended Euclidean algorithm does this for the general case.


With 6 and 7 in particular it is probably easier to note that $$ 7\cdot 1 + 6 \cdot (-1) = 1 $$ and rearrange this to $$ 6\cdot(-1) = 7\cdot(-1)+1 $$ If you want positive $n$ and $m$ (though you're just asking for integers, and $-1$ is a perfectly good integer), add $6\cdot 7$ to both sides of this, so you get $$ 6\cdot(7-1) = 7\cdot(6-1)+1 $$

$\endgroup$
1
$\begingroup$

If $\gcd(a,b)=1$ and $$ a x_0 - b y_0 = 1, $$ then any integer solution of: $$ a x - b y = 1 $$ is given by $x=x_0+kb,y=y_0+ka$. So if $(a,b)=(7,6)$, any integer solution of: $$ 7 x - 6 y = 1 $$ is given by $x=6k+1,y=7k+1$.

$\endgroup$
1
$\begingroup$

Since 6 and 7 are co-prime, your problem is solvable, to begin with. Now, just do a euclidean division between 6 and 7. Euclidean division is an algorithm for producing such Bézout relations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.