Mostre que:
se, e somente se,
.
Passo 1
O enunciado pede para mostrar uma equivalência entre duas afirmações envolvendo o máximo divisor comum. Mais precisamente, dado
(inteiros), devemos provar que
Informações relevantes que temos do enunciado:
- A notação
significa o máximo divisor comum entre os inteiros e . - Queremos provar uma bicondicional: uma direção "se
então " e a direção inversa "se então ".
Nada mais é dado explicitamente; todas as hipóteses necessárias são as que aparecem acima.
Passo 2
Prova da direção "
e
".
Seja
. Por definição de máximo divisor comum,
divide
e
divide
. Como
divide
, então
divide
(pois multiplicar por
preserva a divisibilidade). Assim
divide simultaneamente
e
, ou seja,
divide
.
Agora usamos a hipótese
. Como
divide
e
, segue que
divide
. O único divisor positivo de
é
próprio, logo
. Portanto
.
O mesmo argumento vale trocando
por
: se
então
divide
e
, logo
divide
e
, portanto
divide
, daí
. Assim
.
Concluímos a primeira direção:
implica
e
.
Passo 3
Prova da direção "
e
".
Queremos mostrar que o único divisor comum positivo de
e
é
. Seja
. Se
já terminamos; suponhamos, para chegar a uma contradição, que
. Então existe um primo
tal que
divide
. Assim
Usamos agora o lema de Euclides: se
é primo e
então
ou
. (Breve justificativa do lema: se
e
, então
e existem inteiros
com
; multiplicando por
obtém-se
e a primeira parcela é múltiplo de
, logo
.)
Aplicando o lema ao produto
, a partir de
segue que
ou
.
- Se
, então divide tanto quanto , o que significa que divide . Mas por hipótese , portanto isso é impossível. - Se
, então divide tanto quanto , então divide . Mas por hipótese , portanto isso também é impossível.
Portanto não existe tal primo
. Isso contradiz a suposição
. Logo
não pode ser maior que
, isto é,
. Assim
.
Passo 4
Comentário final e exemplo ilustrativo (para fixar a ideia).
Exemplo: tome
,
,
. Então
e
. Pelo que provamos,
— conferindo na prática. Se, em vez disso, tivéssemos
, então
e de fato
.
Você conseguiu! A prova principal é curta: uma direção usa que qualquer divisor comum de
e
divide
; a outra usa o lema de Euclides (primo que divide produto divide um dos fatores).