Seja
. Mostre que:
Passo 1
O enunciado nos dá um inteiro
e os dois inteiros
e
A pergunta é: mostrar que o máximo divisor comum desses dois inteiros é
; ou seja, provar que
Informações relevantes dadas:
-
é o produto dos inteiros de até . - Os números são
e . - Quer-se mostrar que não existe nenhum divisor inteiro maior que
que divida simultaneamente ambos.
Passo 2
Definição útil (explicação didática): o máximo divisor comum, denotado
, é o maior inteiro positivo que divide tanto
quanto
. Uma técnica comum é assumir que existe um divisor comum
e usar combinações lineares para obter contradições. Também é útil lembrar que se um primo
divide um produto de inteiros, então
divide pelo menos um dos fatores; e que se
divide
e
divide
então
divide
.
Vamos aplicar isso: defina
Queremos mostrar que
.
Passo 3
Vamos usar uma combinação linear simples dos dois números para eliminar termos grandes. Calculemos
Desenvolvendo:
Passo 4
Como
divide tanto
quanto
, ele também divide qualquer combinação inteira desses dois números. Logo
divide o número que acabamos de calcular, isto é,
divide
. Portanto
divide
.
Em linguagem simples: qualquer divisor comum de
e
tem que dividir
.
Passo 5
Agora vejamos o que isto implica para os factores primos de
. Seja
um primo que divide
. Então
divide
. Mas se
divide
e
, então
e, por isso,
divide
(pois
contém todos os fatores de
a
, inclusive
). Logo
divide
.
Mas já sabemos que
divide
(porque
divide
e
divide
). Assim
divide simultaneamente
e
. Então
divide a diferença
o que é impossível, pois nenhum primo maior que
divide
.
Passo 6
A contradição mostra que não existe primo
que divida
. Portanto
não tem fatores primos maiores que
, o que significa
.