EE1 2013.2

Prévia do material em texto

DEPARTAMENTO DE ELETRÔNICA E SISTEMAS - UFPE 
SISTEMAS DISCRETOS – EE1 - 2013.2 
 
 
 
(4 pts) 
1) a) Use o teorema chinês do resto para encontrar �∈���� na congruência 
2���	≡	3	��
�	105	. 
b) Quantos elementos possuem inversos multiplicativos em ��, quando � é o produto 
de dois primos distintos? Justifique. 
 
 
(4 pts) 
2) a) Para quantos valores de c, incongruentes módulo p, a congruência )(mod pca x ≡ 
tem solução (considere o valor de a fixo) ? Justifique. 
b) Considere a construção de sequências de números inteiros usando aritmética módulo 
p, em que o i-ésimo termo da sequência é dado por 0 ), (mod ≥= ipa ii α e 
∗
∈ pZα . 
i) Essas sequências são sempre periódicas? Por quê? Justifique. 
ii) Com p = 17, é possível construir uma tal sequência com período N = 8? Por quê? 
Justifique. 
iii) Qual o menor valor de p que resulta em uma sequência com período 7? Quantas 
sequências deste tipo existem? Justifique. 
 
 
(2 pts) 
3) Sistemas de identificação baseados em aritmética modular são usados em livros, 
placas de carro, talões de cheque, produtos em um supermercado, etc. Um exemplo de 
um sistema desse tipo é o código de barras UPC, que associa a um produto um número 
de 12 dígitos a = (a1, a2, a3, ...., a12), em que a12 é um dígito verificador, calculado de 
modo que o produto escalar a • v ≡≡≡≡ 0 (mod 10), em que v = (3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 
1) é chamado vetor ponderador. Um erro de digitação muito comum nesse cenário é a 
transposição de dois dígitos adjacentes. Existem erros desse tipo que não podem ser 
detectados por esse código de barras? Quais? 
 
 
 
 
 
 
Duração: 2 horas. 10/12/13 Prof. Ricardo Campello