- (Monnalysa) Use o Segundo Princípio da Indução para demonstrar a unicidade da decomposição de um número natural em fatores primos.
Passo 1
O enunciado pede para mostrar, por indução forte (Segundo Princípio da Indução), que qualquer inteiro natural
tem decomposição em fatores primos única, à ordem de multiplicação. O conteúdo principal é a indução forte e o lema de Euclides (se um primo divide um produto, então divide um dos fatores).
Passo 2
Base da indução. Para
, como
é primo, a única forma de escrevê-lo como produto de primos é ele próprio:
Logo a unicidade vale para
.
Passo 3
Passo indutivo. Suponha como hipótese de indução que todo inteiro
com
tem decomposição em primos única (até permutar fatores). Vamos provar que vale para
.
Passo 4
Suponha que existam duas decomposições de
em primos:
onde todos os
e
são primos. Como
, pelo lema de Euclides
divide algum
. Mas
é primo, então
. Sem perda de generalidade troque a ordem dos
de modo que
. Divide-se então ambos os lados por
, obtendo
Agora
, então pela hipótese de indução as duas decomposições em primos de
são iguais, isto é,
e
como multiconjuntos.
Passo 5
Concluímos que
e que, à ordem de multiplicação,
coincide com
. Isso mostra a unicidade da decomposição em primos para
, completando a prova por indução forte.
Resposta
A decomposição de qualquer
em fatores primos é única, salvo a ordem dos fatores.