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$
5
  • $\begingroup$ anything is possible $\endgroup$
    – john
    Commented Jul 25, 2015 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
    Commented Jul 25, 2015 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$ Commented Jul 25, 2015 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
    Commented Jul 25, 2015 at 15:59
  • 2
    $\begingroup$ $n=m=-1$ is the obvious solution from $7-6=1$ and getting the signs right. $\endgroup$ Commented Jul 25, 2015 at 16:02

3 Answers 3

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .