1. (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 n>=2 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 n=2, como 2 é primo, a única forma de escrevê-lo como produto de primos é ele próprio:
2=2
Logo a unicidade vale para n=2.

Passo 3

Passo indutivo. Suponha como hipótese de indução que todo inteiro m com 2<= m<n tem decomposição em primos única (até permutar fatores). Vamos provar que vale para n.

Passo 4

Suponha que existam duas decomposições de n em primos:
n = p1p2cdots pr e n = q1q2cdots qs,
onde todos os pi e qj são primos. Como p1mid n = q1cdots qs, pelo lema de Euclides p1 divide algum qj. Mas qj é primo, então p1=qj. Sem perda de generalidade troque a ordem dos q de modo que qs=p1. Divide-se então ambos os lados por p1, obtendo
np1 = p2cdots pr e np1 = q1cdots qs-1
Agora np1<n, então pela hipótese de indução as duas decomposições em primos de np1 são iguais, isto é, r-1 = s-1 e p2,dots,pr=q1,dots,qs-1 como multiconjuntos.

Passo 5

Concluímos que r=s e que, à ordem de multiplicação, (p1,p2,dots,pr) coincide com (q1,q2,dots,qs). Isso mostra a unicidade da decomposição em primos para n, completando a prova por indução forte.

Resposta

A decomposição de qualquer n>=2 em fatores primos é única, salvo a ordem dos fatores.

Exercícios relacionados