operações modulares

Prévia do material em texto

Operac¸o˜es modulares
As quatro operac¸o˜es matema´ticas usuais sa˜o a soma (+), subtrac¸a˜o (−), multiplicac¸a˜o (×) e
divisa˜o (÷ ou /). No contexto da aritme´tica modular tambe´m podemos definir essas operac¸o˜es, mas
para diferenciar os s´ımbolos, usamos ⊕ para a adic¸a˜o mod m, 	 para subtrac¸a˜o mod m, ⊗ para
multiplicac¸a˜o mod m e � para a divisa˜o mod m.
Vamos estudar cada uma delas:
Adic¸a˜o e multiplicac¸a˜o modulares
Definic¸a˜o: Sejam n um inteiro positivo e a, b ∈ Zn. Definimos
a⊕ b = (a+ b) mod n
a⊗ b = (a× b) mod n
Exemplo: Seja n = 10. Temos o seguinte:
5⊕ 5 = 0; 9⊕ 8 = 7; 5⊗ 5 = 5; 9⊗ 8 = 2
Note que os s´ımbolos ⊕ e ⊗ dependem do contexto. Se estamos em Z10, enta˜o 5 ⊕ 5 = 0, mas
em Z9, temos que 5 ⊕ 5 = 1. Note tambe´m que, se a, b ∈ Zn, os resultados das operac¸o˜es a ⊕ b e
a⊗ b sa˜o bem definidos e sa˜o elementos de Zn.
Proposic¸a˜o: (Fechamento) Sejam a, b ∈ Zn. Enta˜o a⊕ b ∈ Zn e a⊗ b ∈ Zn.
Proposic¸a˜o: Seja n inteiro com n ≥ 2.
• Para todos a, b ∈ Zn, a⊕ b = b⊕ a e a⊗ b = b⊗ a. (Comutativa)
• Para todos a, b, c ∈ Zn, a⊕ (b⊕ c) = (a⊕ b)⊕ c e a⊗ (b⊗ c) = (a⊗ b)⊗ c . (Associativa)
• Para todo a ∈ Zn, a⊕ 0 = a, a⊗ 1 = a e a⊗ 0 = 0. (Elementos de identidade)
• Para todos a, b, c ∈ Zn, a⊗ (b⊕ c) = (a⊗ b)⊕ (a⊗ c). (Distributiva)
Exemplo: Seja Z5, a = 2, b = 3 e c = 4.
• 2⊕ 3 = 0 e 3⊕ 2 = 0 e tambe´m 2⊗ 3 = 1 e 3⊗ 2 = 1
• 2 ⊕ (3 ⊕ 4) = 2 ⊕ 2 = 4 e (2 ⊕ 3) ⊕ 4 = 0 ⊕ 4 = 4 e tambe´m 2 ⊗ (3 ⊗ 4) = 2 ⊗ 2 = 4 e
(2⊗ 3)⊗ 4 = 1⊗ 4 = 4
• 2⊕ 0 = 2, 2⊗ 1 = 2 e 2⊗ 0 = 0
• 2⊗ (3⊕ 4) = 2⊗ 2 = 4 e (2⊗ 3)⊕ (2⊗ 4) = 1⊕ 3 = 4
1
Subtrac¸a˜o modular
Sejam a, b ∈ Zn. Considerando a operac¸a˜o de subtrac¸a˜o usual temos a − b = x, o que implica
em a = b+x, o que significa que a = b+x tem uma u´nica soluc¸a˜o, ou seja, existe um u´nico valor de
x ∈ Zn que satisfaz a equac¸a˜o. De modo semelhante podemos mostrar que a operac¸a˜o a = b⊕x tem
apenas um valor x ∈ Zn que e´ soluc¸a˜o da igualdade. E assim podemos definir a subtrac¸a˜o modular:
Definic¸a˜o: Seja n um inteiro positivo e sejam a, b ∈ Zn. Definimos a 	 b como o u´nico valor
x ∈ Zn de modo que a = b⊕ x.
Proposic¸a˜o: Seja n um inteiro positivo e sejam a, b ∈ Zn. Enta˜o, a	 b = (a− b) mod n
Exemplo: Seja Z9, a = 7, e b = 4.
7	 4 = x tal que 7 = 4⊕ x =⇒ x = 3
7	 4 = (7− 4) mod 9 = 3 mod 9 = 3
Divisa˜o modular
A divisa˜o modular e´ uma operac¸a˜o diferente das demais operac¸o˜es modulares, assim considere-
mos primeiramente algumas situac¸o˜es.
Exemplo: Sejam a, b ∈ Z10 com b 6= 0. Existe soluc¸a˜o para a = b⊗ x? Se existe, ela e´ u´nica?
Consideremos alguns casos:
• a = 6 e b = 2. Ha´ duas soluc¸o˜es para 6 = 2⊗ x, que sa˜o x = 3 e x = 8.
• a = 7 e b = 2. Na˜o ha´ soluc¸a˜o para 7 = 2⊗ x.
• a = 7 e b = 3. Ha´ somente uma soluc¸a˜o para 7 = 3 ⊗ x, que e´ x = 9. Neste caso, podemos
escrever 7� 3 = 9 , ou seja, x = 9 e´ o u´nico valor em Z10 que satisfaz 7 = 3⊗ x.
Definic¸a˜o: (Inverso modular) Sejam n um inteiro positivo e a ∈ Zn. O inverso de a e´ um
elemento b ∈ Zn de modo que a ⊗ b = 1. Um elemento de Zn que tenha inverso e´ chamado
invers´ıvel.
Vamos verificar os inversos em Z10 :
2
• O elemento 0 na˜o possui inverso.
• Os elementos 2, 4, 5, 6 e 8 na˜o possuem inversos.
• Os elementos 1, 3, 7 e 9 sa˜o invers´ıveis.
• Os elementos em Z10 que possuem inversos sa˜o relativamente primos (ou primos entre si) com
o 10.
• O inverso de 3 e´ 7 e o inverso de 7 e´ 3, o mesmo vale para 1 e 9.
Proposic¸a˜o: Seja n um inteiro positivo e seja a ∈ Zn. Se a tem inverso em Zn,o que denota-se
por a−1, enta˜o esse inverso e´ u´nico.
Proposic¸a˜o: Seja n um inteiro positivo e seja a ∈ Zn. Suponhamos que a seja invers´ıvel, ou
seja, existe um elemento b tal que b = a−1. Enta˜o b e´ invers´ıvel e a = b−1. Em outras palavras,
(a−1)−1 = a.
Definic¸a˜o: (Divisa˜o modular) Sejam n um nu´mero inteiro positivo e seja b um elemento in-
vers´ıvel de Zn. Seja a ∈ Zn arbitra´rio. Enta˜o, a� b se define como a⊗ b−1.
Pode-se notar enta˜o que a� b so´ esta´ definida se b e´ um elemento invers´ıvel.
Exemplo: Em Z10, calcule 2� 7.
Note que 7−1 = 3, assim 2� 7 = 2⊗ 3 = 6.
Teorema: (Elementos invers´ıveis de Zn) Seja n um inteiro positivo e seja a ∈ Zn. Enta˜o, a e´
invers´ıvel se e somente se a e n sa˜o primos entre si, ou seja, MDC(a, n) = 1.
Como calcular enta˜o os elementos invers´ıveis em Zn?
Para resolver esse problema, vamos considerar os resultados:
Teorema: Sejam α e β inteiros, na˜o simultaneamente nulos. O menor inteiro da forma αx+βy,
com x e y inteiros e´ αx+ βy = MDC(α, β.)
Exemplo: Encontrar x e y tais que 431x+ 29y = MDC(431, 29).
431 = 14× 29 + 25
29 = 1× 25 + 4
25 = 6× 4 + 1
4 = 1× 4 + 0
O MDC de 431 e 29 e´ 1, ou seja, 431 e 29 sa˜o primos entre si. Considerando as treˆs primeiras
equac¸o˜es:
25 = 431 − 14× 29 (i)
4 = 29 − 1× 25 (ii)
1 = 25 − 6× 4 (iii)
Vejamos agora:
3
1 = 25 − 6× 4 =⇒ 1 = 25 − 6×
(ii)
(29 − 1× 25)
=⇒ 1 = 25 − 6× 29 + 6× 25
=⇒ 1 = −6× 29 + 7× 25
=⇒ 1 = −6× 29 + 7
(i)
(431− 14× 29)
=⇒ 1 = −6× 29 + 7× 431− 7× 14× 29
=⇒ 1 = 7× 431− 104× 29
Temos enta˜o x = 7 e y = −104.
O inverso de a em Zn e´ um inteiro y, tal que a⊗ y = 1. Isso significa que (a · y) mod n = 1 =⇒
ay = nx+ 1 =⇒ ay + nx = 1. Vejamos alguns exemplos:
1) 7−1 em Z10:
10 = 1× 7 + 3
7 = 2× 3 + 1
3 = 1× 3 + 0
=⇒
3 = 10− 1× 7
1 = 7− 2× 3
Temos enta˜o
1 = 7− 2× 3
= 7− 2(10− 1× 7)
= 7− 2× 10 + 2× 7 =⇒ 1 = 3× 7− 2× 10
Portanto em Z10 temos 7−1 = 3.
2) 21−1 em Z100
Mas −19 /∈ Z100. Precisamos de um elemento que pertenc¸a a Z100 e que deixe o mesmo resto
que −19 mod 100 ou seja 81. Assim 21−1 = 81 em Z100.
4
Exemplo: Em Z100 calcule 30� 21.
31� 21 = 31⊗ 21−1 = 31⊗ 81 = (30 · 81)mod100 = 2511mod100 = 11
O general e o Teorema Chineˆs dos Restos1
Na antiguidade, os generais chineses costumavam contar suas tropas perdidas apo´s a guerra da
seguinte forma: ordenavam que as tropas formassem va´rias colunas com um determinado tamanho
e depois contavam quantas sobravam, e faziam isto para va´rios tamanhos diferentes.
Por exemplo, um general chineˆs possuia 1200 tropas antes da guerra. Apo´s a guerra, ele alinhou
as tropas de 5 em 5 de forma que sobraram 3 tropas. Quando alinhou de 6 em 6, tambe´m sobraram
3 tropas. Quando alinhou de 7 em 7, sobrou 1 tropa. E quando alinhou de 11 em 11, na˜o sobrou
nenhuma tropa. Quantas tropas o general tinha?
Para resolver este problema, e´ necessa´rio saber lidar com congrueˆncias. Ale´m disso, vamos utili-
zar uma poderosa arma em Teoria dos Nu´meros, chamada de Teorema Chineˆs dos Restos. De fato,
o problema apresentado acima e´ uma aplicac¸a˜o direta deste teorema.
Basta enta˜o um pequeno esforc¸o para interpretar o problema. Quando o general alinha suas
tropas, formando colunas de tamanho n, ele esta´ realizando uma divisa˜o do nu´mero de tropas por
n, e depois verificando seu resto.
Observe que, na pra´tica, contar o resto e´ muito mais fa´cil que contar o nu´mero total, ou o
quociente. Alia´s, quem conhece um pouco de Teoria dos Nu´meros, sabe que raramente estamos
interessados no quociente, o resto e´ o que importa.
Teorema Chineˆs dos restos: Sejam m1,m2, ...,mr inteiros positivos e primos entre si. O
sistema de congrueˆncias
x ≡ a1 (modm1)
x ≡ a2 (modm2)
...
x ≡ ar (modmr)
tem soluc¸a˜o u´nica x ≡ a1M1y1 + a2M2y2 + ...+ arMryr (modM), onde M = m1m2...mr,Mk = M
mk
e yk e´ tal que Mkyk ≡ 1 (modmk) (ou seja, yk e´ o inverso multiplicativo de Mk mo´dulo mk).
Soluc¸a˜o
Primeiramente, vamos organizar as informac¸o˜es do enunciado de forma matema´tica. Se x e´ o
nu´mero de tropas restantes, temos:
x ≡ 3 (mod5)
x ≡ 3 (mod6)
x ≡ 1 (mod7)
x ≡ 0 (mod11)
Como 5, 6, 7 e 11 sa˜o primos entre si, basta aplicar o Teorema Chineˆs dos Restos. Para isso,
vamos usar a fo´rmula mencionada anteriormente. Temos que:
a1 = 3, a2 = 3, a3 = 1, a4 = 01Retirado de: http://legauss.blogspot.com/2009/06/o-general-e-o-teorema-chines-dos-restos.html
5
m1 = 5, m2 = 6, m3 = 7, m4 = 11
M = 5 · 6 · 7 · 11 = 2310
M1 =
2310
5
= 462, M2 =
2310
6
= 385, M3 =
2310
7
= 330, M4 =
2310
11
= 210
Para calcular os yk e´ simples. Vou deduzir o primeiro deles, os outros irei omitir por serem
ana´logos.
y1 e´ tal que 462.y1 ≡ 1 (mod 5)
Mas 462 deixa resto 2 quando dividido por 5, isto quer dizer que 462 ≡ 2 (mod 5), substituindo
acima temos que
2y1 ≡ 1 (mod 5)
Que nu´mero multiplicamos por 2 que o resto e´ 1 quando dividido por 5?
E´ 3. Pois 3.2 = 6 ≡ 1 (mod 5) (na pior das hipo´teses, so´ ter´ıamos de testar 5-1=4 casos).
Enta˜o y1 ≡ 3 (mod 5).
Repetindo o processo, temos
y2 ≡ 1 (mod 6)
y3 ≡ 1 (mod 7)
y4 ≡ 1 (mod 11).
Pronto, agora basta jogar tudo na fo´rmula:
x ≡ 3.462.3 + 3.385.1 + 1.330.1 + 0.210.1 (mod 2310)
x ≡ 4158 + 1155 + 330 (mod 2310)
x ≡ 5643 (mod 2310)
Portanto
x ≡ 1023 (mod 2310) que e´ equivalente a x = 1023 + 2310q para todo q natural.
Mas queremos x maior que 0 e menor que 1200, o que implica que x = 1023.
Isto significa que podemos comunicar ao general que lhe sobraram 1023 tropas apo´s o combate.
6
7