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 \ldots \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 \ldots \cdot q_{m}\,\!$ e $b=t_{1}\cdot t_{2}\cdot \ldots \cdot t_{n}\,\!$, com cada $q_{j}\,\!$ e cada $t_{j}\,\!$ sendo um número primo, donde segue que: $n=a\cdot b=\left(q_{1}\cdot q_{2}\cdot \ldots \cdot q_{m}\right)\cdot \left(t_{1}\cdot t_{2}\cdot \ldots \cdot t_{n}\right)\,\!$ Assim, basta renomear os primos $q_{j}\,\!$ e $t_{j}\,\!$ como $p_{1},\ldots ,p_{r}\,\!$, e tem-se o teorema.