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
 A: 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)$
A: 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$.
A: Use the fact that 
$$(m+1)(n+1) = mn + m + n + 1 = (mn - 1) + (m+1) + (n+1) $$
THen it is straightforward
A: 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.$$
