UNICAMP - Universidade Estadual de Campinas
Faculdade de Engenharia Elétrica e Computação
Mestrado em Engenharia Elétrica - FEEC
Teorema da Divisão Euclidiana, (MDC)
Máximo Divisor Comum, Aritmética
Modular e suas Propriedades
Leandro Aparecido Sangalli
Pós-Graduando em Engenharia Elétrica - DCA/FEEC
Março de 2012
Campinas - SP
“Existe algo que é mais forte do que o talento:
chama-se determinação.”
Ory Rodrigues
SUMÁRIO
1 Divisibilidade em Z
1.1
1
Divisão Exata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2 Algoritmo da Divisão Euclidiana
3
3 Máximo Divisor Comum (MDC)
5
4 Aritmética Modular
9
4.1
Aritmética Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.2
Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.2.1
Algoritmo de César . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.3
Bibliografia
16
ix
INTRODUÇÃO
Neste trabalho, apresentaremos conceitos sobre o Algoritmo da divisão Euclidiana, (MDC)
Máximo Divisor Comum e Congruência, enfatizando as principais propriedades e demonstrações referentes a esses conteúdos.
xii
CAPÍTULO 1
DIVISIBILIDADE EM Z
1.1
Divisão Exata
Definição 1.1.1. Diz-se que o número inteiro a é divisor do número inteiro b (ou divide b)
ou que o número b é divisı́vel por a se é possı́vel encontrar c ∈ Z, tal que b = a.c. Neste
caso, pode-se dizer também que b é múltiplo de a. Para indicar que a divide b, usaremos a
notação a|b.
A relação entre elementos de Z, definida por x|y, que acabamos de introduzir, goza das
seguintes propriedades:
Proposição 1.1. (i) a|a (Reflexiva)
Demonstração 1.1.1. De fato, a = a.1, ou seja, a|a.
(ii) Se a, b ≥ 0, a|b e b|a, então a = b(Antisimétrica).
Demonstração 1.1.2. Por hipótese, b = a.c1 e a = b.c2 com c1 , c2 ∈ Z. Se a = 0 temos
b = 0 e se b = 0 temos a = 0. Suponhamos a, b > 0. Como a = a.c1 .c2 , segue que c1 .c2 = 1.
Porém c1 e c2 são inteiros positivos, logo, essa igualdade só é possivel para c1 = c2 = 1. O
que nos dá a = b.
1
Seção 1.1 •
Divisão Exata
2
(iii) Se a|b e b|c, então a|c (Transitiva).
Demonstração 1.1.3. Por hipótese, a|b, então b = a.c1 e b|c então c = b.c2 , para algum
c1 , c2 ∈ Z, então c = (a.c1 ).c2 , ou seja, c é múltiplo de a, então a|c.
Proposição 1.2. Se a|b e a|c, então a|(b.x + c.y), quaisquer que sejam os inteiros x e y.
Demonstração 1.1.4. Por hipótese, b = a.d1 e c = a.d2 . Daı́, b.x = a.(x.d1 ) e c.y =
a.(y.d2 ). Agora, somando membro a membro dessa igualdade, obtemos:
b.x + c.y = a.(x.d1 ) + a.(y.d2 ) = a.(x.d1 + y.d2 ), como bx + cy é um múltiplo de a. Então
segue que a|(b.x + c.y).
Proposição 1.3. Se a|b e c|d, então a.c|b.d
Demonstração 1.1.5. Por hipótese, b = a.r e d = c.s para inteiros convenientes r e s.
Multiplicando ambos, membro a membro, obtemos b.d = (a.c)(r.s). Como b.d é um múltiplo
de a.c. Então a.c|b.d.
CAPÍTULO 2
ALGORITMO DA DIVISÃO
EUCLIDIANA
Teorema 2.1. (Algoritmo da Divisão Euclidiana) Dados dois inteiros a e b, com
b > 0, existem e são únicos q e r também inteiros, tais que a = b.q + r, com 0 ≤ r < b.
Demonstração 2.0.6. Vamos provar que dado b > 0 e a ∈ Z, conseguimos q, r ∈ Z tais
que a = b.q + r, com 0 ≤ r < b.
Assim, temos duas possibilidades:
(i) a é múltiplo de b;
(ii) a não é múltiplo de b.
Se (i) ocorre, podemos dizer que b|a e escrever a = b.q, para um certo q ∈ Z, tendo r = 0.
Caso contrário, se (ii) ocorre, temos que a está situado entre dois múltiplos consecutivos de
b, isto é, existe um inteiro q tal que b.q < a < b.(q + 1). Desta forma, 0 < a − b.q < b,
agora fazendo r = a − b.q, temos que 0 < r < b. Ou seja, se a não é múltiplo de b, podemos
escrever a = b.q + r, para um certo q, r ∈ Z, com 0 < r < b.
Assim, por (i) e (ii), segue que dados dois inteiros a e b, com b > 0, temos que existem dois
inteiros q e r, tais que a = b.q + r em que 0 ≤ r < b.
Vamos garantir agora a unicidade de q e r. Suponhamos que exista outro par de inteiros q1 e
r1 , tais que a = b.q1 +r1 , com 0 ≤ r1 < b. Então, b.q +r = b.q1 +r1 , assim, b(q −q1 ) = r1 −r.
Suponhamos por absurdo que r1 6= r. Considerando sem perda de generalidade que r > r1 ,
3
4
Daı́, r1 − r < 0 e como b > 0, temos q − q1 < 0.
Como q1 6= q, vamos supor sem perda de generalidade que q1 > q, assim, q1 − q > 0, ou seja,
q1 − q ≥ 1. Como b(q − q1 ) = r1 − r, segue que r = r1 − b.(q − q1 ) entâo r = r1 + b.(q1 − q),
o que desta forma nos dá, r ≥ b (Absurdo), pois, 0 ≤ r < b. Portanto, q = q1 e r = r1
Prova-se de maneira análoga o caso r < r1 .
Exemplo 2.1. (i) a = 11; b = 7 então 11 = 7.1 + 4, assim temos q = 1 e r = 4
(ii) a = −11; b = 7 então −11 = 7.(−2) + 3, assim temos q = −2 e r = 3
CAPÍTULO 3
MÁXIMO DIVISOR COMUM
(MDC)
Considerando os inteiros 4 e 6, podemos encontrar facilmente seus divisores sendo eles:
D(4) = {±1, ±2, ±4} e D(6) = {±1, ±2, ±3, ±6}.
Assim, os elementos em comum entre os conjuntos D(4) e D(6) são os divisores comuns entre
estes dois inteiros. Ou seja,
D(4) ∩ D(6) = {±1 ± 2}.
Logo o maior divisor comum entre 4 e 6 é o elemento máximo do conjunto D(4) ∩ D(6),
neste caso é o 2.
Definição 3.0.2. Sejam a, b ∈ Z. Um número d ∈ Z se diz máximo divisor comum de a e
b se:
• d > 0;
• d|a e d|b;
• Se c ∈ Z for tal que c|a e c|b, então c|d.
Proposição 3.1. Se d e d1 são máximos divisores comuns de a e b, então d = d1 . Ou seja,
se d é um máximo divisor comum entre a e b então d é único.
5
6
Demonstração 3.0.7. Por hipótese d é o máximo divisor comum de a e b então d ≥ 0, d|a
e d|b, como d1 |a e d1 |b (hipótese de que d1 é o máximo divisor de a e b), pela definição de
máximo divisor comum, temos que d1 |d e de forma análoga d|d1 , como estamos tratando de
números inteiros estritamentes positivos, podemos afirmar que d = d1 .
Proposição 3.2. Se d é o máximo divisor comum de a e b, então d também é máximo
divisor comum de −a e b.
Demonstração 3.0.8. Podemos escrever (−a) = (−1).a. Ou seja, (−a) é múltiplo de a.
Desta forma, d|(−a). Portanto, mdc((−a), b) = d.
Podemos mostrar de maneira análoga para os casos em que d = mdc(a, −b) e d = mdc(−a, −b).
Proposição 3.3. Se a|b então mdc(a, b) = a.
Demonstração 3.0.9. Sabemos de imediato que a|a. Por hipótese a|b, ou seja a é divisor
de a e b. Devemos mostrar agora que a é o maior desses divisores em comum. Suponhamos
que exista c ∈ Z tal que c|a e c|b, pelo fato de c|a, temos que c ≤ a. Logo, mdc(a, b) = a.
Proposição 3.4. Se d|a e d|b, então d|(a ± b).
Demonstração 3.0.10. Por hipótese, d|a então podemos escrever a = d.n1 e também por
hipótese d|b então podemos escrever b = d.n2 . Lembrando que vamos provar que d|(a + b).
Pela relação descrita acima, podemos escrever a + b = (d.n1 ) + (d.n2 ) = (d.n1 + d.n2 ) =
d.(n1 + n2 ).Como a + b = d(n1 + n2 ) e n1 ; n2 ∈ Z então n1 + n2 ∈ Z. Assim podemos dizer
que d|(a + b).
Cap. 3 •
Máximo Divisor Comum (MDC)
7
De modo análogo, mostramos que Se d|a e d|b então d|(a − b).
Proposição 3.5. Se a = b.q + r e d = mdc(a, b), então d = mdc(b, r). E se d = mdc(b, r)
então, d = mdc(a, b).
Demonstração 3.0.11. Por hipótese, temos que d = mdc(a, b), então d|a e d|b. Pelo fato
de d|b temos que d|b.q, com q ∈ Z. Então, pela Proposição (3.4) temos que d|(a − b.q),
ou seja, d|r. Se existe c ∈ Z de tal forma que c|b e c|r então c|(b.q + r), ou seja, c|a.
Assim, como c|a e c|b então c|d, já que d = mdc(a, b). Como d|b e d|r e c|d, concluı́mos que
d = mdc(b, r). De maneira análoga mostramos que se d = mdc(b, r), então d = mdc(a, b).
O resultado a seguir garante a existência do máximo divisor comum.
Proposição 3.6. O Objetivo do método que será apresentado agora é encontrar o máximo
divisor comum de dois inteiros a e b, por meio de aplicações sucessivas do algoritmo euclidiano.
a
=
b.q1 + r1 ; (r1 < b)(∗)
b
=
r1 .q2 + r2 ; (r2 < r1 )
r1
..
.
=
r2 .q3 + r3 ; (r3 < r2 )
rn−2 = rn−1 .qn + rn (rn < rn−1 )
rn−1 =
rn .qn+1
Se em (∗) ocorrer r1 = 0, podemos dizer de acordo com a Proposição (3.3) que o máximo
divisor comum entre a e b existe e é b. Suponhamos r1 6= 0, assim temos b > r1 > r2 >
... > rn−1 , para algum n ∈ N. Desta forma, teremos em algum momento um resto rn+1 = 0.
Então, podemos escrever rn−1 = rn .qn+1 , que pelas proposições anteriores, podemos afirmar
que rn = mdc(rn−1 , rn ) = ... = mdc(b, r1 ) = mdc(a, b). Ou seja, rn = mdc(a, b). Este método
é chamado de Método da Divisão Sucessiva.
8
Exemplo 3.7. Vamos determinar pelo processo das divisões sucessivas, o mdc(41, 12)
41 = 12.3 + 5
12 = 5.2 + 2
5 = 2.2 + 1
2 = 1.2 + 0
Portanto o mdc(41, 12) = 1
Proposição 3.8. Se d = mdc(a, b), então mdc(sa, sb) = sd, para todo s ∈ Z.
Demonstração 3.0.12. Vamos multiplicar por s o cada uma das igualdades obtidas pelo
algoritmo da divisão sucessiva que nos da o mdc(a, b) = d. Assim, temos:
s.a
=
(s.b).q1 + r1 ; (r1 < b)
s.b
=
(s.r1 ).q2 + r2 ; (r2 < r1 )
s.r1
..
.
= s.r2 .q3 + r3 ; (r3 < r2 )(∗)
s.rn−2 =
(s.rn−1 ).qn + rn
s.rn−1 =
(s.rn ).qn+1
Então, vemos pelo método da divisão sucessiva que, d = rn :
s.d = s.rn |{z}
= mdc(s.rn−1 , s.rn ) = · · · = mdc(s.b, s.r1 ) |{z}
= mdc(sa, sb). Podemos obter (∗)
∗
∗∗
aplicando a Proposição (3.3) e podemos obter (∗∗) aplicando a Proposição (3.5). Assim,
podemos concluir que se mdc(a, b) = d então s.d = mdc(s.a, s.b).
Corolário 3.8.1. Se a|b.c e mdc(a, b) = 1, então a|c.
Demonstração 3.0.13. Segue da Proposição (3.8) que se o mdc(a, b) = 1, então mdc(c.a, c.b) =
c, da hipótese temos que a|b.c e obviamente a|a.c. Logo, pela definição de máximo divisor
comum a|mdc(a.c, b.c), De onde concluı́mos que a|c.
CAPÍTULO 4
ARITMÉTICA MODULAR
4.1
Aritmética Modular
“O conceito de congruência se tornou um dos instrumentos mais fortes da Teoria dos
Números, foi introduzido por Karl Friedrich Gauss (1777-1855) em sua obra Disquisitiones
Arithmeticae de 1801.(Domingues, p. 124, 1991).”
Antes de estudarmos as propriedades da relação de Congruência, destacaremos que esta
ferramenta da álgebra pode ser usada para resolver problemas do nosso cotidiano como por
exemplo, responder a seguinte questão:
Se hoje é sábado, daqui a 1520 dias, que dia da semana será? E há 1520 dias,
que dia da semana foi?
Definição 4.1.1. Sejam a,b e m números inteiros, m > 0. Dizemos que a é congruo a b,
módulo m, se m|(a − b). Notação, a ≡ b(mod m).
Exemplo 4.1. (i) 73 ≡ 4(mod23), pois 23|73 − 4 ou ainda, 73(mod23) = 4(mod23)
Exemplo 4.2. (ii) 21 ≡ −9(mod10), pois 10|21 + 9 ou ainda 21(mod10) = −9(mod10)
Corolário 4.2.1. Se a ≡ b(mod m) então a.c ≡ b.c(mod m).
Demonstração 4.1.1. Por hipótese temos que a ≡ b(mod m), ou seja, m|(a − b). Logo,
m|(a − b).c, ou seja, m|(a.c − b.c), então a.c ≡ b.c(mod m).
As congruências têm as seguintes propriedades:
9
Seção 4.1 •
Aritmética Modular
10
Proposição 4.3. [a(modn)] + [b(modn)] = a + b(modn)
Proposição 4.4. [a(modn)] − [b(modn)] = a + b(modn)
Proposição 4.5. [a(modn)].[b(modn)] = a.b(modn)
As demonstrações das proposições anteriores estão disponı́veis na referência [6] desse
trabalho.
Observação 4.5.1. A congruência módulo n é uma relação de equivalência no sentido que
a ≡ a, se a ≡ b então b ≡ a e se a ≡ b e b ≡ c então a ≡ c para todos os números inteiros
a, b, c. Isto permite decompor o conjunto dos números inteiros como união finita disjunta de
todas as classes de equivalência. O conjunto dessas classes de equivalência tem n elementos
e é representado por Zn , onde Zn = {0, 1, ..., n − 1}.
Exemplo 4.6. O conjunto das classe de equivalência de Z5 é:
Z5 = {0, 1, 2, 3, 4}
Propriedades da aritmética modular para inteiros módulo n: Dados w, x, y, z ∈ Zn , temos:
Proposição 4.7. (Leis Comutativas) (w + x)mod(n) = (x + w)mod(n) e
(w.x)mod(n) = (x.w)mod(n)
Proposição 4.8. (Leis Associativas) [(w + x) + y]mod(n) = [w + (x + y)]mod(n) e
[(w.x).y]mod(n) = [w.(x.y)]mod(n)
Proposição 4.9. (Leis Distributivas) [w.(x + y)]mod(n) = [(w.x) + (w.y)]mod(n) e
[(w.x).y]mod(n) = [w.(x.y)]mod(n)
Proposição 4.10. (Identidades) (0 + w)mod(n) = (w)mod(n) e
(1.w)mod(n) = (w)mod(n)
Proposição 4.11. (Inverso Aditivo (−w)) Para cada w ∈ Zn existe um z, de modo que
w + z ≡ 0(modn)
Cap. 4 •
Aritmética Modular
As demonstrações das proposições anteriores estão disponı́veis na referência [6] desse trabalho.
Podemos desenvolver operações com elementos do conjunto das classes de equivalência
normalmente, assim como operamos nos conjuntos usuais.
Exemplo 4.12. Tabela de operações em Z4 = {0, 1, 2, 3} = {−1, 0, 1, 2}
4.2
4.2.1
Aplicações
Algoritmo de César
Um dos métodos mais antigos de criptografia foi criado pelo Imperador de Roma Júlio César,
por volta do ano 50 A.C. Este método consiste na substituição de uma letra por outra três
posições adiante na tabela de codificação.
11
Seção 4.2 •
Aplicações
12
ALGORITMO DE CIFRAGEM
Se P é a letra a qual queremos cifrar e C é o número correspondente a letra já cifrada
na tabela anterior, então, o algoritmo é executado da seguinte forma:
C ≡ n(P )+3(mod 26), onde n(P ) é o número correspondente a letra P na tabela anterior
.
ALGORITMO DE DECIFRAGEM
Para descobrir o P a partir de C, basta aplicar o procedimento reverso da congruência:
P ≡ C − 3(mod 26)
Exemplo 4.13. Vamos utilizar o algoritmo de Cesár, para cifrar a palavra CASA.
CIFRAGEM:
De acordo com a tabela as letras da palavra CASA, ocupam as seguintes posições.
P1 = C, onde n(P1 ) = 2
P2 = A, onde n(P2 ) = 0
P3 = S, onde n(P3 ) = 18
P4 = A, onde n(P4 ) = 0
Agora vamos cifrar essas letras de acordo com o algoritmo. Obtendo os seguintes C’s como
blocos cifrados:
C1 = 5 = F
C2 = 3 = D
C3 = 21 = V
C4 = 3 = D
Cap. 4 •
Aritmética Modular
13
DECIFRAGEM:
Para decifrar da mensagem recebida (FDVD), executamos o algoritmo inverso de cifragem.
Obtendo os seguintes P ’s:
P1 = C
P2 = A
P3 = S
P4 = A
Nossa mensagem original.
Seção 4.3 •
4.3
Exercı́cios
14
Exercı́cios
1. O Máximo Divisor Comum de dois números x e y é 20. Para se chegar a esse resultado
pelo processo das divisões sucessivas, os quocientes encontrados foram, pela ordem, 2,
1, 3 e 2. Determine x e y.
Solução: Vamos observar a seguinte tabela que pode ser construida pelo Método das
Divisões Sucessivas
2
1
3
2
a
b
r1
r2
r3 = 20
r1
r2
r3
0
Assim, temos os seguintes valores:
r3 = 20; r2 = 2.r3 = 40; r1 = 3.r2 + r3 = 140; b = r1 + r2 = 180 e a = 2.b + r1 = 500
Desta forma, podemos afirmar que os dois números cujo o máximo divisor comum entre
eles é 20 são 180 e 500.
2. Se hoje é Sexta-Feira, que dia da semana será daqui a 1520 dias?
Solução: Indiquemos por 0 o dia de hoje (Sexta-Feira), por 1 o dia de amanhã
(Sábado), e assim por diante. Vamos observar a seguinte tabela:
Sexta Sábado
Domingo Segunda Terça
Quarta Quinta
0
1
2
3
4
5
6
7
8
9
10
11
12
13
...
...
...
...
...
...
...
Desta forma, devemos descobrir em qual coluna da tabela se encontra o número 1520.
Para isso,basta observar que dois números estão na mesma coluna se e somente se,
sua diferença é divisı́vel por 7. Suponhamos que o número 1520 se encontra na coluna
encabeçada pelo número a, onde 0 ≤ a ≤ 6, assim
1520 − a = 7q, para algum q ∈ Z+
Assim temos,
Cap. 4 •
Aritmética Modular
15
1520 = 7q + a
Pela unicidade do resto na divisão euclidiana, segue desta desigualdade que a é o resto
da divisão de 1520 por 7, ou seja, 1520 = 7.217 + 1, logo concluı́mos que a = 1, desta
forma, 1520 está na segunda coluna da tabela. portando daqui 1520 dias será um
sábado.
3. Mostre que o número 220 − 1 é divisı́vel por 41.
Solução: 220 − 1 é divisı́vel por 41 se e somente se, 220 − 1 ≡ 0(mod41). Ou seja,
220 ≡ 1(mod41). Desta forma,
220 = (26 )3 22 ≡ (23)3 22 ≡ 31.4 ≡ 1(mod41).
Logo, 220 ≡ 1(mod41)
Portanto, 220 − 1 é divisı́vel por 41
REFERÊNCIAS BIBLIOGRÁFICAS
[1] COUTINHO, S. C. Números Inteiros e Criptografia RSA. Rio de Janeiro: IMPA, 2009.
[2] VIDIGAL, A.; AVRITZER D.; SOARES, E.F.; BUENO, H. P.; FERREIRA, M. C. C.;
FARIA, M. C. Fundamentos de Álgebra. Belo Horizonte: Editora UFMG, 2009.
[3] DOMINGUES, H. H. Fundamentos de Aritmética. São Paulo: Atual, 1991.
[4] DOMINGUES, H. H.; IEZZI, G. Álgebra Moderna. São Paulo: Atual, 2003.
[5] SANTOS, J. P. O.; Teoria dos Números.Rio de Janeiro: Associação Instituto Nacional
de Matemática Pura e Aplicada, 2003.
[6] STALLINGS, W.; Criptografia e segurança de Redes. 4 ed. São Paulo: Pearson Prentice
Hall, 2008.
16