Avaliação Final

Prévia do material em texto

UNIVERSIDADE FEDERAL DO CEARÁ 
ENGENHARIA DA COMPUTAÇÃO 
MATEMÁTICA DISCRETA 
 
 
 
 
 
 
 
 
 
 AVALIAÇÃO FINAL 
 Chrystian Gemaque Maciel - 501212 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
QUIXADÁ 
 2021 
1) Prove o teorema: “Para todo n inteiro, se n mod 10 = 4, então n2 mod 10 = 6”. 
Resposta = Por demonstração exaustiva, temos n = 4, 4 mod 10 = 4  42 = 16 mod 10 = 
6, sendo válido para esse caso; porém quando n = 3, 3 mod 10 = 3  32 = 9 mod 10 = 9. 
nesse caso provando ser falso e invalidando o teorema pois não se verifica em todos os 
inteiros. 
 
2) Resolva a soma abaixo realizando uma mudança de índices. Os passos no seu 
desenvolvimento de sua resposta devem ser baseados nas propriedades de somatórios e 
fórmulas fechadas. Obs.: Explique a sua resposta, indicando quais propriedades ou 
fórmulas está usando em cada passo. Respostas sem explicações ou com adição manual 
dos termos serão automaticamente zeradas. 12Σj=5(3*2j – 2j2 + 5), Sendo aj = 3*2j – 2j2 
+ 5; 
 
3) Usando a técnica de Prova por Indução, mostre que: “Para todo n nos números 
naturais, 4 | 2n2 + 6n”. 
Resposta = Caso base: Se n = 1, p(1) = 4 | 2 * 12 + 6 * 1 = 4 | (2 + 6) = 4 | 8 = 2; 
 
Passo indutivo: 
p(n + 1) = 4 | 2n2 + 6(n + 1); 
= 2(n + 12) + 6(n + 1) 
= 2(n + 12) + 6(2n) 
= 2(2n) + 6(2n) 
= 4n + 8  n = 8 / 4 = 2 
 
4) Resolva os itens abaixo fornecendo todos os cálculos e explicando cada passo 
realizado. Respostas sem discussão dos métodos utilizados poderão ser penalizadas. 
a) Encontre as fatorações individuais dos números 234 e 273. 
 R= 
 
 234 2 2 * 3 * 3 * 13 = 234 273 3 3 * 7 * 13 = 273 
 117 3 91 7 
 39 3 13 13 
 13 13 1 
 1 
 
 
b) Utilizando as fatorações obtidas no Item (a), encontre todos os divisores positivos de 
234 e, similarmente, todos os divisores positivos de 273. 
 
Resposta = Pelo algoritmo da fatoração temos que 234 = 21 * 32 * 131, e se variarmos o 
expoente de 2 de 0 até 1, teremos 1 + 1 = 2, variando o expoente de 3 de 0 até 2 teremos 
2 + 1 = 3, e por fim variando o de 13 de 0 até 1, teremos 1 + 1 = 2. Como os expoentes 
são independentes, deve-se multiplicar os números de possíveis valores. 
Concluímos que 234 tem (1 + 1) * (2 + 1) * (1 + 1) = 2 * 3 * 2 = 12 divisores. 
 
20 * 30 * 130 = 1 20 * 31 * 130 = 3 21 * 31 * 130 = 6 20 * 31 * 131 = 39 
20 * 30 * 131 = 13 21 * 30 * 130 = 2 21 * 30 * 131 = 26 21 * 31 * 131 = 78 
21 * 32 * 131 = 234 21 * 32 * 130 = 18 20 * 32 * 131 = 117 20 * 32 * 130 = 9 
 
De maneira igual ao número acima usarei o mesmo método para descobrir os divisores 
positivos de 273 = 31 * 71 * 131, variando o expoente de 3 de 0 até 1, teremos 1 + 1 = 2, 
variando o expoente de 7 de 0 até 1, teremos 1 + 1 = 2, e variando o expoente de 13 de 0 
até 1, teremos 1 + 1 = 2, e multiplicando os valores, concluímos que 273 tem (1 + 1) * (1 
+ 1) * (1 + 1) = 2 * 2 * 2 = 8 divisores. 
 
30 * 70 * 130 = 1 31 * 70 * 130 = 3 30 * 71 * 130 = 7 30 * 70 * 131 = 13 
31 * 71 * 130 = 21 31 * 70 * 131 = 39 30 * 71 * 131 = 91 31 * 71 * 131 = 273 
 
c) Com base nos cálculos realizados nos itens anteriores, mostre ao menos duas formas 
diferentes de calcular mdc(234, 273). Após encontrar este resultado, liste ao menos duas 
formas diferentes de calcular mmc(234, 273). 
 
Resposta = Primeira forma de calcular mdc: Calculando a partir dos fatores comuns, pelo 
algoritmo da fatoração temos que todo divisor de 234 é combinação de (20, 21) com (30, 
31, 32) e com (130, 131); 
E que 273 é combinação de (30, 31) com (70, 71) e com (130, 131). 
Com isso temos que os divisores comuns de 234 e 273 só podem ser combinações de 30 
ou 31 ou 130 ou 131, o que nos dá apenas quatro números 1, 3, 13 ou 39, portanto 
MDC(234, 273) = 39. 
Segunda forma de calcular o mdc: Comparando as duas listas de divisores de 234 e 273: 
Divisores de 234: 1, 2, 3, 6, 9, 13, 18, 26, 39, 78, 117, 234; 
Divisores de 273: 1, 3, 7, 13, 21, 39, 91, 273; 
E nesse caso temos que o máximo divisor de comum de (234, 273) = 39. 
 
Agora para o cálculo de mmc, a primeira forma: Calculando o mmc a partir dos fatores 
comuns, calculando os fatores de 234 e 273, observando que o menor múltiplo comum 
entre eles terá estes fatores apenas, ademais como 31 | 32, basta usar o 32 para incluir os 
dois fatores de base 3. 
MMC(234, 273) = 21 * 32 * 71 * 131 = 1638; 
A segunda forma de calcular o mmc: Calculando o mmc a partir do mdc, como já se sabe 
que o mdc(234, 273) = 39, o teorema “Dados s, t inteiros positivos, teremos que MMC(s, 
t) * MDC(s, t) = s * t.”; 
Com isso temos que mmc(234, 273) = 234 * 273 / 3 = 6 * 273 = 1638. 
 
d) Encontre um valor para x tal que mdc(x, 234) ≠ mdc(273, x) ≠ mdc(234, 273). 
Explique como você encontrou este valor. 
6) Prove o teorema: “Para todo m inteiro positivo e todos a, b, c, d inteiros, se a ≡ b 
(mod m) e c ≡ d (mod m), então a*c ≡ b*d (mod m).” 
Resposta = Pelo algoritmo da divisão, existem inteiros positivos k1, k2 k3 k4, com restos 
l1, l2, que para quaisquer inteiros positivo a, b, c e d: 
 a = mk1 + l1; b = mk2 + l1; c = mk3 + l2; d = mk4 + l2; 
Usando o algoritmo da divisão temos: 
(mk1 + l1) * (mk3 + l2) ≡ (mk2 + l1) * (mk4 + l2) 
m2k1k3 + mk1l2 + mk3l1 + l1l2 ≡ m2k2k4 + mk4l1 + l1l2 
Provando ser verdade o teorema e que a*c ≡ b*d (mod m) é válido. 
 
BÔNUS 2: Usando Prova por Indução, prove que “Seja f(x) = k*rx uma progressão 
geométrica com r ≠ 1, mostre que nΣi=0 k*ri = k*r(n+1) – k / r-1, para todo n natural”. 
 
Resposta = Seja p(n) nΣi=0 k*ri = k*r(n+1) – k / r-1; se n = 1, teremos p(1): A soma do 
primeiro termo = k*r0 = k*r  sendo verdade para n = 1; 
p(2): sendo n = 2, teremos k*r + k*r1 = k*r (r + 1), p(2) = k*r(r2 – 1) / r – 1 = k*r(r + 1) 
 sendo verdade para quando n = 2. Provando ser verdade para todo n natural.