Se a e b sāo números naturais primos entre si, prove que
também
são, para quaisquer
.
Resolução: Vamos supor mdc
. Entāo
e
admitem um divisor primo comum
. Se
, então
se
, então
a ou
; por indução: p|a. Analogamente p|b. Absurdo.
Passo 1
O enunciado diz que
e
são números naturais tais que
, e pede para provar que, para quaisquer
, também vale
O conteúdo é Teoria dos Números, usando o fato de que um divisor primo de uma potência divide a base.
Passo 2
Lema: se
é primo e
com
, então
.
Prova por indução em :
Prova por indução em
- Base (
): trivial, pois implica . - Passo indutivo: suponha válido para
. Se , pelo Lema de Euclides ou . No segundo caso, pela hipótese indutiva . Logo em todo caso .
Passo 3
Prova por absurdo: suponha
. Então existe primo
tal que
e
.
Pelo lema do Passo 2, e
. Isso contradiz
.
Pelo lema do Passo 2,
Passo 4
Como chegamos a um absurdo ao supor
, concluímos que
ou seja,
e
são primos entre si.