Teoria de números/Máximo divisor comum

Demonstração

Dado um número inteiro $n$, vamos mostrar por indução que $n=p_1\cdot p_2\cdot \dots \cdot p_r$, com cada $p_j$ sendo um número primo. De fato, para $n=2$, o teorema é válido, pois basta tomar $p_1=2$. Se $n>2$, e $n$ for primo, a afirmação é obviamente verdadeira, pois é suficiente escolher $p_1=n$. Considere então que $n>2$ é composto, e que a hipótese de indução é que todo número menor que $n$ admite decomposição em fatores primos. Logo, existem inteiros $a$ e $b$ tais que $n=a\cdot b$. Além disso, $a$ e $b$ são menores que $n$. Pela hipótese de indução, tem-se $a=q_1\cdot q_2\cdot \dots \cdot q_m$ e $b=t_1\cdot t_2\cdot \dots \cdot t_n$, com cada $q_j$ e cada $t_j$ sendo um número primo, donde segue que: $n=a\cdot b=(q_1\cdot q_2\cdot \dots \cdot q_m)\cdot (t_1\cdot t_2\cdot \dots \cdot t_n)$ Assim, basta renomear os primos $q_j$ e $t_j$ como $p_1,\dots ,p_r$, e tem-se o teorema.

• Ver como deveria funcionar a predefinição em: http://pt.wikibooks.org/wiki/Teoria_de_n%C3%BAmeros/M%C3%A1ximo_divisor_comum