Matemática Discreta

O argumento do absurdo
C´
ıcero Thiago B. Magalh~ aes Introdu¸ c˜ ao
O argumento do absurdo ´e uma t´ecnica simples de resolver problemas. O argumento consiste em assumir que a conclus˜ ao do problema n˜ ao ´ e verdadeira, e em seguida, obter um fato absurdo! Em seguida apresentarei alguns problemas que podem ser resolvidos usando esta t´ecnica.
1. Prove que existem infinitos n´ umeros primos.
Solu¸
c˜ ao Vamos supor que a sequˆencia dos primos seja finita. Seja pois, p1 , p2 , . . . , pn a lista de todos os
´ claro que R n˜ ao ´ e divis´ıvel por nenhum dos pi primos. Consideramos o n´ umero R = p1 · p2 . . . pn + 1. E de nossa lista e que R ´ e maior do que qualquer pi . Mas sabemos que todo inteiro maior do que 1 pode ser representado de maneira (a menos de uma ordem) como um produto de fatores primos (*). Dessa maneira, R ´ e primo ou possui algum fator primo e isto implica na existˆencia de um primo quen˜ ao pertence a lista. Portanto a sequˆencia dos n´
`
umeros primos n˜ ao pode ser finita.
(*) Teorema fundamental da aritm´ etica 2. Prove que
Solu¸
c˜ ao √

2´ e irracional.

Suponhamos, por absurdo, que

√

2 seja racional, ou seja, que se tenha

√ p = 2, onde p e q s˜ ao primos q p p 2 seja irredut´ıvel. Dessa maneira temos que
= 2 ⇒ p2 = 2q 2 . Da u
´ ltima q q
2
2
2
equa¸c˜ ao fica f´ acil concluir que p ´ e par. Ent˜ ao coloquemos p = 2k e teremos (2k) = 2q ⇒ 2k = q 2 , e pelo mesmo motivo acima,√conclu´ımos que q ´ e par, absurdo, pois inicialmente supusemos que p e q a ser escrito em forma de fra¸c˜ ao, dessa maneira conclu´ımos eram primos entre si.√ Logo, 2 nunca poder´ a irracionalidade do 2. entre si, ou seja, a fra¸c˜ ao 3. Sejam p e q n´ umeros primos ´ımpares consecutivos. Prove que p + q ´ e um produto de pelo menos 3 inteiros positivos maiores do que 1 (n˜ ao necessariamente distintos). (Teste de sele¸c˜ ao do Brasil para IMO)
Solu¸
c˜ ao ´ f´