elementary number theory - 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

Answer

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.$$