Mostre que:
se, e somente se,
, para todos
.
Passo 1
O enunciado pede para mostrar a equivalência entre duas afirmações: que
e que
para todos
.
Informações dadas:
Informações dadas:
-
e são inteiros (assume-se inteiros não nulos). -
e são números naturais arbitrários.
O que devemos provar: a afirmação “” é verdadeira se, e somente se, para quaisquer tem-se .
Passo 2
Lembrando alguns conceitos úteis (explicados de forma simples):
-
denota o máximo divisor comum (mdc) de e . Dizer significa que e são coprimos, isto é, não têm nenhum divisor primo em comum. - Uma propriedade básica de números primos: se
é primo e divide (com ), então divide . Isto acontece porque e um primo que divide um produto divide pelo menos um dos fatores; aqui todos os fatores são , logo .
Vou usar essas ideias para mostrar as duas implicações necessárias da equivalência.
Passo 3
Provar: se
então
para todos
.
Prova passo a passo:
Prova passo a passo:
- Suponha
. Queremos ver que nenhum primo divide simultaneamente e . - Tome um primo arbitrário
. Suponha, para obter contradição, que divide tanto quanto . - Pela propriedade citada no Passo 2, de
segue que . De segue que . - Assim
seria um divisor primo comum de e , o que contradiz . - Como nenhum primo pode dividir ambos
e , a maior parte comum de e é . Portanto .
Isto vale para quaisquer. Logo a implicação está provada.
Passo 4
Uma prova alternativa (com identidade de Bézout) da mesma implicação, para intuição extra:
- Se
, pela identidade de Bézout existem inteiros tais que . - Suponha
é um divisor comum de e . Então qualquer primo divisor de divide (porque divide ) e divide (porque divide ); portanto não existem primos tais se , logo . - Assim o único divisor comum possível é
, então .
Esta versão usa a mesma ideia essencial (nenhum primo comum) mas dá uma intuição via divisores.
Passo 5
Provar a implicação inversa: se
para todos
então
.
Isto é praticamente imediato:
Isto é praticamente imediato:
- A hipótese diz que a propriedade vale para todos
. - Em particular, tomando
e obtemos , ou seja .
Portanto a implicação inversa é trivial.
Passo 6
Mostrei ambas as direções: (i) se
então para quaisquer
vale
; (ii) se
para todos
então, em particular para
,
. Assim as duas afirmações são equivalentes.