Neste post, vamos provar que todo número pode ser escrito como o produto de números primos. Usaremos indução forte, ou seja, não assumiremos a verdade da proposição P apenas para n-1 (indução fraca), mas para todo inteiro menor que n, inclusive n-1. É importante lembrar que as formas forte e fraca são equivalentes, mas as vezes, optar por uma das formas facilita a prova. Confira nosso post sobre os tipos de indução aqui.
P(n): Todo número inteiro n > 1 pode ser escrito como o produto de números primos.
A prova é por indução em n:
- Caso Base: para n = 2, temos que 2 é primo, logo é o único fator primo.
- Hipótese de Indução: vamos assumir que para $2 \le j \le n-1$, j pode ser escrito como o produto de números primos.
- Caso Geral: Devemos considerar dois caso. Se n for primo, então n pode ser escrito como o produto de um primo, ele mesmo. Caso n seja composto, ou seja, n = a * b com $2 \le a \le b \le n-1$, sabemos que por hipótese de indução a e b podem ser escritos como o produto de primos. Como n = a * b, a decomposição de n em fatores primos, é simplesmente a multiplicação de todos os fatores de a pelos fatores de b. C.Q.D
@inductioncode
Nenhum comentário:
Postar um comentário