aula3

Prévia do material em texto

1 
 
 
UNIVERSIDADE FEDERAL DA BAHIA- UFBA 
DISCIPLINA: Matemática Discreta II – MAT A97 
Michele Novais 
 
Aula 3 
1. CONGRUÊNCIA 
1.1. PROPRIEDADES BÁSICAS 
Definição 1.1.1. Seja um número natural maior que 1. 
Dois números inteiros dizem-se congruentes 
módulo se Se é congruente a módulo 
 denota-se . 
Observe que dado qualquer inteiro , 
 . Se dizemos que é incongruente a 
 , Isto é . 
Exemplo 1.1.2. , pois . 
 . Pois 
Teorema 1.1.3. é congruente a módulo se, e 
somente se, a divisão de cada um deles por tem um 
mesmo resto. 
Demonstração. Seja e 
com , . Se 
 Como deve ser Logo 
 
 Seja e com 
 Então 
 . Logo 
 . 
 
Exemplo 1.1.4. no qual 
 , e 
 . Nesse caso todos os elementos de uma 
mesma classe são côngruos. 
Proposição 1.1.5. Se são inteiros, , as 
seguintes sentenças são verdadeiras: 
(i) . 
(ii) 
(iii) 
 
 
2 
 
 
Demonstração. (i) como . 
Logo . (ii) Se 
então 
 para algum . Logo 
 
(iii) Como e , 
existem inteiros tais que 
 
 
 
Esta proposição nos diz que a relação de congruência, 
definida no conjunto dos inteiros, é uma relação de 
equivalência, pois acabamos de provar que ela reflexiva, 
simétrica e transitiva. 
Proposição 1.1.6. A relação de congruência é de 
equivalência em e compatível com a soma e o produto. Ou 
seja, se então se 
 
Exemplo 1.1.7. 
 . 
Proposição 1.1.8. Se são inteiros com e 
 , então . 
Proposição 1.1.9. 
 com são inteiros com 
 positivos, então 
Exemplo 1.1.10. 
 . 
Teorema 1.1.11. (Pequeno Teorema de Fermat) Seja 
primo. Se 
Corolário 1.1.12. Se é um primo e é um inteiro positivo 
então 
Exemplo 1.1.13. Achar o resto da divisão de por 13. 
 
 
 
 
 
 
 
 
3 
 
 
 
 
 
 
Observação 1.1.14. 
(i) 
(ii) 
Exemplo 1.1.15. Mostrar que 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.2. CONGRUÊNCIA LINEAR 
Chamamos de congruência linear em uma variável a uma 
congruência da forma onde é uma 
incógnita. 
Se então . 
Isto é transformamos em uma equação com duas variáveis. 
Nem sempre essa equação tem solução. 
Definição 1.2.1. Uma equação da forma onde 
 são inteiros é chamada equação Diofantina linear. 
Proposição 1.2.2. Seja inteiros e 
 então a equação não possui nenhuma solução 
inteira. Se ela possui infinitas soluções e se e 
 uma solução particular, então todas as soluções 
são dadas por e onde k é 
um inteiro. 
 
 
 
4 
 
 
Exemplo 1.2.3. Achar o menor múltiplo de 7 que deixa resto 
1 quando dividido por 2,3,4,5,6.