22  O Teorema Chinês dos Restos (V1.0)

Teorema 22.1 Sejam \(m,n\in\N\) primos entre si e sejam \(r_m\in\{0,\ldots,m-1\}\) e \(r_n\in\{0,\ldots,n-1\}\). Existe um único inteiro \(a\) entre \(0\) e \(mn-1\) tal que o resto de \(a\) quando dividido por \(m\) é \(r_m\) e o resto de \(a\) quando dividido por \(n\) é \(r_n\), respetivamente

Comprovação. Seja \(a\in\{0,\ldots,mn-1\}\) e escreva \(a=q_mm+r_m=q_nn+r_n\) onde \(r_m\in\{0,\ldots,m-1\}\) e \(r_n=\{0,\ldots,n-1\}\). Defina a aplicação \(\psi\) na seguinte forma: \[\begin{align*} \psi&:\{0,\ldots,mn-1\}\to \{0,\ldots,m-1\}\times\{0,\ldots,n-1\}\\ a&\mapsto(r_m,r_n). \end{align*}\] A afirmação do teorema é equivalente à afirmação que \(\psi\) é bijetiva e é isso que nos vamos provar. Como o domínio e o codomínio de \(\psi\) têm a mesma cardinalidade, precisamos provar apenas que \(\psi\) é injetiva. Assuma que \(a_1,a_2\in\{0,\ldots,mn-1\}\) tais que \(a_1\leq a_2\) e \[ \psi(a_1)=\psi(a_2)=(r_m,r_n). \] Isso implica que \[ a_1=q_1m+r_m=q_2n+r_n\quad \mbox{e}\quad a_2=q_3m+r_m=q_4n+r_n \] com alguns \(q_1,q_2,q_3,q_4\in\Z\). Daqui obtemos que \[ a_2-a_1=(q_3-q_1)m=(q_4-q_2)n \] e \(n\mid a_2-a_1\) e \(m\mid a_2-a_1\). Lembrando que \(\mdc mn=1\), isso implica que \(mn\mid a_2-a_1\). Mas \(0\leq a_2-a_1 < mn\), e assim \(a_2-a_1=0\); ou seja \(a_2=a_1\). Assim obtemos que nossa função \(\psi:a\mapsto (r_m,r_n)\) é injetiva e precisa ser bijetiva