Criptografia

UNICAMP - Universidade Estadual de Campinas
Faculdade de Engenharia El´etrica e Computa¸ca˜o
Mestrado em Engenharia El´etrica - FEEC

Teorema da Divis˜ ao Euclidiana, (MDC)
M´
aximo Divisor Comum, Aritm´etica
Modular e suas Propriedades

Leandro Aparecido Sangalli
P´os-Graduando em Engenharia El´etrica - DCA/FEEC

Mar¸co de 2012
Campinas - SP

“Existe algo que ´e mais forte do que o talento: chama-se determina¸ca˜o.”
Ory Rodrigues

´
SUMARIO

1 Divisibilidade em Z
1.1

1

Divis˜ao Exata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2 Algoritmo da Divis˜ ao Euclidiana

3

3 M´ aximo Divisor Comum (MDC)

5

4 Aritm´ etica Modular

9

4.1

Aritm´etica Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.2

Aplica¸co˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.2.1

Algoritmo de C´esar . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4.3

Bibliografia

16

ix

˜
INTRODUC
¸ AO

Neste trabalho, apresentaremos conceitos sobre o Algoritmo da divis˜ao Euclidiana, (MDC)
M´aximo Divisor Comum e Congruˆencia, enfatizando as principais propriedades e demonstra¸co˜es referentes a esses conte´ udos. xii

CAP´ITULO 1
DIVISIBILIDADE EM Z

1.1

Divis˜ ao Exata

Defini¸c˜ ao 1.1.1. Diz-se que o n´ umero inteiro a ´e divisor do n´ umero inteiro b (ou divide b) ou que o n´ umero b ´e divis´ıvel por a se ´e poss´ıvel encontrar c ∈ Z, tal que b = a.c. Neste caso, pode-se dizer tamb´em que b ´e m´ ultiplo de a. Para indicar que a divide b, usaremos a nota¸c˜ao a|b.
A rela¸c˜ao entre elementos de Z, definida por x|y, que acabamos de introduzir, goza das seguintes propriedades:
Proposi¸c˜
ao 1.1. (i) a|a (Reflexiva)
Demonstra¸c˜
ao 1.1.1. De fato, a = a.1, ou seja, a|a.

(ii) Se a, b ≥