Sejam
e
inteiros. Prove que:
(d) Se
, então
onde
e
são inteiros positivos.
(d) Se
Passo 1
O que o enunciado dá e pede (resumindo bem devagarinho):
são inteiros (isso nos diz que estamos trabalhando em
).\n
Estamos na hipótese de que — ou seja,
e
não têm nenhum divisor inteiro positivo comum além de
.\n
O que precisamos provar: que, para quaisquer inteiros positivos e
, vale
Estamos na hipótese de que
O que precisamos provar: que, para quaisquer inteiros positivos
Passo 2
Ideia geral (sem cálculos ainda): tomar um divisor comum qualquer de
e
e mostrar que esse divisor só pode ser
. Para isso vamos usar uma propriedade muito útil sobre números primos: se
é primo e
divide um produto, então
divide pelo menos um dos fatores. Essa propriedade permite concluir que se um primo divide
então ele divide
. Vou provar essa propriedade rapidamente (é uma ferramenta que aparece sempre em provas desse tipo).
Passo 3
Propriedade básica (Lema de Euclides, versão curta): se
é um número primo e
(ou seja,
divide o produto
), então
ou
.
Prova curta e didática: suponha
. Se
já terminou. Caso contrário,
não divide
, então
. Pelo Teorema de Bézout (existe sempre inteiros
tais que
quando
), multiplicando por
obtemos
Como
, o termo
é múltiplo de
; e obviamente
também é múltiplo de
. Então a soma
é múltiplo de
. Logo
. Isso mostra que se
não divide
então divide
; portanto
ou
. QED.
Passo 4
Lema aplicado a potências: se
é primo e
para algum inteiro
, então
.
Prova por indução simples (ou por repetição da aplicação do lema anterior):
- Para
é trivial: . - Suponha válido para
. Se então . Pelo lema de Euclides, ou . Se já terminamos; se então, pela hipótese de indução, . Portanto em todo caso .
Assim fica demonstrado que qualquer primo que dividedivide .
Passo 5
Agora a prova principal: seja
. Queremos mostrar
.
Considere um número primo
que divida
. Como
e
, temos
; pelo lema do passo anterior segue que
. De forma análoga,
implica
e portanto
. Assim qualquer primo divisor
de
divide simultaneamente
e
.
Passo 6
Concluir por contradição com a hipótese: se existisse algum primo
que divide
, então
dividiria
e
ao mesmo tempo, o que implica
. Mas isso contradiz a hipótese
. Portanto não existe primo que divida
.
Se um inteiro positivo
não tem nenhum divisor primo, então
. Logo
.
Passo 7
Um exemplo rápido para fixar a intuição: tome
,
(aqui
),
,
. Então
e
. De fato
, porque nenhum primo divisor de
(que é apenas
) divide
, e nenhum primo divisor de
(que é apenas
) divide
. Isso ilustra a ideia do argumento anterior.