Teoria dos Números

Prévia do material em texto

Teoria dos Números
• A teoria dos números é um dos ramos mais antigos da 
matemática, que se tornou central na criptografia e na 
segurança dos computadores. 
• Não chegaremos a abordar métodos para criptografia nesta • Não chegaremos a abordar métodos para criptografia nesta 
disciplina, mas veremos a aritmética modular, que é 
fundamental para esses métodos.
• Vamos começar com um teorema que estabelece o que é a 
divisão entre dois números inteiros. 
HAC ED2013 1
Teorema (Divisão)
Sejam a, b ∈ Z com b>0. Então, existem inteiros q e r tais 
que
a = qb + r e 0 ≤≤≤≤ r < b.
Além disso, existe um único par de tais inteiros (q, r) que • Além disso, existe um único par de tais inteiros (q, r) que 
satisfaz essas condições.
• O inteiro q é chamado quociente e o inteiro r é chamado 
resto.
HAC ED2013 2
Divisão...
• Podemos falar em divisão de a por b envolvendo números inteiros,
se b formaior que zero.
• A primeira parte do teorema diz que, na divisão de a por b, o inteiro
a será igual a “q vezes b” somado com um inteiro r que, obviamente,
não pode ser maior que b.não pode ser maior que b.
• A segunda parte do teorema afirma que esse par de números q e r é 
único. Existe apenas uma forma de dividir a por b (inteiros) 
resultando em apenas um quociente q e um resto r.
• Observe que tanto a quanto o quociente q podem ser inteiros 
negativos, mas b e r devem ser inteiros positivos.
HAC ED2013 3
Exemplo
Sejam a = 12 e b = 5. 
Então o quociente é q = 2 e o resto é r = 2, porque
12 = 2 * 5 + 2 e 0 ≤≤≤≤ 2 < 5
(Dividindo 12 por 5, o quociente é 2 e “sobra” 2).(Dividindo 12 por 5, o quociente é 2 e “sobra” 2).
Sejam a = 35 e b = 10. 
Então o quociente é q = 3 e o resto é r = 5, porque
35 = 3 * 10 + 5 e 0 ≤≤≤≤ 5 < 10
(Dividindo 35 por 10, o quociente é 3 e “sobra” 5).
HAC ED2013 4
Sejam a = 30 e b = 6. 
Então o quociente é q = 5 e o resto é r = 0, porque
30 = 5 * 6 + 0 e 0 ≤≤≤≤ 0 < 6
Sejam a = -37 e b = 5. (Atenção!! Divisão de um inteiro negativo)Sejam a = -37 e b = 5. (Atenção!! Divisão de um inteiro negativo)
Então o quociente é q = -8 e o resto é r = 3, porque
-37 = -8 * 5 + 3 e 0 ≤≤≤≤ 3 < 5.
Sejam a = -19 e b = 4. 
Então o quociente é q = -5 e o resto é r = 1, porque
-19 = -5 * 4 + 1 e 0 ≤≤≤≤ 1 < 4.
HAC ED2013 5
Div e Mod
As operações div e mod estão associadas ao processo de divisão. Dados 
a e b, essas operações dão o quociente e o resto no problema da 
divisão. 
Sejam a, b ∈ Z com b>0. Pelo Teorema da Divisão existe um único par 
de inteiros q e r tais que a = qb + r e 0 ≤ r < b. de inteiros q e r tais que a = qb + r e 0 ≤ r < b. 
Definimos as operações div e mod como
a div b = q e amod b = r.
Div: quociente da divisão de a por b 
Mod: resto da divisão de a por b.
HAC ED2013 6
Exemplos
12 div 5 = 2 12 mod 5 = 2
35 div 10 = 3 35 mod 10 = 5
30 div 6 = 5 30 mod 6 = 0
-37 div 5 = -8 -37 mod 5 = 3
-19 div 4 = -5 -19 mod 4 = 1
11 div 3 = 3 11 mod 3 = 2
23 div 10 = 2 23 mod 10 = 3
HAC ED2013 7
Observação:
• O resto nunca é negativo. No exemplo em que 
a =-37 e b = 5, se calculássemos a operação aritmética de divisão, o 
resultado seria:
-37/5 = -7,4. 
Mas, no contexto dos números inteiros, as operações div e mod são 
definidas de acordo com o estabelecido no teorema da divisão. Logo,
-37 div 5 = -8 e -37 mod 5 = 3 porque 
-37 = -8 * 5 + 3 e 0 ≤≤≤≤ 3 < 5.
HAC ED2013 8
Diferentes significados da palavra “mod”:
• No tópico de relações: relação de congruência modulo n, denotada por 
x ≡ y (mod n)
(x e y diferem por um múltiplo de n).
• Na teoria dos números: resto da divisão de dois inteiros.
È possível, porém estabelecer uma ligação entre esses dois significados da 
palavra mod, com o resultado mostrado na proposição a seguir:
HAC ED2013 9
Proposição
Sejam a, b, n ∈ Z com n>0. Então,
a ≡≡≡≡ b (mod n) ⇔⇔⇔⇔ amod n = bmod n.
O mod à esquerda é uma relação e o mod à direita é uma 
operação binária.
Por exemplo,
23 ≡ 11 (mod 6) e 
23 mod 6 = 5 e 11 mod 6 = 5.
HAC ED2013 10
Máximo Divisor Comum
• Sejam a, b ∈ Z. Dizemos que um inteiro d é um divisor
comum de a e b se
d|a e d|b. 
(O inteiro d é divisor comum de a e b se de divide a e d
divide b).divide b).
Exemplo: Os divisores comuns de 18 e 24 são:
-6, -3, -2, -1, 1, 2, 3 e 6.
O máximo divisor comum de dois números inteiros é o 
máximo entre todos os divisores comuns.
HAC ED2013 11
Sejam a, b ∈ Z. Dizemos que um inteiro d é o máximo divisor 
comum de a e b se 
d é um divisor comum de a e b, e
se e é um divisor comum de a e b, então e ≤ d. se e é um divisor comum de a e b, então e ≤ d. 
O máximo divisor comum de a e b é denotado por mdc(a, b).
Exemplos: mdc(18, 24) = 6, mdc(30, 20) = 10
mdc(30,24) = 6, mdc(-30, -24) = 6.
HAC ED2013 12
Cálculo do Máximo divisor comum
• Se, por exemplo, a= 24 e b =18, poderíamos, sem muita dificuldade, 
calcular um a um os divisores de cada um dos números dados e verificar 
qual é o maior deles.
• Quando desejamos encontrar o mdc de dois números grandes, porém, 
esse processo se torna inviável. esse processo se torna inviável. 
• Para simplificar esse cálculo podemos usar um procedimento chamado de 
Algoritmo de Euclides, que se baseia na proposição a seguir.
HAC ED2013 13
Proposição:
Sejam a e b inteiros positivos e c = amod b. Então, mdc (a,b) 
= mdc (b,c).
Sendo assim, para inteiros positivos a e b temos Sendo assim, para inteiros positivos a e b temos 
mdc (a, b) = mdc (b, amod b).
HAC ED2013 14
Processo para encontrar mdc de dois inteiros positivos a e b: 
-Encontrar o resto da divisão de a por b (c = a mod b). 
Encontrar o mdc de b e esse resto (mdc(b,c)). Com isso, o 
problema original ficou reduzido a um problema mais simples.
HAC ED2013 15
problema original ficou reduzido a um problema mais simples.
•Caso os números b e c ainda sejam grandes, reaplicar o 
resultado da proposição e reduzir ainda mais a grandeza dos 
números envolvidos no cálculo do mdc. 
•Esse processo pode se repetir até que o resto da divisão de a 
por b seja 0. O valor procurado é b.
Exemplo
Calcular mdc (689, 234)
689 mod 234 = 221 ⇒mdc (689, 234) = mdc (234, 221)
234 mod 221 = 13 ⇒mdc (234, 221) = mdc (221, 13)234 mod 221 = 13 ⇒mdc (234, 221) = mdc (221, 13)
221 mod 13 = 0 ⇒mdc (221, 13) = 13
HAC ED2013 16
Algoritmo de Euclides para o Máximo Divisor 
Comum
Entrada: inteiros positivos a e b.
Saída: mdc (a, b)
Seja c = amod b.Seja c = amod b.
Se c = 0 retornamos a resposta b e paramos.
Em caso contrário (c ≠ 0), calculamos mdc(b, c).
HAC ED2013 17
Exemplo
Iniciamos com a= 75 e b = 63.
Calculamos c = 75 mod 63 = 12
Como 12 ≠ 0, devemos calcular mdc(63,12)
Reiniciamos o processo com a=63 e b = 12
Calculamos c = 63 mod 12 = 3Calculamos c = 63 mod 12 = 3
Como 3 ≠ 0, devemos calcular mdc(12,3)
Reiniciamos o processo com a=12 e b = 3
Calculamos c = 12 mod 3 = 0
Como obtemos c=0, obtemos a resposta mdc(12,3) = 3 e, portanto, 
mdc(12,3) = mdc(63,12) = mdc(75,63) = 3.
HAC ED2013 18
Veja agora o que acontece quando o valor de a é menor que o valor de b. 
Suponha que queremos calcular o mdc(63,75).
Aplicando o algoritmo de Euclides, começamos com a=63 e b = 75.
Para começar, calculamos c = 63 mod 75 = 63Para começar, calculamos c = 63 mod 75 = 63
Como c não é zero, prosseguimos com a = 75 e b = 63, que é o primeiro 
passo do exemplo anterior. 
Assim, quando o valor de a é menor que o valor de b, a primeira iteração do 
algoritmo de Euclides apenas inverte a ordem dos valores.
HAC ED2013 19
Propriedade do mdc
Teorema
Sejam a e b inteiros,não simultaneamente nulos. O menor inteiro 
positivo da forma 
ax+by, ax+by, 
onde x e y são inteiros, é mdc(a, b).
Esse teorema estabelece que existem x e y inteiros tal que ax+by é o 
mdc(a,b) e, além disso, esse valor é o menor inteiro positivo dessa 
forma. 
HAC ED2013 20
Observação
Suponhamos a = 30 e b = 24. 
Já sabemos que mdc(30,24) = 6. Quais são os valores de x e y tais que 
30x+24y = 6? Temos mais de um par de valores nessas condições:
x=-3 e y=4, pois 30(-3) + 24.4 = -90+96 = 6x=-3 e y=4, pois 30(-3) + 24.4 = -90+96 = 6
x=1 e y=-1 pois 30(1) +24(-1) = 30-24 = 6
HAC ED2013 21
• A Tabela seguinte mostra os valores ax+by para os inteiros x e y
entre -4 e 4. 
• O intervalo, [-4,4], foi escolhido arbitrariamente, apenas para 
ilustrar o raciocínio apresentado, já que não podemos construir ilustrar o raciocínio apresentado, já que não podemos construir 
uma tabela que mostre o valor ax+by para todos os pares x e y. 
• O menor inteiro positivo nessa tabela é o 6. 
HAC ED2013 22
y
-4 -3 -2 -1 0 1 2 3 4
-4 -216 -192 -168 -144 -120 -96 -72 -48 -24
-3 -186 -162 -138 -144 -90 -66 -42 -18 6
-2 -156 -132 -108 -84 -60 -36 -12 12 36
HAC ED2013 23
x
-2 -156 -132 -108 -84 -60 -36 -12 12 36
-1 -126 -102 -78 -54 -30 -6 18 42 66
0 -96 -72 -48 -24 0 24 48 72 96
1 -66 -42 -18 6 30 54 78 102 126
2 -36 -12 12 36 60 84 108 132 156
3 -6 18 42 66 90 114 138 162 186
4 24 48 72 96 120 144 168 192 216
O teorema afirma que não conseguimos encontrar valores de x e y não 
simultaneamente nulos tal que ax+by seja positivo e menor que 6.
Em decorrência, temos:
Sejam a e b inteiros arbitrários (não simultaneamente nulos). É impossível 
acharmos inteiros x e y com
0 < ax + by < mdc(a, b)
porque ax + by é divisível por mdc (a,b).
HAC ED2013 24
Processo para encontrar x e y
• Para encontrar os valores x e y, dados a e b, tais que ax + 
by = mdc(a, b), estendemos o algoritmo de Euclides, 
mantendo os quocientes e os restos durante o processo.
• Essa extensão ao algoritmo de Euclides será explicada por • Essa extensão ao algoritmo de Euclides será explicada por 
meio de um exemplo:
• Encontrar x e y tais que
431x+29y = mdc(431,29) = 1
HAC ED2013 25
Exemplo
• O primeiro passo é calcular o mdc(431, 29) pelo algoritmo 
de Euclides, registrando o valor de a div b. 
• a=431, b=29
c= 431 mod 29 = 25 (431 div 29 = 14)c= 431 mod 29 = 25 (431 div 29 = 14)
Assim, mdc(431,29) = mdc(29,25)
• a=29, b=25
c = 29 mod 25 = 4 (29 div 25 = 1)
Assim, mdc (431,29) = mdc(29,25) = mdc (25,4)
HAC ED2013 26
• a=25, b=4
c= 25 mod 4 = 1 (25 div 4 = 6)
Assim, mdc (431,29) = mdc(29,25) = mdc (25,4)= mdc(4,1)
a=4, b=1• a=4, b=1
c= 4 mod 1 = 0 (4 div 1 = 4)
Assim, mdc (431,29) = mdc(29,25) = mdc (25,4)= mdc(4,1) = 1
HAC ED2013 27
• Reescrever as igualdades encontradas durante a aplicação 
do algoritmo seguindo a expressão usada no teorema 
sobre a divisão: Se b é divisor de a, então existem q e r 
(maior ou igual a zero) tal que a = qb + r.
• Assim, temos:
431 = 14 * 29 + 25 (14 é o quociente da divisão e 25 é o resto)
29 = 1 * 25 + 4 (1 é o quociente da divisão e 4 é o resto)
25 = 6 * 4 + 1 (6 é o quociente da divisão e 1 é o resto)
4 = 4 * 1 + 0. (4 é o quociente da divisão e 0 é o resto) 
HAC ED2013 28
Em todas essas equações, exceto a última, resolver em 
relação ao resto (reescrever isolando o resto do lado 
esquerdo da igualdade):
431 = 14 * 29 + 25 se transforma em 25 = 431 - 14 * 29 431 = 14 * 29 + 25 se transforma em 25 = 431 - 14 * 29 
29 = 1 * 25 + 4 se transforma em 4 = 29 - 1 * 25
25 = 6 * 4 + 1 se transforma em 1 = 25 - 6 * 4
HAC ED2013 29
• Fazer substituições, a partir da penúltima equação:
A última equação tem 1 na forma 25x + 4y.
Substituímos o 4 usando a equação anterior:
1 = 25 - 6 * 4
= 25 – 6 * (29 - 1 * 25)
= -6 * 29 + 7 * 25.
HAC ED2013 30
25 = 431 - 14 * 29
4 = 29 - 1 * 25
1 = 25 - 6 * 4
Agora substituímos o 25 usando a primeira equação:
1 = -6 * 29 + 7 * 25
= -6 * 29 + 7 * (431 - 14 * 29)
= 7 * 431 + (-6 + 7 * -14) * 29
25 = 431 - 14 * 29
= 7 * 431 + (-6 + 7 * -14) * 29
= 7 * 431 + -104 * 29
Assim achamos x = 7 e y = -104 para obter
431x + 29y = mdc(431,19) = 1.
HAC ED2013 31
25 = 431 - 14 * 29
4 = 29 - 1 * 25
1 = 25 - 6 * 4
Alguns conceitos
• Um inteiro positivo p > 1 é dito um número primo ou um primo se 
seus únicos divisores são ±1 e ±p, ou seja se p tem apenas os 
divisores triviais. 
• Se n > 1 não é primo, então n é dito composto.
• Se n > 1 não é primo, então n = ab, onde 1 < a, b < n.
• Sejam a e b inteiros. Dizemos que a e b são relativamente primos
(ou primos entre si) se e somente se mdc(a, b) = 1.
• Dois inteiros são relativamente primos se os únicos divisores que 
eles têm em comum são 1 e -1.
HAC ED2013 32
Corolário
Sejam a e b inteiros. Existem inteiros x e y tais que 
ax + by = 1 se e somente se 
a e b são relativamente primos.
HAC ED2013 33
Aritmética Modular
• A aritmética é o estudo das operações básicas: adição, subtração, 
multiplicação e divisão sobre os domínios dos números inteiros Z ou 
dos números racionais.
• A a aritmética modular é o estudo das operações básicas sobre um 
contexto diferente, que é o sistema dos números inteiros módulo n. contexto diferente, que é o sistema dos números inteiros módulo n. 
• O conjunto Zn, onde n é um inteiro positivo, é o conjunto de todos os 
números naturais de 0 a n-1, inclusive:
Zn = {0, 1, 2, ..., n – 1}
HAC ED2013 34
Assim, por exemplo:
Z1 = {0}
Z2 = {0, 1}
Z = {0, 1, 2}Z3 = {0, 1, 2}
Z4 = {0, 1, 2, 3}
.....
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
.....
HAC ED2013 35
Operações
• Na aritmética modular, as operações básicas são:
• adição mod n
• subtração mod n 
• multiplicação mod n • multiplicação mod n 
• divisão mod n
HAC ED2013 36
Adição e Multiplicação Modulares
• A operação de adição modular é denotada pelo símbolo ⊕ e a
multiplicação modular é denotada pelo símbolo ⊗.
• Para trabalhar com operações modulares, é necessário definir
previamente qual o contexto em que as operações serão realizadas,
ou seja o conjunto Z .ou seja o conjunto Zn.
• Sejam n um inteiro positivo e a, b ∈ Zn. Definimos
a⊕⊕⊕⊕ b = (a + b) mod n e (adição modular)
a⊗⊗⊗⊗ b = (a * b) mod n (multiplicação modular)
HAC ED2013 37
• As operações do lado esquerdo das igualdades são operações 
modulares. As operações do lado direito das igualdades são 
operações regulares envolvendo inteiros. 
• O operador mod representa a operação relacionada à divisão, ou 
seja, o resto da divisão inteira.seja, o resto da divisão inteira.
• Esta definição diz é que:
• “a soma modular de a e b no contexto Zn é igual ao resto da divisão 
inteira da soma de a e b por n” e
• “o produto modular de a e b no contexto Zn é igual ao resto da 
divisão inteira do produto de a e b por n”.
HAC ED2013 38
Exemplos
• Se n = 10, Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
5 ⊕ 5 = (5 + 5) mod 10 = 10 mod 10 = 0
9 ⊕ 8 = (9 + 8) mod 10 = 17 mod 10 = 7
5 ⊗ 5 = (5 * 5) mod 10 = 25 mod 10 = 5
9 ⊗ 8 = (9 * 8) mod 10 = 72 mod 10 = 29 ⊗ 8 = (9 * 8) mod 10 = 72 mod 10 = 2
• Se n = 7, Z7 = {0, 1, 2, 3, 4, 5, 6}
5 ⊕ 5 = (5 + 5) mod 7 = 10 mod 7 = 3
3 ⊕ 6 = (3 + 6) mod 7 = 9 mod 7 = 2
5 ⊗ 5 = (5 * 5) mod 7 = 25 mod 7 = 4
3 ⊗ 6 = (3 * 6) mod 7 = 18 mod 7 = 4
HAC ED2013 39
Observações
• As operações ⊕ e ⊗ dependem de contexto.Se n=10, 5 ⊕ 5 = 0, mas se n=9, 5 ⊕ 5 = 1.
• Os valores envolvidos nas operações também dependem do 
contexto. contexto. 
Se n = 10, podemos calcular operações modulares entre os valores que 
estão no conjunto 
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
HAC ED2013 40
Propriedades das operações ⊕ e ⊗:
• Fechamento:
Sejam a, b ∈ Zn. Então a⊕ b e a⊗ b ∈ Zn. 
Essa propriedade diz que o resultado da soma ou da multiplicação 
modular entre elementos de um dado contexto também está no modular entre elementos de um dado contexto também está no 
mesmo contexto.
• Exemplo:
Se n = 10, 9 ⊕ 8 = (9 + 8) mod 10 = 17 mod 10 = 7
E 7∈ Z10.
HAC ED2013 41
• Comutativa:
Seja n inteiro com n ≥ 2. 
Para todos os valores a, b ∈ Zn, temos que 
a⊕⊕⊕⊕ b = b ⊕⊕⊕⊕ a e a ⊗⊗⊗⊗ b= b ⊗⊗⊗⊗ a
• Associativa:
Para todos os valores a, b ∈ Zn, temos que 
a⊕⊕⊕⊕(b⊕⊕⊕⊕c) =(a⊕⊕⊕⊕b)⊕⊕⊕⊕c e a⊗⊗⊗⊗(b⊗⊗⊗⊗c) =(a⊗⊗⊗⊗b)⊗⊗⊗⊗c.
HAC ED2013 42
• Elementos identidade:
Para todo a ∈ Zn, temos que 
a⊕⊕⊕⊕0 = a, a⊗⊗⊗⊗1 = a e a⊗⊗⊗⊗0 = 0. a⊕⊕⊕⊕0 = a, a⊗⊗⊗⊗1 = a e a⊗⊗⊗⊗0 = 0. 
• Distributiva:
Para todos os valores a, b, c ∈ Zn, temos que 
a⊗⊗⊗⊗ (b⊕⊕⊕⊕c) =(a⊗⊗⊗⊗b)⊕⊕⊕⊕( a⊗⊗⊗⊗c)
HAC ED2013 43
Outras características
• Podemos apresentar outras características importantes das 
operações de soma e multiplicação modular.
• Sobre a soma, podemos provar que, dado um contexto, uma 
equação da forma a = b ⊕ x tem apenas uma solução, isto é, tem 
apenas um elemento do contexto dado que, somado a b, resulta a. apenas um elemento do contexto dado que, somado a b, resulta a. 
• Proposição:
Seja n um inteiro positivo e sejam a, b ∈ Zn. Então, existe um e um 
só x ∈ Zn tal que a = b ⊕ x.
HAC ED2013 44
Outras características...
Omesmo não pode ser afirmado sobre a multiplicação modular.
Considere o contexto Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Qual é o valor de x que satisfaz a equação 2⊗x = 6?• Qual é o valor de x que satisfaz a equação 2⊗x = 6?
2⊗3 = 6 e que 2⊗8 = 6. Assim, x pode ser 3 ou 8.
• Qual é o valor de x que satisfaz a equação 2⊗x = 7?
não há valores para x que resolvam essa equação.
• Qual é o valor de x que satisfaz a equação 3⊗x = 7?
existe apenas um valor x = 9 que é solução para 3⊗x = 7.
HAC ED2013 45
Subtração Modular
• Na aritmética tradicional, podemos definir:
Sejam a, b∈Z. Definimos a-b como a solução da equação a =b+x.
• Utilizamos a mesma abordagem para definir a subtração modular. 
Já sabemos que a equação a = b ⊕ x tem apenas uma solução.
Subtração Modular:
Seja n um número positivo e sejam a, b∈∈∈∈ZZZZn. Definimos a Ө b como o 
único valor x ∈∈∈∈ZZZZn tal que a = b ⊕⊕⊕⊕ x.
HAC ED2013 46
Exemplos
• Se n = 10, Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Qual o valor de 3 Ө 2 = ? É a solução para 3 = 2 ⊕ x
2⊕ 1 = (2 + 1) mod 10 = 3 mod 10 = 3
Logo, x = 1 e 3 Ө 2 = 1
Qual o valor de 9 Ө 8 = ? É a solução para 9 = 8 ⊕ x
8 ⊕ 1 = (8 + 1) mod 10 = 9 mod 10 = 9
Logo, x = 1 e 9 Ө 8 = 1
Qual o valor de 4 Ө 9 = ? É a solução para 4 = 9 ⊕ x
9 ⊕ 5 = (9 + 5) mod 10 = 14 mod 10 = 4
Logo, x = 5 e 4 Ө 9 = 5
HAC ED2013 47
Exemplos
• Se n = 9, Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}
Qual o valor de 3 Ө 2 = ? É a solução para 3 = 2 ⊕ x
2⊕ 1 = (2 + 1) mod 9 = 3 mod 9 = 3
Logo, x = 1 e 3 Ө 2 = 1
Qual o valor de 5 Ө 8 = ? É a solução para 5 = 8 ⊕ x
8 ⊕ 6 = (8 + 6) mod 9 = 14 mod 9 = 5
Logo, x = 6 e 5 Ө 8 = 6
Qual o valor de 3 Ө 7 = ? É a solução para 3 = 7 ⊕ x
7 ⊕ 5 = (7 + 5) mod 9 = 12 mod 9 = 3
Logo, x = 5 e 3 Ө 7 = 5
HAC ED2013 48
Subtração Modular 
Alternativamente, podemos definir:
Seja n um inteiro positivo e sejam a, b∈Zn. 
Então, 
a Ө b = (a-b) mod n.a Ө b = (a-b) mod n.
Prova:
Para mostrar que a Ө b = (a-b) mod n, Devemos mostrar que:
1) [(a-b) mod n] ∈Zn e,
2) Se x = (a-b) mod n, então a = b ⊕ x.
HAC ED2013 49
Provar 1): 
é óbvio, porque (a-b)mod n é um inteiro em Zn.
Provar 2): 
note que se x = (a-b) mod n, note que se x = (a-b) mod n, 
então x = a-b+kn para algum inteiro k. 
Então
b ⊕⊕⊕⊕ x = [b+(a-b+kn)] mod n = (a+kn) mod n = a.
HAC ED2013 50
Exemplos
• Se n = 10, Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
3 Ө 2 = (3-2) mod 10 = 1 mod 10 = 1
9 Ө 8 = (9-8) mod 10 = 1 mod 10 = 1
4 Ө 9 = (4-9) mod 10 = -5 mod 10 = 5
• Se n = 9, Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}
3 Ө 2 = (3-2) mod 9 = 1 mod 9 = 1
5 Ө 8 = (5-8) mod 9 = -3 mod 9 = 6
3 Ө 7 = (3-7) mod 9 = -4 mod 9 = 5
HAC ED2013 51
Divisão modular
• Na aritmética comum temos a lei do cancelamento:
ab = ac => b=c.
• Mas em Z10, 
5⊗2 = 5⊗4 mas 2 ≠4.
A divisão modular de a por b (a∅∅∅∅b) não pode ser definida como o 
único x∈Zn tal que a = b ⊗ x, pois x não é único.
Considere 6∅∅∅∅2 em Z10. Como calcular?
Qual a solução para 2 ⊗ x = 6? 
2 ⊗ 3 = 6, logo x = 3
2 ⊗ 8 = 6, logo x = 8
HAC ED2013 52
Outros exemplos
• Dados a, b ∈ Z10 (com b ≠0) qual a solução para a = b ⊗ x?
• Se a=6 e b=2, há duas soluções para 6 = 2 ⊗ x:
x=3 e x=8
• Se a=7 e b=2, não há solução para 7 = 2 ⊗ x.• Se a=7 e b=2, não há solução para 7 = 2 ⊗ x.
• Se a=7 e b=3, há uma solução para 7 = 3 ⊗ x:
x=9
• Apenas nesse último caso faz sentido escrever
7∅∅∅∅3=9
HAC ED2013 53
Divisão modular
Usamos o fato
a÷b = a.b-1 (b-1 é o inverso de b)
Para definir a divisão modular. Para definir a divisão modular. 
(A divisão modular de a por b está definida apenas quando b 
possui inverso no contexto)
HAC ED2013 54
Inverso Modular
Sejam n um inteiro positivo e a ∈ Zn. O inverso de a é um elemento b ∈ Zn tal
que
a⊗⊗⊗⊗b = 1. 
Um elemento de Zn que tenha inverso é chamado inversível.
Nem todos os elementos de Zn têm inverso. Porém, se ele tiver inverso, esse 
inverso é único. O inverso de um elemento a é denotado por a-1. 
HAC ED2013 55
Proposição:
• Seja n um inteiro positivo e seja a ∈ Zn. Se a tem um inverso 
em Zn, então tem apenas um inverso.
• Prova:
Suponhamos que a tenha dois inversos, b e c ∈ Zn com b≠c. 
Considere b ⊗ a ⊗ c . 
Pela propriedade associativa para ⊗, 
b = b ⊗ 1 = b ⊗ (a ⊗ c) = (b ⊗ a) ⊗ c = 1 ⊗ c = c
o que contradiz b≠c. ⇒⇐.
HAC ED2013 56
Proposição:
Seja n um inteiro positivo e seja a ∈ Zn, a invertível. 
Se b = a-1, então b é invertível e a = b-1. Em outras palavras, 
(a-1)-1 = a.
• Prova:
(exercício)
HAC ED2013 57
• Para calcular a divisão modular precisamos 
saber:
– Que elementos são invertíveis em um contexto– Que elementos são invertíveis em um contexto
– Como calcular o inverso de um número
HAC ED2013 58
Quais elementos tem inverso?
• Considere como exemplo o conjunto Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. 
O inverso de 2 é o elemento x ∈ Z10 tal que 2 ⊗ x = 1.
• Como já sabemos calcular a multiplicação modular, podemos fazer 
alguns cálculos com elementos de Z10 e descobrir que
2 não tem inverso.2 não tem inverso.
• O inverso do elemento 3 é o elemento x ∈ Z10 tal que 
3 ⊗ x = 1. 
• Podemos verificar que:
3 ⊗ 7 = (3*7) mod 10 = 21 mod 10 = 1. 
Logo, x = 7 é o inverso de 3 em Z10. Escrevemos 3
-1= 7.
HAC ED2013 59
Se calcularmos o inverso de todos os elementos de Z10, vamos verificar 
que:
• 0 não tem inverso
• Os elementos 2, 4, 5, 6 e 8 não têm inversos• Os elementos 2, 4, 5, 6 e 8 não têm inversos
• Os elementos 1, 3, 7 e 9 têm inversos, e esse inverso é único.
Das afirmações colocadas, concluímos que os elementos de Z10 que têm 
inverso são exatamente aqueles que são relativamente primos com 
10. 
HAC ED2013 60
• Teorema:
Seja n um inteiro positivo e seja a ∈ Zn. Então, a é invertível se e 
somente se a e n são relativamente primos.
• Dois números inteiros são relativamente primos se o máximo divisor 
comum deles é um, ou seja, mdc(a,b) = 1.
• De fato, os elementos de Z10 quesão relativamente primos com 10 
são exatamente aqueles que têm inverso em Z10:
mdc( 1,10) = 1, mdc( 3,10) = 1, mdc( 7,10) = 1, mdc( 9,10) = 1
HAC ED2013 61
Exercício
Podemos analisar o que acontece com o contexto 
Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}. 
Os elementos invertíveis em Z9 são 1, 2, 4, 5, 7 e 8, todos relativamente 
primos com 9.
Os elementos não invertíveis em Z9 são 0, 3 e 6. 
HAC ED2013 62
Divisão modular
• Seja n um inteiro positivo e seja b um elemento invertível de Zn. Seja 
a ∈ Zn arbitrário. Então definimos a divisão modular como
a∅b = a⊗ b-1. 
• Exemplo:
Em ∈ Z10 calcule 2∅7.
Como 7-1 = 3, 2∅7 = 2⊗ 3 = 6.
HAC ED2013 63
Exemplos
Calcular 8 ∅ 7 em Z10
8 ∅ 7 = 8⊗ 7-1 = 8⊗ 3 = (8.3) mod 10 = 24 mod 10 = 4.
Calcular 8 ∅ 7 em Z9
8 ∅ 7 = 8⊗ 7-18 ∅ 7 = 8⊗ 7-1
Encontrar inverso de 7 em Z9, ou seja, b tal que 7⊗b = 1.
7⊗b = 1 => (7.b) mod 9 = 1 => (7.4) mod 9 = 1
8 ∅ 7 = 8⊗ 7-1 = 8⊗ 4 = (8.4) mod 10 = 32 mod 10 = 2.
HAC ED2013 64
Método para calcular inverso
Seja n um inteiro positivo e seja a ∈ Zn. 
Suponha que a é relativamente primo a n, ou seja, mdc(a,n) 
= 1.
Como calcular a-1?
– Queremos encontrar b tal que (a*b) + kn = 1– Queremos encontrar b tal que 
– a ⊗ b = 1 
– (a*b) mod n = 1
– (a*b) + kn = 1
• Processo para encontrar b:
– Encontrar os inteiros x e y tal que ax + ny = 1
(x é um candidato a b mas pode não estar em Zn)
– Definir b = x mod n
HAC ED2013 65
(a*b) + kn = 1
ax + ny = 1
Método para calcular inverso
• O processo para calcular inversos utiliza o seguinte resultado:
• Proposição:
Sejam a e b inteiros. Existem inteiros x e y tais que ax+by = 1 se e somente 
se a e b são relativamente primos
Lembretes:
• Podemos encontrar x e y usando retro-substituição no Algoritmo de 
Euclides
• Queremos encontrar b tal que a ⊗ b = 1, ou seja, 
(a.b) mod n = 1 com b em Zn
HAC ED2013 66
Exemplo
Calcular 29-1 em Z431
• Encontramos x e y tais que 431x + 29y = 1
x = 7 e y = -104, logo (-104 . 29) mod 431 = 1
• Entretanto, -104 ∉ Z431 
• Assim, fazemos b = -104 mod 431 = 327
• Calcular 131 ∅ 29 em Z431
131 ∅ 29 = 131 ⊗ 29-1= 131 ⊗ 327 = (131 . 327) mod 431 =
42847 mod 431 = 178
HAC ED2013 67
Cálculo de equações
9 ⊗⊗⊗⊗ x = 4 em ZZZZ12
Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
9 ⊗ x = (9 * x) mod 12 = 4
Método 1: Testar os elementos de Z12 um a um:
Será x = 0? (0*9) mod 12 = 0 mod 12 = 0 Não!
Será x = 1? (1*9) mod 12 = 9 mod 12 = 9
Será x = 2? (2*9) mod 12 = 18 mod 12 = 6
Será x = 3? (3*9) mod 12 = 27 mod 12 = 3
Será x = 4? (4*9) mod 12 = 36 mod 12 = 0 
HAC ED2013 68
Cálculo de equações
Será x = 5? (5*9) mod 12 = 45 mod 12 = 9 
Será x = 6? (6*9) mod 12 = 54 mod 12 = 6
Será x = 7? (7*9) mod 12 = 63 mod 12 = 3
Será x = 8? (8*9) mod 12 = 72 mod 12 = 0
Será x = 9? (9*9) mod 12 = 81 mod 12 = 
...... ...... 
HAC ED2013 69
Cálculo de equações
7 ⊗⊗⊗⊗ x = 4 em ZZZZ12
Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
7-1 = 7
7 ⊗ x = (7 * x) mod 12 = 4
Método 2: Multiplicar os dois lados da equação pelo inverso do coeficiente 
de x:
7 ⊗ x = 4 => 7-1⊗ 7 ⊗ x = 4 ⊗ 7-1 => x = 4 ⊗ 7 = 28 mod 12 = 4
Solução: x = 7
HAC ED2013 70
4 ⊗⊗⊗⊗ x Ө 8 = 9 em Z11
• A ordem de prioridade dos operadores é a mesma da aritmética comum:
4 ⊗ x Ө 8 = 9 em Z11 equivale a (4 ⊗ x) Ө 8 = 9 em Z11
Fazendo (4 ⊗ x) = y, temos:Fazendo (4 ⊗ x) = y, temos:
y Ө 8 = 9, logo, y = 6
Agora vamos resolver 4 ⊗ x = 6.
Como 4 tem inverso em Z11 e 4
-1 = 3, 
4 ⊗ x = 6 => 3 ⊗ 4 ⊗ x = 6 ⊗ 3 => x = 6 ⊗ 3 => x = 7
Solução: x = 7.
HAC ED2013 71