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

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

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