Aula 13-Aritmética Modular

Prévia do material em texto

Álgebra Modular
Se m é um número inteiro positivo e a ∈ Z, denotamos por a mod m o resto da divisão
de a por m. Ou seja, a mod m = r, onde r é o número inteiro que satisfaz 0 ≤ r < m e
a = m · q + r, q ∈ Z
Observação 1. Lemos a mod m como "a módulo m".
Exemplo 1. Determine a mod m para os valores de a e m dados.
(a) a = 133 e m = 57
133 = 57 · 2 + 19
Logo, 133 mod 57 = 19.
(b) a = 33 e m = 15
33 = 15 · 2 + 3
Logo, 33 mod 15 = 3.
(c) a = −33 e m = 15
−33 = 15 · (−3) + 12
Logo, (−33) mod 15 = 12.
(d) a = −735 e m = 20
735 = 20 · 36 + 15
−735 = 20 · (−37) + 5
Logo, (−735) mod 20 = 5.
(e) a = 5 e m = 17
5 = 17 · 0 + 5
Logo, 5 mod 17 = 5.
(f) a = −5 e m = 15
−5 = 15 · (−1) + 10
Logo, (−5) mod 15 = 10.
(g) a = 0 e m = 23
0 = 23 · 0 + 0
Logo, 0 mod 23 = 0.
(h) a = 16 e m = 8
16 = 8 · 2 + 0
Logo, 16 mod 8 = 0.
Observe que
(1) Se a = 0 e m ∈ N, então 0 = m · 0 + 0. Logo,
1
0 mod m = 0 para todo m ∈ N
(2) Se a ∈ Z e m = 1, então a = 1 · a+ 0. Logo,
a mod 1 = 0 para todo a ∈ Z
(3) Se a ≥ 0 e a < m, então a = m · 0 + a. Logo,
a mod m = a para todo a ∈ Z+ satisfazendo a < m
(4) Se a é um múltiplo de m, então existe b ∈ Z tal que a = m · b = m · b+ 0. Logo,
a mod m = 0 para todo a ∈M(m)
Definição 1. Sejam a, b ∈ Z e m ∈ N. Dizemos que a é congruente com b módulo m e
escrevemos que a ≡ b( mod m) se
a mod m = b mod m
ou seja, se os restos da divisão de a por m e de b por m são iguais. Se a e b não são congruentes
módulo m, então escrevemos que a��≡b( mod m).
Exemplo 2. Determine se a ≡ b( mod m) para os valores de a, b e m dados.
(a) a = 1419, b = 71 e m = 13
1419 = 13 · 109 + 2
Logo, 1419 mod 13 = 2.
71 = 13 · 5 + 6
Logo, 71 mod 13 = 6.
Concluímos que 1419��≡71( mod 13).
(b) a = −475, b = 307 e m = 17
475 = 17 · 27 + 16
−475 = 17 · (−28) + 1
Logo, (−475) mod 17 = 1.
307 = 17 · 18 + 1
Logo, 307 mod 17 = 1.
Concluímos que (−475) ≡ 307( mod 17).
Proposição 1. Se a, b ∈ Z e m ∈ N, então a ≡ b( mod m) se, e somente se, (a− b) ∈M(m).
Demonstração: Vamos mostrar inicialmente que
a ≡ b( mod m) → (a− b) ∈M(m)
Suponha que a ≡ b( mod m). Os restos das divisões de a por m e de b por m são iguais.
Suponha que a mod m = b mod m = r. Existem números q1, q2 ∈ Z tais que
a = m · q1 + r
2
b = m · q2 + r
Logo,
(a− b) = (m · q1 + r)− (m · q2 + r) = m · q1 + r −m · q2 − r = m · q1 −m · q2 = m · (q1 − q2)
Como q1 − q2 ∈ Z, então (a − b) = m · (q1 − q2) implica que (a − b) é um múltiplo de m e,
portanto, (a− b) ∈M(m).
Vamos mostrar agora a recíproca do resultado, ou seja, vamos mostrar que
(a− b) ∈M(m) → a ≡ b( mod m)
Suponha que (a− b) ∈M(m). Existe k ∈ Z tal que a− b = m · k. Suponha que b mod m = r.
Temos que b = m · q1 + r, onde 0 ≤ r < m, q1 ∈ Z. Portanto,
a− b = m · k
a− (m · q1 + r) = m · k
a−m · q1 − r = m · k
a = m · k +m · q1 + r
a = m · (k + q1) + r
Se tomarmos q2 = k + q1, então q2 ∈ Z e a = m · q2 + r com 0 ≤ r < m. Portanto, q2 é
o quociente e r é o resto da divisão de a por m. Concluímos que a mod m = r. Como b
mod m = r também, então a ≡ b( mod m).
Exemplo 3. Em cada caso, determine se a ≡ b( mod m).
(a) a = 416, b = 411 e m = 5.
Como a− b = 416− 411 = 5 ∈M(5), então 416 ≡ 411( mod 5)
(b) a = 617, b = 604 e m = 5.
Como a− b = 617− 604 = 13 /∈M(5), então 617��≡617( mod 5)
(c) a = 471, b = 438 e m = 11.
Como a− b = 471− 438 = 33 ∈M(11), então 471 ≡ 438( mod 11)
(d) a = 471, b = 438 e m = 3.
Como a− b = 471− 438 = 33 ∈M(3), então 471 ≡ 438( mod 3)
(e) a = 715, b = 411 e m = 10.
Como a− b = 715− 411 = 304 /∈M(10), então 715��≡411( mod 10)
(f) a = 603, b = 617 e m = 7.
Como a− b = 603− 617 = −14 ∈M(7), então 603 ≡ 617( mod 7)
(g) a = 603, b = 617 e m = 2.
Como a− b = 603− 617 = −14 ∈M(2), então 603 ≡ 617( mod 2)
3
Proposição 2. Se m ∈ N e a, k ∈ Z, então a ≡ a+ km( mod m).
Prova: Temos que a mod m = r, onde a = qm + r, q ∈ Z é o quociente e 0 ≤ r < m é o
resto da divisão de a por m. Temos então que
a+ km = qm+ r + km = (q + k)m+ r
Logo, q + k é o quociente e r é o resto da divisão de a + km por m. Portanto, r = (a + km)
mod m e concluímos que
a mod m = (a+ km) mod m ⇒ a ≡ a+ km( mod m)
Exemplo 4. 6 ≡ 19( mod 13), pois 19 = 6 + 13
3 ≡ 29( mod 13), pois 29 = 3 + 26 = 3 + 2 · 13
3 ≡ −23( mod 13), pois −23 = 3− 26 = 3− 2 · 13
Definição 2. Seja a ∈ Z. Chamamos o conjunto a = {b ∈ Z | b ≡ a( mod m)} de classe de
equivalência de a módulo m.
Se denotarmos o resto da divisão de a por m por ra, então
a = {b ∈ Z | b = m · q + ra, onde q ∈ Z}
Em outras palavras, a é o conjunto de todos os números obtidos dos múltiplos de a por uma
soma por ra.
Observe que se a ≡ b( mod m), então a = b
Como existem exatamente m restos possíveis na divisão por m (são eles 0, 1, 2, 3, ...,m− 1),
então existem exatamente m classes de equivalência módulo m:
0, 1, 2, 3, ..., m− 1
Observe que
0 = {b ∈ Z | o resto da divisão de b por m é 0} =M(m)
Exemplo 5. Em cada caso, determine todas as classes de equivalência módulo m.
(a) m = 6.
Temos 6 restos possíveis na divisão por 6. São eles: 0, 1, 2, 3, 4, 5. Logo, existem 6 classes
de equivalência módulo 6:
• 0 =M(6) = {...,−18,−12,−6, 0, 6, 12, 18, ...}
• 1 = {...,−17,−11,−5, 1, 7, 13, 19, ...}
• 2 = {...,−16,−10,−4, 2, 8, 14, 20, ...}
• 3 = {...,−15,−9,−3, 3, 9, 15, 21, ...}
• 4 = {...,−14,−8,−2, 4, 10, 16, 22, ...}
• 5 = {...,−13,−7,−1, 5, 11, 17, 23, ...}
(b) m = 2.
Temos 2 restos possíveis na divisão por 2. São eles: 0, 1. Logo, existem apenas 2 clas-
ses de equivalência módulo 2:
4
• 0 =M(2) = {b ∈ Z | b é par }
• 1 = {b ∈ Z | b é ímpar }
(c) m = 1.
Temos apenas 1 resto possível na divisão por 1: 0. Logo, existe apenas 1 classe de equiva-
lência módulo 1:
0 =M(1) = Z
Conjunto dos inteiros módulo m
Chamamos o conjunto {0, 1, 2, 3, ...,m− 1} de conjunto dos inteiros módulo m e o denotamos
por Zm. Ou seja,
Zm = {0, 1, 2, 3, ...,m− 1}
Observe que Zm é o conjunto de todos os restos possíveis na divisão porm. Nós trabalhamos
com esse conjunto de forma bem diferente do que nós trabalhamos com os conjuntos de números
vistos até então.
Vamos definir inicialmente as operações de soma, subtração, produto e divisão nesse con-
junto.
Definição 3. Sejam m ∈ N e a, b ∈ Zn.
Definimos a soma módulo m dos números a e b como sendo o número (a+ b) mod m. Deno-
tamos a soma módulo m por ⊕ para diferenciá-la da soma tradicional de números inteiros. Ou
seja,
a⊕ b = (a+ b) mod m
onde (a+ b) mod m é o resto da divisão do número inteiro a+ b por m.
Definimos o produto módulo m dos números a e b como sendo o número (a · b) mod m. Deno-
tamos o produto módulo m por ⊗ para diferenciá-la do produto tradicional de números inteiros.
Ou seja,
a⊗ b = (a · b) mod m
onde (a · b) mod m é o resto da divisão do número inteiro a · b por m.
Observe que (a⊕ b) mod m ∈ Zm e (a⊗ b) mod m ∈ Zm.
Exemplo 6. Calcule a⊕ b e a⊗ b módulo 7 nos seguintes casos:
(a) a = 1, b = 6
a+ b = 7. Como 7 mod 7 = 0, então a⊕ b = 0
a · b = 6. Como 6 mod 7 = 6, então a⊗ b = 6
(b) a = 3, b = 5
a+ b = 8. Como 8 mod 7 = 1, então a⊕ b = 1
a · b = 15. Como 15 mod 7 = 1, então a⊗ b = 1
5
(c) a = 4, b = 4
a+ b = 8. Como 8 mod 7 = 1, então a⊕ b = 1
a · b = 16. Como 16 mod 7 = 2, então a⊗ b = 2
(d) a = 0, b = 5
a+ b = 5. Como 5 mod 7 = 5, então a⊕ b = 5
a · b = 0. Como 0 mod 7 = 0, então a⊗ b = 0
Exemplo 7. Calcule as seguintes somas e produtos módulo 13:
(a) 3⊕ 11
3 + 11 = 14. Como 14 mod 13 = 1, então 3⊕ 11 = 1
(b) 12⊗ 11
12 · 11 = 132. Como 132 mod 13 = 2, então 12⊗ 11 = 2
(c) 10⊕ 7
10 + 7 = 17. Como 17 mod 13 = 4, então 10⊕ 7 = 4
(d) 10⊗ 7
10 · 7 = 70. Como 70 mod 13 = 5, então 10⊗ 7 = 5
Se m ≥ 2, então algumas propriedades da soma e do produto módulo m são:
(1) a⊕ 0 = a para todo a ∈ Zm (pois a+ 0 = a e a ∈ Zm).
(2) a⊗ 0 = 0 para todo a ∈ Zm (pois a · 0 = 0 e 0 ∈ Zm).
(3) a⊗ 1 = a para todo a ∈Zm (pois a · 1 = a e a ∈ Zm).
(4) a⊕ b = b⊕ a para todo a, b ∈ Zm (pois a+ b = b+ a).
(5) a⊗ b = b⊗ a para todo a, b ∈ Zm (pois a · b = b · a).
(6) a⊗ (b⊕ c) = (a⊗ b)⊕ (a⊗ c) para todo a, b, c ∈ Zm.
(7) a⊗ (b⊗ c) = (a⊗ b)⊗ (a⊗ c) para todo a, b, c ∈ Zm.
(8) a⊕ (b⊕ c) = (a⊕ b)⊕ (a⊕ c) para todo a, b, c ∈ Zm.
6
Proposição 3. Sejam m ∈ N e a, b ∈ Zm. Existe um único x ∈ Zm tal que a = b⊕ x.
Prova: Seja x = (a− b) mod m.
Como x é o resto da divisão de a − b por m, então 0 ≤ x < m. Logo, x ∈ Zm. Além disso,
temos que
a− b = m · q + x ⇒ x = a− b−m · q
Logo, como 0 ≤ a < m, então
b⊕ x = (b+ x) mod m = (b+ a− b−m · q) ·m = (a−m · q) mod m = a
Concluímos que x satisfaz a equação a = b⊕ x.
Vamos mostrar agora que x é único.
Suponha que x, y ∈ Zm, que a = b⊕ x e que a = b⊕ y.
b⊕ x = (b+ x) mod m = b+ x+ km = a
b⊕ y = (b+ y) mod m = b+ y + cm = a
Logo,
b+ x+ km = b+ y + cm⇒ x+ km = y + cm
⇒ x = y + cm− km
⇒ x = y + (c− k)m
⇒ x ≡ y( mod m)
⇒ x mod m = y mod m
Como 0 ≤ x < m e 0 ≤ y < m, então x = y.
Definição 4. Sejam m ∈ N e a, b ∈ Zn.
Definimos a subtração módulo m dos números a e b como sendo o único número x ∈ Zm tal
que a = b⊕ x e a denotamos por a	 b.
Observe que pela proposição anterior, a	 b = (a− b) mod m.
Exemplo 8. Calcule as seguintes subtrações módulo 13:
(a) 3	 11
3− 11 = −8. Como −8 mod 13 = 5, então 3	 11 = 5
(b) 12	 11
12− 11 = 1. Como 1 mod 13 = 1, então 12	 11 = 1
(c) 7	 3
7− 3 = 4. Como 4 mod 13 = 4, então 7	 3 = 4
(d) 0	 11
0− 11 = −11. Como −11 mod 13 = 2, então 0	 11 = 2
7
A divisão modular será um pouco mais trabalhosa de definir. Muitas coisas que valem para
as operações de números inteiros não valem para as operações modulares. Por exemplo, se
x, y ∈ Z, então
5x = 5y ⇒ x = y
Entretanto, isso não é verdade nos inteiros módulo m. Por exemplo, em Z10, temos que
5⊗ 2 = 5⊗ 4
mas 2 6= 4.
Observe que não podemos definir a divisão de forma semelhante ao que fizemos para a
subtração, pois se definirmos a divisão de a por b modulo m como sendo o número x ∈ Zm que
satisfaz a = b ⊗ x, então esse número x pode não estar bem definido (como é possível ver no
exemplo abaixo).
Exemplo 9. Considere o conjunto Z10.
⊗ 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9
2 0 2 4 6 8 0 2 4 6 8
3 0 3 6 9 2 5 8 1 4 7
4 0 4 8 2 6 0 4 8 2 6
5 0 5 0 5 0 5 0 5 0 5
6 0 6 2 8 4 0 6 2 8 4
7 0 7 4 1 8 5 2 9 6 3
8 0 8 6 4 2 0 8 6 4 2
9 0 9 8 7 6 5 4 3 2 1
Pela tabela conseguimos ver que
(a) Se considerarmos a = 6 e b = 2, temos dois números distintos x ∈ Zn que satisfazem
6 = 2⊗ x, pois 2⊗ 3 = 6 e 2⊗ 8 = 6.
(b) Se considerarmos a = 7 e b = 2, não existe nenhum número x ∈ Zn que satisfaz 7 = 2⊗ x.
(c) Se considerarmos a = 7 e b = 3, então existe um único número x ∈ Zn que satisfaz 7 = 3⊗x
(que é o número 9).
Vamos tentar então outra abordagem.
Definição 5. Sejam m ∈ N, m ≥ 2 e a ∈ Zm. Dizemos que a é invertível se existir algum
x ∈ Zm tal que a⊗ x = 1.
Exemplo 10. Se considerarmos o conjunto Z10, então
• Os números 0, 2, 4, 5, 6, 8 não são invertíveis, pois nenhuma das multiplicações módulo 10
desses números com os outros números resulta em 1.
• O número 1 é invertível, pois 1⊗ 1 = 1.
• O número 3 é invertível, pois 3⊗ 7 = 1.
• O número 7 é invertível, pois 7⊗ 3 = 1.
• O número 9 é invertível, pois 9⊗ 9 = 1.
8
Proposição 4. Se m ∈ N, m ≥ 2 e se a ∈ Zm é invertível, então existe um único x ∈ Zm tal
que a⊗ x = 1.
Prova: Suponha que a é invertível. Suponha que a⊗ x = 1 e a⊗ y = 1. Então
x = x⊗ 1 = x⊗ (a⊗ y) = (x⊗ a)⊗ y = 1⊗ y = y
Ou seja, x = y.
Se o número a é invertível, então denotamos o único número x que satisfaz a ⊗ x = 1 por
a−1 e o chamamos de inverso de a.
Exemplo 11. Se considerarmos o conjunto Z10, então
• 1−1 = 1
• 3−1 = 7
• 7−1 = 3
• 9−1 = 9
Proposição 5. Se m ∈ N, m ≥ 2, se a ∈ Zm é invertível e b = a−1, então b também é invertível
e b−1 = a. Ou seja, (a−1)−1.
Definição 6. Seja m ∈ N e seja b um elemento invertível de Zm. Se a é um elemento qualquer
de Zm, então definimos a divisão de a por b como sendo o número a⊗ b−1 e a denotamos por
a� b.
Exemplo 12. Determine todos o elementos invertíveis de Z7 e determine seus inversos. Se
for possível, calcule as divisões
(a) 2� 3
(b) 5� 2
(c) 6� 6
(d) 4� 3
(e) 2� 1
Resolução:
⊗ 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
Logo, os números 1, 2, 3, 4, 5, 6 são invertíveis em Z7 (ou seja, todos os números não nulos de
Z7 são invertíveis. Temos ainda que
9
• 1−1 = 1
• 2−1 = 4
• 4−1 = 2
• 3−1 = 5
• 5−1 = 3
• 6−1 = 6
(a) 2� 3 = 2⊗ 3−1 = 2⊗ 5 = 10 mod 7 = 3
(b) 5� 2 = 5⊗ 2−1 = 5⊗ 4 = 20 mod 7 = 6
(c) 6� 6 = 6⊗ 6−1 = 6⊗ 6 = 36 mod 7 = 1
(d) 4� 3 = 4⊗ 3−1 = 4⊗ 5 = 20 mod 7 = 6
(e) 2� 1 = 2⊗ 1−1 = 2⊗ 1 = 2 mod 7 = 2
Observe que se m ≥ 3, então pelo menos dois números de Zm são invertíveis: o 1 e o m− 1.
De fato,
• Como 1⊗ 1 = 1, então 1−1 = 1.
Logo, a� 1 = a⊗ 1−1 = a⊗ 1 = a para todo a ∈ Zm.
• Como (m − 1)2 = m2 − 2m + 1 = m(m − 2) + 1, então (m − 1)2 mod m = 1. Logo,
(m− 1)⊗ (m− 1) = 1 e, portanto, (m− 1)−1 = m− 1.
Teorema 1. Sejam m ∈ N e a ∈ Zm. Temos que a é invertível se, e somente se mdc(a,m) = 1
Prova: Vamos provar inicialmente que se a é invertível, então mdc(a, b) = 1.
Suponha que a é invertível. Existe b ∈ Zm tal que a⊗ b = 1. Isso significa que
a · b mod m = 1 → a · b = m · q + 1
onde q é o quociente da divisão de a · b por m. Mas então
a · b−m · q = 1
Ou seja, a equação diofantina linear ax+my = 1 possui solução. Logo, 1 tem que ser múltiplo
de mdc(a,m). Mas, então 1 ≥ mdc(a,m) ≥ 1. Concluímos assim que mdc(a,m) = 1.
Vamos provar agora que se mdc(a,m) = 1, então a é invertível.
Suponha quemdc(a,m) = 1. A equação diofantina linear ax+my = 1 possui solução. Portanto,
existem números x, y ∈ Z tais que
a · x+m · y = 1
Seja x mod m = b. Isso significa que x = m · q + b. Temos então que
a · x+m · y = 1 ⇒ a · (m · q + b) +m · y = 1
⇒ a ·m · q + a · b+m · y = 1
⇒ a · b+m · (a · q + y) = 1
⇒ a · b = −m · (a · q + y) + 1
⇒ a · b mod m = 1
⇒ a⊗ b = 1
⇒ b = a−1
Concluímos assim que a é invertível.
10
Observação 2. A demonstração nos fornece uma forma de calcular a−1. Basta escrever o
mdc(a,m) = 1 como combinação linear de a e m
a · x+m · y = 1
para obter x e então determinar a−1 = x mod m.
Exemplo 13. Calcule em Z431:
(a) 29−1
(b) 30� 29
Resolução:
(a) Vamos utilizar o algoritmo de Euclides para determinar mdc(29, 431). Temos que
431 = 29 · 14 + 25
29 = 25 · 1 + 4
25 = 4 · 6 + 1
4 = 1 · 4 + 0
Logo, mdc(29, 241) = mdc(1, 0) = 1. Vamos escrever o mdc(29, 431) como combinação
linear de 29 e de 241.
431 = 29 · 14 + 25 → 25 = 431− 29 · 14
29 = 25 · 1 + 4 → 4 = 29− 25
25 = 4 · 6 + 1 → 1 = 25− 4 · 6
1 = 25− 4 · 6
= 25− (29− 25) · 6
= 25− 29 · 6 + 25 · 6
= 25 · 7− 29 · 6
= (431− 29 · 14) · 7− 29 · 6
= 431 · 7− 29 · 98− 29 · 6
= 431 · 7− 29 · 104
= 431 · 7 + 29 · (−104)
= 29 · (−104) + 431 · 7
Portanto,
29 · (−104) + 431 · 7 = 1
Temos então que 29−1 = (−104) mod 431. Como
−104 = 431 · (−1) + 327
então 29−1 = 327
(b) 30� 29 = 30⊗ 29−1 = 30⊗ 327 = 30 · 327 mod 431 = 9810 mod 431 = 328
Proposição 6. Se a, b ∈ Zm, se b é invertível, se b | a e se a÷ b = c, então a� b = c. Ou seja,
se a, b ∈ Zm, se b é invertível e se a é um múltiplo de b, então o resultado da divisão modular
a� b coincide com o resultado da divisão normal de números inteiros a÷ b.
11
Prova: Suponha que a, b ∈ Zm, que b é invertível e que b | a.
Como b | a, então a = c · b onde c ∈ Z. Como a, b ≥ 0, então 0 ≤ c ≤ a e, portanto, c ∈ Zm.
Temos que
1 = b⊗ b−1 = b · b−1 mod m
Logo, o resto da divisão de b · b−1 por m é 1. Ou seja,
b · b−1 = m · q + 1
Portanto,
a� b = a⊗ b−1
= a · b−1 mod m
= (c · b) · b−1 mod m
= c · (b · b−1) mod m
= c · (m · q + 1) mod m
= c ·m · q +c mod m
= c · q ·m+ c mod m
= c
Exemplo 14. Calcule 39� 13 em Z40.
Como mdc(13, 40) = 1, então 13 é invertível em Z40.
Como 39÷ 13 = 3, então 39� 13 = 3.
Exemplo 15. Calcule 4� 2 e 6� 2 em Z7.
Como mdc(2, 7) = 1, então 2 é invertível em Z7.
Como 4÷ 2 = 2, então 4� 2 = 2.
Como 6÷ 2 = 3, então 6� 2 = 3.
Exemplo 16. Calcule 46� 2 e 18� 2 em Z69.
Como mdc(2, 69) = 1, então 2 é invertível em Z69.
Como 46÷ 2 = 23, então 46� 2 = 23.
Como 18÷ 2 = 9, então 18� 2 = 9.
12