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 ri que quedan al dividir los números ib entre m son todos no nulos. Y tienen que ser todos diferentes pues la afirmación ri=rj no puede sostenerse. Porque ri=ib−qim. De aquí que ri=rj⇔ib−jb=(i−j)b=M(m) y se logra una contradicción. En otras palabras, la función f(i)=ri,i=1,2,⋯,m−1 es biyectiva, es decir, es una permutación de {1,2,⋯,m−1}. Esto permite asegurar que algún rk=1. Es decir, existe k de {1,2,...,m−1} tal que kb=qkm+1. O sea kb−qkm=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′−qkm′)d=1 y se logra ver que d está obligado a ser 1.)
Alguno de los números b,2b,⋯ 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,⋯,m−1) entonces m y b son coprimos (b=b′d, m=m′d⇔m′b=b′m con m′<m si d>=2).