Mostre que
se, somente se,
;
Passo 1
O enunciado pede pra mostrar a equivalência
Isso é teoria de divisibilidade e máximo divisor comum (gcd), junto com o Lema de Bézout (que diz que, para qualquer par de inteiros, o gcd aparece como combinação linear desses inteiros). Vamos usar:
- Propriedades básicas de divisibilidade (se d divide x, então d divide x·y).
- Lema de Bézout:
se, e somente se, existem inteiros tais que .
Passo 2
(“⇒”) Suponha
. Queremos mostrar
(e o caso de
é idêntico).
- Seja
. - Por definição,
e . - Como
, existe um inteiro tal que . Então
logo
.
4. Assim divide ao mesmo tempo
e
, o que implica
. Mas
, então forçosamente
.
Conclusão: . Igual para
.
4. Assim
Conclusão:
Passo 3
(“⇐”) Agora suponha
e
. Vamos mostrar
usando Bézout.
- Como
, existem inteiros tais que
- Como
, existem inteiros tais que
- Multiplicando as duas igualdades:
- Expandindo à esquerda:
- Agrupando termos para ver combinação linear de
e :
Ou seja, existem inteiros
e
tais que
- Isso mostra que 1 é combinação linear de
e . Qualquer divisor comum de e teria de dividir 1, logo só pode ser . Assim .
Resposta
Portanto, ficou provado que