Monitoria de Discreta:

Aula de Revisão

Mini-prova 3

Temas:

- Primos e Máximo Divisor Comum;

- Inteiros e Algoritmos;

- Aplicações de Teoria dos Números e

- Prova por Indução

Monitores: Flávia Porto / Gibson Nunes / Hugo Rafael / Ismar Pereira / João

Paulo / José Eduardo / Justan Luiz / Luciano Farias / Pamela Thays/ Tiago

Neves

Primos

- Dizemos que um número inteiro é primo quando ele só

é divisível por 1 e por ele próprio;

- Um número inteiro é composto se existe um número

entre um e ele mesmo que o divide;

- Se n é composto então n possui um divisor primo entre

1 e a raiz quadrada de n;

- A quantidade de números primos menores que x,

quando x tende ao infinito, é aproximadamente x/ln(x).

Máximo Divisor Comum(MDC) e

Mínimo Múltiplo Comum(MMC)

- Seja a e b inteiros, o MDC entre a e b é o maior número que

divide a e também divide b;

- Seja a e b inteiros, o MMC entre a e b é o menor número

que é dividido por a e por b

- Exercicio:

- Sejam mdc(p, q) = 45, mmc(g,q) = 270 e q = 90 .

- A) Fatore os números;

- B) utilize a definição de mdc em termos de fatores

primos para encontrar p, que deve estar fatorado.

- C) utilize a definição de mmc em termos de fatores

primos para encontrar g, que deve estar fatorado.

Inteiros e Algoritmos

- Algoritmo de Euclides: método para encontrar o MDC

de dois números inteiros diferentes de 0.

- Exercicio

- Utilizando o algoritmo de euclides encontre o

MDC(112,68)

Teorema Chinês do Resto

Passo 1

Passo 2

Passo 3

Exemplo 1

Exemplo 1(continuação)

Exemplo 1(continuação)

Exemplo 1(continuação)

Exemplo 1(continuação)

Prova por Indução

Passo 1

Passo 2

Passo 3

Prove que (n²-1) é divisível por 8, onde n é um número ímpar positivo (Capítulo 4, Questão 35, Rosen, 6ª edição em inglês)

Para n ser ímpar deve haver um m tal que:

n = 2*m+1 Caso base:

((2*0+1)² - 1) mod 8 = 0 ok! Obs: n tem que ser positivo (n>0), por

isso m tem que ser maior ou igual a 0

Exemplo 2

Hipótese de Indução

Consideraremos igualdade consistente para m=k

((2*k+1)² - 1) mod 8 = 0

(4*k² + 4*k + 1 - 1) mod 8 = 0

(4*k² + 4*k) mod 8 = 0 ok!

Exemplo 2(continuação)

Passo Indutivo Verificaremos se a equação é válida para m=k+1

(4*(k+1)² + 4*(k+1)) mod 8 = 0 (4*(k²+2*k+1) + 4*k + 4) mod 8 = 0 (4*k² + 8*k + 4 + 4*k + 4) mod 8 = 0 (4*k² + 4*k + 8*k + 8) mod 8 = 0 (((4*k² + 4*k) mod 8) + ((8*k + 8) mod 8)) mod

8 = 0 Usando a hipótese de indução temos que :

((4*k² + 4*k) mod 8) = 0

(0 + (8*(k+1) mod 8)) mod 8 = 0 (0 + 0) mod 8 = 0

0 = 0 ok!

Exemplo 2(continuação)