Algorítimos - Iniciação à matemática/algebra

Prévia do material em texto

Mat 131
Algoritmo da divisão em ℤ ( Algoritmo de Euclides)
Para quaisquer a ,b∈ℤ , b>0 , existe um único par de inteiros r e q de maneira que
a=bq+r , em que 0≤r<b .
Prove o seguinte resultado:
“Se a∈ℤ então (a3−a) é múltiplo de 3 ”
Observação: Como a3−a=(a−1)⋅a⋅(a+1) , este resultado pode ser reescrito como:
“ O produto de três números inteiros consecutivos é múltiplo de 3 ”.
Prova: Seja a∈ℤ . Após dividir o número a por 3 , obtem-se um quociente q e um resto
r , com r∈{0,1,2} , tal que a=3q+r .
(i) Se r=0 então a=3⋅q . Neste caso, a3−a=a⋅(a−1)⋅(a+1)=3q⋅(3q−1)⋅(3q+1) é 
divisível por 3 .
(ii) Se r=1 então a=3q+1 . Neste caso, a3−a=a(a1)(a+1)=(3q+1)3q(3q+2) =
3⋅[(3q+1)⋅q⋅(3q+2)] é múltiplo de 3 .
(iii) Se r=2 então a=3q+2 . Neste caso, a3−a=a(a−1)(a+1)=(3q+2)(3q+1)(3q+3) =
3⋅[(3q+2)(3q+1)(q+1)] é múltiplo de 3
Portanto, a3−a é múltiplo de 3 , para todo a∈ℤ
Exercício para casa: 
Mostre que, se p>3 e p é primo então p é da forma 6k+1 ou 6k−1 , para algum inteiro
k>0 .
Sentenças Abertas
Definição: Chama-se sentença aberta ou função proposicional com um variável em um conjunto
A , um expressão p(x) tal que p(a) é falsa (F) ou verdadeira (V ) se a∈A . O 
conjunto A recebe o nome de conjunto universo.
Exemplo: 
a) P(n): n+1>8 e A=ℕ ;
P(1):1+1>8→P(1)é Falsa
P(9): 9+1>8→P(9)é Verdadeira
b) P(x) : x é divisor de10 e A=ℕ* ;
P(1), P(2), P(5)e P(10) são proposições verdadeiras.
c) P(n): 8divide32n+7 e A=ℕ .
Definição: Chama-se conjunto verdade de uma sentença aberta p(x) em um conjunto A , o 
conjunto V p de todos os elementos a∈A tais que p(a) é uma proposição verdadeira (V ) .
V p={x∈A : p(x )} 
Exemplo 1: P(n): n+1>8 , A=ℕ
V p={n∈ℕ :n+1>8 }
V p={n∈ℕ :n>7 }
V p={8,9,10, ... , n ,...}
Exemplo 2: O conjunto verdade da sentença aberta (x2−2x )>0 em ℤ é:
V p={x∈ℤ: x
2−2 x>0}
V p={x∈ℤ:(x<0)v (x>2)}
V p={x∈ℤ: x<0}U {x∈ℤ: x>2}
V p=ℤ−{0,1,2}
Princípio de indução
Seja p(n) um função proposicional com n∈ℤ e n≥a . Suponhamos que se consiga 
provar o seguinte:
(i) p(a) é verdadeira;
(ii) Se k≥a e P(k ) é verdadeira, então P(k+1) também é verdadeira. Então P(r ) é 
verdadeira, para todo n≥a .
Exemplo: Prove, por indução, que,
P(n): 8 divide 32n+7 , para todo n∈ℕ .
Prova:
(i) P(0) é verdadeira, pois 32 ·0+7=8=8 ·1
(ii) Seja k≥0 e suponha P(k ) verdadeira, ou seja, 32k+7=8 ·l , para algum l∈ℕ . Vamos 
provar que P(k+1) é verdadeira. Note que:
32(k+1)+7= 32 k+2+7= 9 ·32k+7= (8+1)·32 k+7= 8 ·32k+8 l= 8 ·[32k+l ]=8· j , com j∈ℕ
Segue do Princípio de indução que P(n) é verdadeira, para todo n∈ℕ .