# How to prove that gcd(m+1, n+1) divides (mn-1)

I'm learning about divisors and the gcd, but now I'm stuck at proving:

gcd(m+1, n+1) divides (mn-1) for all m,n in the set of Integers

Help is appreciated on how to prove this! Thanks

• $mn-1=(m+1)(n+1)-(m+1)-(n+1)$ Jan 8 '17 at 20:29

A common strategy to solve this type of problem is using the following simple fact:

If $d$ divides $a$ and $b$, then d divides $$a\cdot r+b\cdot s$$ for all $r,s \in \mathbb{Z}$.

Thus if $d=\gcd(m+1,n+1)$, then obviously $d$ divides $m+1$ and $n+1$, and so d divides $$(m+1)\cdot r+(n+1)\cdot s$$ for all $r,s \in \mathbb{Z}$. In particular, for $r=n$ and $s=-1$, we have that $d$ divides $$(m+1)\cdot n+(n+1)\cdot (-1)=mn-1.$$

• Thanks for this clarification! One of my attempts stranded at (m+1)⋅r + (n+1)⋅s. Could you maybe explain why in particular r = n and s = -1? Or do you simply take these to get to mn-1 as we can state that (m+1)⋅r+(n+1)⋅s for all r and s in Z? Jan 8 '17 at 21:10
• Exactly! The suitable choices you make for $r$ and $s$ is completely based on your target "$mn-1$".
– math
Jan 8 '17 at 21:13
• @Superkuuk You hit the nail on the head.The problem with this approach is that it pulls the answer out of a hat, i.e. there is no motivation for the choice of $\,r,s.\,$ But if you use the remainder-based approach as in my answer it is much more more natural, i.e. it is just a special case of the Polynomial Remainder Theorem, i.e that $\,P(x) \equiv P(c)\pmod{x-c}.\$ Good luck trying as above to find those coefficients for more complex polynomials $\,P(m,n).\,$ OTOH, evaluating $\,P(m,n)\,$ at $\,n,m = -1\,$ is utterly trivial. Jan 8 '17 at 21:36
• @BillDubuque - I disagree that it's "pulling the answer out of a hat". Mathematics is, first and foremost, a pursuit of pattern-matching. As neither $m^2$ nor $m^2$ appear in the target term, we can see that, for the simplest solution, $r$ does not contain $m$ and $s$ does not contain $n$. So we have $(m+1)(an+b)+(n+1)(cm+d)=mn-1$. Expanding the left and equating, we get $a+c=1$, $b+c=0$, $a+d=0$, and $b+d=-1$. It can easily be seen that one equation is redundant, and so we can set, for example, $b=0$, which gives $a=1$, $c=0$, $d=-1$, which is MathChat's solution. Jan 9 '17 at 8:45
• @GlenO But no such derivation is given in the answer. Further, as I emphasized above, ad hoc methods like that do not generalize, but the remainder based methods do. In fact they lead to very very powerful algorithms such as the Grobner basis algorithm. Ad-hoc attempts at "pattern matching" cannot compete with algorithms. Jan 9 '17 at 14:57

Hint $\$ mod \,\gcd(m\!+\!1,n\!+\!1)\!:\ \ \begin{align} &m\!+\!1\equiv0\equiv n\!+\!1\\ \Rightarrow\ &\ \ \,m\equiv -1\equiv n\\ \Rightarrow\ &mn\equiv (-1)(-1)\equiv 1\end{align}

Remark $\$ More generally, as above, using the Polynomial Congruence Rule we deduce

$$P(m,n)\equiv P(a,b)\,\ \pmod{\gcd(m\!-\!a,m\!-\!b)}$$

for any polynomial $\,P(x,y)\,$ with integer coefficients, and for any integers $\,m,n,a,b.$

OP is special case $\, a,b = -1\$ and $\ P(m,n) = mn\$ (or $\ mn-1)$

Although it's less elegant than the other approaches, you can also prove this through direct substitution. First observe that \begin{align} \gcd(m+1, n+1)=d & \implies m+1=pd,n+1=qd \\ & \implies m=pd-1,n=qd-1 \end{align} for some $p,q\in\mathbb{Z}$. Then \begin{align} mn-1 & = (pd-1)(qd-1)-1 \\ & = (pqd^2-(p+q)d+1)-1 \\ & = (pqd-(p+q))d, \end{align} which is an integer multiple of $d$.

Use the fact that

$$(m+1)(n+1) = mn + m + n + 1 = (mn - 1) + (m+1) + (n+1)$$

THen it is straightforward