If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$

Question

I have to write a proof for

If $m$ is odd, and $n-1$ is divisible by $3$, then $(nm)-1$ is divisible by $6$

The way I solved it is: Given $m$ is odd this means that $m = 2k + 1$ where $k$ is some integer.

Given $n-1$ is divisible by $3$, this means that $n-1=3L$ or $n= 3L +1$ where $L$ is some integer.

It follows that $(nm) - 1 = (3L +1)(2K +1) = 6KL + 3L + 2k$

This doesn't seem to me to be divisible by $6$. But the online exercise we are using for my class solves $(3L +1)(2K +1)$ to be $6KL + 1$, which doesn't seem like because FOIL. What could I be doing wrong and what is the right answer to this proof?

Answer 1

Given $m = 2k + 1$ and $n = 3l + 1$, we get $$ mn - 1 = (2k+1)(3l+1) - 1 = 6kl + 2k + 3l + 1 - 1\\ = 6kl + 2k + 3l $$ And if this doesn't look like it's always divisible by $6$, then that's because it isn't. This is best proven by just giving an example. For instance, $k = l = 1$ gives $6 + 2 + 3 = 11$. Translating this back to $m$ and $n$, we get $$ m = 2k + 1 = 3\\ n = 3l+1 = 4 $$ and we can easily check that in this special case

• $m$ is odd
• $n-1$ is divisible by $3$
• $mn - 1$ is not divisible by $6$.

which means we have disproven the statement.

Answer 2

The inference holds true $\iff m,n\equiv 1\pmod{\!6},\,$ by case $\,p,q = 2,3\,$ below.

Lemma $\ $ Suppose that $\,m,n,p,q\,$ are integers and $\ \ell = {\rm lcm}(p,q) .\,$

$$ {\rm If}\ \ \ \begin{align} m\equiv 1\!\!\!\pmod{\!p}\\ n\equiv 1\!\!\!\pmod{\!q}\end{align} \ \ \ {\rm then}\ \ \ mn\equiv 1\!\!\!\pmod{\!\ell} \iff m,n\equiv 1\!\!\!\pmod{\!\ell}$$

Proof $\ (\Rightarrow)\ $ Since $\, p\mid \ell\,$ and $\,mn\equiv 1\pmod{\ell}\,$ this congruence persists $\!\bmod p\,$ so

$$\bmod p\!:\ \ \color{#c00}{m\equiv 1},\ \color{#c00}mn\equiv 1\,\Rightarrow\, n\equiv 1$$

Similarly we infer $\, m\equiv 1\pmod{\!q}.\,$ Hence $\,p,q\mid m\!-\!1,n\!-\!1\Rightarrow\, {\rm lcm}(p,q)\mid n\!-\!1,m\!-\!1$

$(\Leftarrow)\ \ \ \bmod \ell\!:\,\ m,n\equiv 1\,\Rightarrow\, mn\equiv 1$