Use a prova por contradição para demostrar que:
Para todo
, se
, então a
ou a
Para todo
Passo 1
O enunciado pede que demonstremos a seguinte afirmação: para quaisquer
, se
, então
ou
.
Informações dadas que vamos usar: e
são inteiros e há a hipótese numérica
.
O que devemos provar: pelo menos uma das duas afirmações é verdadeira — não divide
ou
não divide
.
Informações dadas que vamos usar:
O que devemos provar: pelo menos uma das duas afirmações é verdadeira —
Passo 2
Vou usar prova por contradição. Uma explicação rápida e simples do método: para provar uma afirmação do tipo “P implica (Q ou R)”, assumimos
e a negação da conclusão, isto é, assumimos
e
. A negação de uma disjunção é a conjunção das negações, então assumimos
e
e
. Então procuramos uma contradição com
ou com axiomas conhecidos; ao chegar numa contradição concluímos que a negação da conclusão é impossível, logo a conclusão é verdadeira. Aqui, a conclusão é "
ou
". A negação será "
e
". Vamos assumir isso e partir pra contradição.
Passo 3
Assumimos, para obter contradição, que
e que tanto
divide
quanto
divide
. Em símbolos, assumimos
Vou agora usar a definição de divisibilidade.
Passo 4
Definição usada: dizer que
significa que existe um inteiro
tal que
. Aplicando essa definição às duas hipóteses de divisibilidade, existem inteiros
e
tais que
e
Aqui
.
Subtraindo a primeira igualdade da segunda (isso é uma técnica comum para explorar duas divisibilidades simultâneas), obtemos
Subtraindo a primeira igualdade da segunda (isso é uma técnica comum para explorar duas divisibilidades simultâneas), obtemos
O lado esquerdo simplifica para
. No lado direito, fatoramos
:
Passo 5
A igualdade
mostra que
divide
. Mais formalmente, existem inteiros (aqui
) cujo produto com
é
. Pela propriedade dos inteiros, se um inteiro
divide
então
; isto porque se
com
, tomando valores absolutos temos
e os únicos divisores positivos de
são
mesmos, logo
.
Mas a hipótese inicial dizia . Isso implica que
é um inteiro com magnitude pelo menos
, ou seja
. Isso contradiz o que obtivemos no passo anterior (
). Portanto a suposição de que ambas as divisibilidades ocorriam leva a uma contradição.
Mas a hipótese inicial dizia
Passo 6
Como a conjunção "
e
" é impossível sob a hipótese
, a negação dessa conjunção — que é "
ou
" — deve ser verdadeira. Assim, mostramos que, para quaisquer
com
, vale que
ou
.
Resposta
Para todo
, se
então
ou
.