Si ninguno de los números $b,2b,...,(m-1)b$ es divisible entre $m$, entonces $m$ y $b$ son coprimos.
La hipótesis del teorema equivale a decir que los residuos $r_i$ que quedan al dividir los números $ib$ entre $m$ son todos no nulos. Y tienen que ser todos diferentes pues la afirmación $r_i=r_j$ no puede sostenerse. Porque $r_i=ib-q_im$. De aquí que $r_i=r_j \Leftrightarrow ib-jb = (i-j)b = M(m)$ y se logra una contradicción. En otras palabras, la función $f(i)=r_i, i=1,2, \cdots ,m-1$ es biyectiva, es decir, es una permutación de $\{1,2, \cdots ,m-1\}$. Esto permite asegurar que algún $r_k=1$. Es decir, existe $k$ de $\{1,2,...,m-1\}$ tal que $kb=q_k m+1$. O sea $kb-q_k m=1$. Pero esto es lo mismo que decir que $m$ y $b$ son coprimos. (Porque si tuviesen un divisor común, d digamos, entonces $b=b ' d$ y $m=m ' d$. Así que $(kb ' - q_k m ' )d=1$ y se logra ver que d está obligado a ser 1.)
Alguno de los números $b,2b, \cdots$ tiene que ser divisible entre $m$ (con seguirdad $mb$ lo es). Pero si tengo que llegar hasta $mb$ para lograr un múltiplo de $m$ (ningún $ib$ contiene a $m$ como factor con $i=1,2, \cdots ,m-1$) entonces $m$ y $b$ son coprimos ($b=b'd$, $m = m ' d \Leftrightarrow m ' b=b ' m$ con $m ' < m$ si $d>=2$).
