Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 1
Disciplina: ÁLGEBRA APLICADA À COMPUTAÇÃO
Código: CCMP0001
Carga Horária Semestral: 60h
Professor: Carlos Alexandre Barros de Mello
Obrigatória:
x
Eletiva :
Número de Créditos: TEÓRICOS: 04; PRÁTICOS: 0; TOTAL: 04
Pré-Requisito: Linguagem de Programação Imperativa e Lógica
Co-Requisito: Período Indicado: 3º
EMENTA
Conjuntos. Relações. Funções. Restrição. Fecho. Indução. Recursão. Sistemas
algébricos. Reticulados. Monóides. Grupos. Anéis. Álgebras booleanas.
BIBLIOGRAFIA
ROSS, Kenneth, WRIGHT, Charles. DISCRETE MATHEMATICS, New Jersey,
Ed. Prentice-Hall, 2002.
BURTON, David M. ELEMENTARY NUMBER THEORY, New York, Ed.
McGraw-Hill , 2001.
CALENDÁRIO DE PROVAS
1oEE
2oEE
2a Chamada
Final
01/04
25/05
01/06
03/06
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 2
PARTE I. Teoria dos Conjuntos
A teoria dos conjuntos é a base da matemática. Assim, os conceitos de
“conjuntos” e “associação” são tidos como termos básicos não-definidos e o
resto da matemática é definido nesses termos.
Um conjunto é uma coleção de objetos. A definição do conjunto não deve ser
ambígua de modo que se possa decidir se um objeto pertence ou não ao
conjunto.
Um objeto a que pertence a um conjunto S é chamado membro de S ou
elemento de S. Se a é um objeto, A é um conjunto e a é membro de A, dizemos
que a ∈ A ou a ∉ A, se a não é membro de A.
É possível descrever um conjunto de diversas maneiras. Uma delas é listando
seus elementos (forma extencionista):
ù = {0, 1, 2, 3, 4, ...} = Conjunto dos Números Naturais
P = {1, 2, 3, 4, ...} = Conjunto dos Positivos = ù*
Z = {.., -3, -2, -1, 0, 1, 2, 3, ...} = Conjunto dos Inteiros
Q = Conjunto dos Racionais = Números da forma m/n
ú = Reais = Todos os números racionais ou não
÷ = Complexos
Podemos ver como esses Universos se relacionam entre si na Figura 1.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 3
Fig. 1. Relação entre os Universos.
Outra forma de apresentar os conjuntos é através de regras de formação:
{x : x ∈ ú ∧ 1 ≤ x < 3}
(representa todos os reais maiores ou iguais a 1 e
menores que 3)
Uma terceira forma é através de intervalos.
O mesmo exemplo anterior poderia ser escrito como:
{x : x ∈ ú ∧ x ∈ [1, 3) }
Assim, podemos ter:
[a, b] = {x : x ∈ ú ∧ x ∈ a ≤ x ≤ b}
[a, b) = {x : x ∈ ú ∧ x ∈ a ≤ x < b}
(a, b] = {x : x ∈ ú ∧ x ∈ a < x ≤ b}
(a, b) = {x : x ∈ ú ∧ x ∈ a < x < b}
Pode haver mais de uma forma de descrever um mesmo conjunto.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 4
Sejam dois conjuntos S e T, dizemos que T é um subconjunto de S, se todo
elemento de T pertence a S: T ⊂ S. Se T está contido e é igual a S, dizemos: T
⊆ S.
Assim, T = S, sse, T ⊂ S ∧ S ⊂ T.
Podemos escrever que T ⊂ S, indicando que T está contido em S, mas T é
diferente de S. Se T ⊂ S, dizemos que T é um subconjunto próprio de S.
Teorema 1.1: Transitividade da Contingência
Suponha que A, B e C são conjuntos quaisquer. Se A ⊆ B e B ⊆ C, então A ⊆ C.
Prova:
Suponha que A ⊆ B e B ⊆ C. Seja a um elemento qualquer pertencente a A.
Assim, a ∈ A. X ⊆ Y implica que todo elemento de X também é elemento de Y.
Assim, como A ⊆ B, então a ∈ B, para todo a pertencente a A. Da mesma forma,
como B ⊆ C, todo elemento de B pertence a C. Como a pertence a B, a também
pertence a C.
Considere agora os seguintes conjuntos:
{n ∈ ù: 2 < n < 3}
{x ∈ ú: x2 < 0}
{r ∈ Q: r2 = 2}
{ x ∈ ú: x2 + 1 = 0}
Esses conjuntos têm em comum o fato de não possuírem elementos. O conjunto
sem elementos é chamado de Conjunto Vazio, representado por ∅ ou { }.
Cuidado! {∅} é um conjunto com um elemento (o vazio).
Se A é um conjunto, {A} é outro conjunto com um membro apenas não
importando quantos elementos existam em A. Assim, {∅} não é o conjunto
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 5
vazio. É um conjunto com um elemento mesmo que o vazio não contenha
elementos. Temos que ∅ ∈ {∅}, ∅ ⊂ {∅}, mas ∅ ∉ ∅.
O conjunto de todos os subconjuntos de um conjunto S é chamado de Conjunto
das Partes de S (Power Set) e será representado por P(S). Obviamente,
ieS
fazem parte de P(S):
a) P(∅) = {∅}
b) Se S = {a}, então P(S) = {∅, {a}}
c) Se S = {a, b}, então P(S) = {∅, {a}, {b}, {a, b}}
d) Seja S um conjunto finito com n elementos, n ≥ 0, então P(S) tem 2n
elementos.
f) Se S é infinito, P(S) é infinito também.
1.1 Operações entre Conjuntos
União: A ∪ B = {x: x ∈ A ∨ x ∈ B}
Interseção: A ∩ B = {x: x ∈ A ∧ x ∈ B}
Dois conjuntos são ditos disjuntos se A ∩ B =∅
Complemento Relativo: A – B = {x: x ∈ A ∧ x ∉ B}
Diferença Simétrica: A ⊕ B = {x: x ∈ A ∨ x ∈ B, mas não ambos}
A ⊕ B = (A ∪ B) – (A ∩ B) = (A – B) ∪ (B – A)
Às vezes, é conveniente ilustrar relações através de diagramas de Venn1. Os
diagramas de Venn são largamente utilizados nos estudos da teoria dos
conjuntos. Eles utilizam figuras geométricas para representar as estruturas da
teoria dos conjuntos. A figura abaixo apresenta a representação de algumas
relações através dos diagramas.
1
John Venn, Matemático inglês (1834-1923)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
A∪B
A∩B
A–B
Página 6
A⊕B
U = Conjunto Universo
U – A = Complemento Absoluto ou complemento de A = Ac
No estudo da álgebra de conjuntos, podemos fazer uma relação fácil com
elementos da lógica como os conectivos. Por analogia temos:
Conectivo Lógico
Operação sobre Conjuntos
Negação
Complemento
Disjunção
União
Conjunção
Interseção
1.2 Leis da Álgebra de Conjuntos
1. Leis Comutativas
a) A ∪ B = B ∪ A
b) A ∩ B = B ∩ A
2. Leis Associativas
a) (A ∪ B) ∪ C = A ∪ (B ∪ C)
b) (A ∩ B) ∩ C = A ∩ (B ∩ C)
3. Leis Distributivas
a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 7
4. Leis Idempotentes
a) A ∪ A = A
b) A ∩ A = A
5. Identidade
a) A ∪ i = A
b) A ∪ U = U
c) A ∩ i = i
d) A ∩ U = A
6. Complemento Duplo: (Ac)c = A
7.a) A ∪ Ac = U
b) A ∩ Ac = i
8.a) Uc = i
b) ic= U
9. Leis de deMorgan
a) (A ∪ B) c = A c ∩ B c
b) (A ∩ B) c = A c ∪ B c
10. Associatividade da Diferença Simétrica
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
Prova da Lei de deMorgan a:
a) (A ∪ B) c = A c ∩ B c
Vamos tentar mostrar que (A ∪ B) c ⊆ A c ∩ B c e A c ∩ B c ⊆ (A ∪ B) c
I) Seja x ∈ (A ∪ B) c ⇒ x ∉ (A ∪ B), logo x ∉ A e x ∉ B. Assim, x ∈ Ac e x ∈ Bc
Como x pertence a ambos, x também deve pertencer à interseção. Assim:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 8
x ∈ (Ac ∩ Bc)
⇒ (A ∪ B) c ⊆ A c ∩ B c
Por outro lado:
II) Seja x ∈ Ac ∩ Bc ⇒ x ∈ Ac e x ∈ Bc. Assim, x ∉ A e x ∉ B. Logo, x ∉ (A ∪ B).
Isso implica que x ∈ (A ∪ B)c.
⇒ A c ∩ B c ⊆ (A ∪ B) c
I e II só são possíveis se (A ∪ B) c = A c ∩ B c. Logo, está provado. A Lei b tem
prova similar.
1.3 Pares Ordenados
Sejam S e T dois conjuntos e s∈S e t∈T. Podemos formar o par ordenado <s, t>
≠ <t, s>. Onde <s1, t1> = <s2, t2>, sse s1 = s2 e t1 = t2. O conjunto de todos os
pares ordenados <s, t> é chamado produto cartesiano de S e T e é escrito SxT:
Se S = T, podemos escrever SxS = S2.
Exemplos: Se S = {1, 2, 3} e T={a, b}
SxT = {<1, a>, <1, b>, <2, a>, <2, b>, <3, a>, <3, b>}
SxS = S2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}
As seguintes propriedades regem o produto cartesiano:
1) Não-Comutatividade: Sejam A e B dois conjuntos. Então AxB é, em geral,
diferente de BxA.
2) Não-Associatividade: Sejam A, B e C três conjuntos. Então (AxB)xC é, em
geral, diferente de Ax(BxC).
Observações:
a) A x ∅ = ∅
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 9
b) ∅ x A = ∅
c) ∅2 = ∅
O produto cartesiano se distribui sobre a união e a interseção:
a) Distributividade do produto cartesiano sobre a união:
Ax(BUC) = (AxB)U(AxC)
b) Distributividade do produto cartesiano sobre a interseção:
Ax(B∩C) = (AxB)∩(AxC)
O produto cartesiano é uma operação reversível. Ou seja, dado o conjunto de
pares gerados pelo produto de AxB, é possível retornar ao conjunto A e ao
conjunto B que gerou esses pares. Para tanto, os primeiros operandos dos
pares fazem parte do conjunto A e os segundos operandos fazem parte de B.
Exemplo: Se o resultado do produto cartesiano de dois conjuntos A e B foi:
{<a, a>, <a, b>, <b, a>, <b, b>}
então:
A = {a, b} e B = {a, b}.
A reversibilidade só não é possível quando o produto envolver o conjunto vazio.
Como visto nas observações acima, o produto cartesiano de qualquer conjunto
com o conjunto vazio retorna o próprio vazio não sendo possível, assim,
identificar o conjunto que gerou o resultado.
1.4 Paradoxo de Russell
Por definição, um conjunto é uma coleção de zero ou mais elementos distintos
os quais não possuem qualquer ordem associada.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 10
Se considerarmos que um conjunto pode possuir conjuntos como elementos,
surge a questão:
Um conjunto pode ser elemento de si mesmo?
Para resolvermos esse problema, temos que entender a noção de conjunto
ordinário. Considere a seguinte definição por compreensão:
S = {A | A é um conjunto ordinário}
Ou seja, o conjunto de todos os conjuntos que não são elementos de si
mesmos.
Essa definição, no entanto, retrata uma contradição, um paradoxo2, denominado
de Paradoxo de Russell.
Teorema 1.2: Paradoxo de Russell
A seguinte definição não é um conjunto:
S = {A | A é um conjunto ordinário}
Prova:
Vamos fazer uma prova por absurdo. Ou seja, partimos da negação das
hipóteses e tentamos chegar a um resultado absurdo.
Assim, vamos considerar que S é um conjunto.
Como S é um conjunto de conjuntos, podemos verificar se S é um elemento de
si mesmo. Vamos supor os dois casos:
1) S ∈ S: Temos então
Se S ∈ S então, pela definição de conjunto ordinário, S não é um conjunto
ordinário. Isso implica que S ∉ S. Ou seja, um absurdo, pois de S ∈ S
concluímos que S ∉ S.
2) S ∉ S: Temos então
2
Paradoxo é uma situação que, embora pareça fazer sentido, não tem solução. Exemplos: paradoxo da
biblioteca, do barbeiro, de Cretense (ou do mentiroso), etc.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 11
Se S ∉ S, então, pela definição, S é um conjunto ordinário. Mas, pela definição,
S ∈ S, o que é uma contradição. Ou seja, de S ∉ S concluímos que S ∈ S.
Assim, é um absurdo supor que S é um conjunto, portanto, S não é um conjunto.
Pelo paradoxo de Russell, podemos afirmar ainda que não exista o conjunto de
todos os conjuntos. Ou seja, nem toda coleção de elementos constitui um
conjunto. O conjunto Universo não pode ser considerado o conjunto de todos os
conjuntos em larga escala. Apenas para um pequeno escopo essa definição é
válida. Essa é a chamada álgebra pequena.
1.5 Aplicações de Teoria dos Conjuntos em Computação
Existem diversas aplicações da Teoria dos Conjuntos dentro da computação.
Vamos listar aqui três aplicações das mais simples.
1.5.1 Linguagens de Programação
Na linguagem de programação Pascal é possível definir tipos de dados
baseados em conjuntos finitos, variáveis conjuntos sobre esses tipos de dados,
bem como constantes conjuntos (também finitos). Pascal possui as seguintes
operações sobre conjuntos:
+
(união)
*
(interseção)
-
(diferença)
Exemplo:
dias_semana = set of (seg, ter, qua, qui, sex, sab, dom);
feriado, trabalho, feriado_trabalho, uteis, parados: dias_semana;
feriado := [qua, sab];
trabalho := [seg,..,sex];
feriado_trabalho := trabalho*feriado;
{interseção = {qua}}
uteis := trabalho – feriado;
{diferença = {seg, ter, qui, sex}}
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
parado := [sab, dom] + feriado;
Página 12
{união = {qua, sab, dom}}
1.5.2 Teoria da Computação
Álgebra de conjuntos é fundamental em alguns assuntos relacionados com
Teoria da Computação. A teoria da computação trata da análise do que é
solucionável através de computador, i.e., o que é computável. Instruções são
reconhecidas por um computador se existir um autômato finito para reconhecer
essas instruções. Um autômato finito é um modelo matemático para sistemas
com entradas e saídas discretas. As instruções são conjuntos de palavras
formadas por operações aplicadas sobre um alfabeto. Essas operações são,
basicamente, união, interseção e complemento.
Exemplo:
Suponha o alfabeto ∑ = {a, b}. Sejam as linguagens:
L1 = {a, ab}
L2 = {b, aa}
Assim, L1*L2 denota uma expressão regular que corresponde às strings {ab,
aaa, abb, abaa}. Ou seja, são reconhecidas strings que comecem com uma
palavra de L1 seguida de uma palavra de L2. De forma análoga, a expressão
regular L1 + L2 denota as strings formadas por palavras de L1 ou de L2.
1.5.3 Processamento Digital de Imagens
Na área de processamento digital de imagens, encontramos o uso direto da
Teoria dos Conjuntos nos assuntos relacionados a Morfologia Matemática a qual
envolve técnicas que avaliam as estruturas dentro de uma imagem.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Exemplos:
Página 13
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 14
PARTE II. Teoria dos Números
A Teoria dos Números é a parte da matemática que lida, basicamente, com o
Universo Discreto. Ou seja, apenas números inteiros são reconhecidos. Não
existem valores definidos entre os inteiros x e x + 1, onde x é inteiro.
1. Indução Matemática (Método de Prova)
(Capítulo 1 do Burton)
Princípio da Ordenação
Todo conjunto não-vazio S de números inteiros não-negativos contém um
elemento mínimo. Ou seja, existe algum inteiro a em S tal que a ≤ b, para todo b
pertencente a S.
Teorema 1.1: Propriedade Arquimediana. Se a e b são quaisquer inteiros
positivos pertencentes a um conjunto S de inteiros não-negativos, a é o
elemento mínimo de S, então existe um número inteiro positivo n tal que na ≥ b.
Prova:
Assuma que o teorema é falso. Assim, para algum a e b, na < b, para todo n ∈
Z+. Então o conjunto:
S = {b – na | n ∈ Z+}
é composto apenas por inteiros positivos (pois na < b):
na < b ⇒ na – b < 0 ⇒ b – na > 0
Pelo Princípio da Ordenação, S vai possuir um elemento mínimo. Como todos os
elementos são da forma b – na, vamos supor que o elemento mínimo seja:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 15
b – ma
Observe, porém, que b – (m + 1)a também faz parte do conjunto S, já que S
contém todos os elementos dessa forma. Mas, temos:
b – (m + 1)a = (b – ma) – a < b – ma
Isso implica que b – ma não é o elemento mínimo. Isso mostra que o conjunto
em questão não tem elemento mínimo. Tal contradição (ou absurdo) partiu da
suposição que o Teorema não era válido. Logo, o Teorema é verdadeiro.
Teorema 1.2: Princípio da Indução Finita
Seja S um conjunto de inteiros positivos com as seguintes propriedades:
a) O inteiro 1 ∈ S (Base para a indução)
b) Sempre que o inteiro k ∈ S, o próximo inteiro k + 1 também deve
pertencer a S (Passo da Indução)
Então S é o conjunto de todos os inteiros positivos.
Obs: Entenda “1” como o primeiro elemento de seu conjunto. Por exemplo,
suponha que temos algo a ser provado para todos os inteiros maiores ou iguais
a 2. Assim, o primeiro elemento será o 2.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 16
Exemplos:
1. 12 + 22 + 32 + ... + n2 = n.(2.n + 1).(n + 1)/6
,
para n = 1, 2, 3,...
n = 1: 12 = 1 = 1.(2.1 + 1).(1 + 1)/6
....
n = k: 12 + 22 + 32 + ... + k2 = k.(2.k + 1).(k + 1)/6
(I)
n = k + 1: 12 + 22 + 32 + ... + k2 + (k + 1)2 = ???
de (I):
12 + 22 + 32 + ... + k2 = k.(2.k + 1).(k + 1)/6
Logo:
12 + 22 + 32 + ... + k2 + (k + 1)2 =
(12 + 22 + 32 + ... + k2) + (k + 1)2 =
k.(2.k + 1).(k + 1)/6 + (k + 1)2 =
[(k+1)/6].[k.(2.k + 1) + 6.(k + 1)] =
[(k+1)/6].(2k2 + 7k + 6) = [(k+1)/6].(2k + 3).(k + 2) = (k+1).(2k + 3).(k + 2)/6
(II)
Pela fórmula dada, teríamos, para n = k + 1:
n.(2.n + 1).(n + 1)/6 = (k + 1).[2.(k + 1) + 1].(k + 1 + 1)/6 =
= (k + 1).(2k + 3).(k + 2)/6
(III)
Como II = III, está provado.
2.
Cuidado!! É preciso sempre calcular o caso base!
Suponha que resolvemos não calculá-lo neste exemplo:
Provar que: 1 + 3 + 5 + ... + (2n - 1) = n2 + 3
n = k: 1 + 3 + 5 + ... + (2k - 1) = k2 + 3
(I)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 17
n = k + 1: 1 + 3 + 5 + ... + (2k - 1) + [2(k + 1) – 1] = ???
k2 + 3
n = k + 1:
+ (2k + 1)
= k2 + 3 + 2k + 1 =
= k2 + 2k + 1 + 3 = (k + 1)2 + 3
Ou seja, conseguimos provar a proposição corretamente! No entanto, não existe
nenhum valor para n que satisfaça essa proposição!
n = 1: 1 = 1 ≠ 12 + 3
n = 2: 1 + 3 = 4 ≠ 22 + 3
Logo, o caso base já indicaria que a assertiva é falsa. Nesse caso, não é preciso
fazer qualquer outra prova. Para a indução ser verdadeira, tanto o caso base
quanto o passo da indução devem ser verdadeiros.
Comentários Finais: Métodos de Prova
Um dos mais comuns métodos de prova é a prova direta na qual, dado o
conjunto de hipóteses H1, ..., Hn, devemos mostrar:
H1 ∧ H2 ∧ H3 ∧ … ∧ Hn ⇒ C
onde C é a conclusão a ser inferida.
Provas que não são diretas são ditas indiretas. O primeiro tipo delas é a prova
por contrapositivo, ou seja, mostrar que: ¬C ⇒ ¬(H1 ∧ H2 ∧ H3 ∧ … ∧ Hn)
Outro método de prova indireta é a prova por contradição:
H1 ∧ H2 ∧ H3 ∧ … ∧ Hn ∧ ¬C ⇒ Uma contradição (ou um Absurdo)
Uma implicação da forma H1 ∨ H2 ∨ H3 ∨ … ∨ Hn ⇒ C pode ser escrita como:
(H1 ⇒ C) ∧ (H2 ⇒ C) ∧ …. ∧ (Hn ⇒ C)
e, provando cada (H1 ⇒ C), (H2 ⇒ C), ..., separadamente, temos uma prova por
Casos.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 18
Uma implicação P ⇒ Q é algumas vezes dita vagamente verdadeira ou
verdadeira por default se P é falso. Uma prova vaga é uma prova de uma
implicação P ⇒ Q, mostrando que P é falso. Não é um tipo de prova muito
usado, pois não diz nada sobre Q.
Uma implicação P ⇒ Q é algumas vezes dita trivialmente verdadeira se Q é
verdadeiro. Neste caso, o valor verdade de P é irrelevante. Uma prova trivial de
P ⇒ Q é uma na qual Q é verdadeira sem qualquer referência a P.
Exemplo:
Se x e y são Reais tal que x.y = 0, então (x + y)n = xn + yn, n pertencente aos
inteiros. Ou seja, sejam:
p = “x.y = 0”
q = “(x + y)n = xn + yn”
Vamos analisar
p⇒q
Essa proposição é trivialmente verdadeira para n = 1; (x + y)1 = x1 + y1 é
obviamente verdade e este fato independe da hipótese x.y = 0. Para n ≥ 2, a
hipótese torna-se necessária.
Uma prova construtiva especifica o objeto ou indica como ele pode ser
determinado por algum procedimento ou algoritmo. Uma prova não-construtiva
estabelece a existência de objetos por meios indiretos, como uma prova por
contradição, sem dar direções sobre como encontrá-los.
Exemplo:
É possível provar que existem infinitos números primos sem construir uma lista
de todos eles (prova não-construtiva). Uma prova construtiva criaria tal lista.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 19
2. Teorema da Divisibilidade de Inteiros
(Capítulo 2 do Burton)
2.1 O Algoritmo da Divisão
Teorema 2.1: O algoritmo da Divisão. Dados inteiros a e b, com b > 0, existem
inteiros únicos q e r, satisfazendo:
0≤r<b
a = q.b + r,
Onde q é o quociente e r é o resto.
Corolário: Se a e b são inteiros, com b ≠ 0, então existem inteiros únicos q e r,
tal que:
0 ≤ r < |b|
a = q.b + r,
Problemas:
1. Prove que o quadrado de qualquer inteiro pode ser escrito como 3k ou 3k + 1,
onde k é um inteiro. Por exemplo, 22=4= 3.1 + 1, 32=9 = 3.3, 72=49= 3.16 + 1, ....
Solução
Pelo algoritmo da divisão, temos que qualquer inteiro x quando dividido por 3
pode gerar apenas os restos 0, 1 ou 2, já que 0 ≤ r < 3. Logo, qualquer inteiro ao
ser dividido por 3 gera um número na forma 3j, 3j + 1 ou 3j + 2. Vamos calcular o
valor do quadrado de x para cada caso desses:
I) Para x = 3j: x2 = (3j)2 = 3.(3j2) = 3k
(k um inteiro)
II) Para x = 3j + 1: x2 = (3j + 1)2 = 9j2 + 6j + 1 = 3(3j2 + 2j) + 1 = 3k + 1
(k um inteiro)
2
2
2
2
II) Para x = 3j + 2: x = (3j + 2) = 9j + 12j + 4 = 3(3j + 4j + 1) + 1 = 3k + 1
(k um inteiro)
Logo, o quadrado de qualquer inteiro pode ser escrito como 3k ou 3k + 1, para k
um inteiro.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 20
2. Prove que o cubo de qualquer inteiro pode ser escrito da forma 9k, 9k + 1 ou
9k + 8, com k um inteiro.
Solução
Similar ao que fizemos antes, pelo algoritmo da divisão, temos que qualquer
inteiro x quando dividido por 3 pode gerar apenas os restos 0, 1 ou 2, já que 0 ≤
r < 3. Logo, qualquer inteiro ao ser dividido por 3 gera um número na forma 3j, 3j
+ 1 ou 3j + 2. Vamos calcular o valor do cubo de x para cada caso desses:
I) Para x = 3j: x3 = (3j)3 = 9.(3j3) = 9k
(k um inteiro)
II) Para x = 3j + 1: x3 = (3j + 1)3 = 33.j3 + 3.32.j2 + 3.3.j + 1 = 9.(3.j3 + 3.j2 + j) + 1 =
9k + 1
(k um inteiro)
II) Para x = 3j + 2: x2 = (3j + 2) 3 = 33.j3 + 3.2.32.j2 + 3.22.3.j + 23 = 9.(3.j3 + 3.2.j2 +
+ 22.j) + 8 = 9k + 8
(k um inteiro)
Logo, o cubo de qualquer inteiro pode ser escrito como 9k, 9k + 1 ou 9k + 8,
para k um inteiro.
3. Para n ímpar, mostre que n4 + 4n2 + 11 é da forma 16k.
Solução
Qualquer número ímpar pode ser escrito na forma 2j + 1. Logo, precisamos
substituir n por 2j + 1 e calcular a equação:
n4 + 4n2 + 11 = (2j + 1)4 + 4(2j + 1)2 + 11
= (24j4 + 4.23j3 + 6.22j2 + 4.2.j + 1) + 4.(22.j2 + 2.2.j + 1) + 11
= (16j4 + 32j3 + 24j2 + 8j + 1) + (16j2 + 16j + 4) + 11
= 16j4 + 32j3 + 40j2 + 24j + 16
(I)
Observe que a expressão acima não é da forma 16k! Alguns elementos são,
outros não. Vamos separá-los:
(I) = 16.(j4 + 2j3 + 1) + 40j2 + 24j
(II)
Mais ainda...
(II) = 16.(j4 + 2j3 + 1) + 32j2 + 8j2 + 16j + 8j
= 16.(j4 + 2j3 + 2j2 + j + 1) + 8j2 + 8j = 16w + 8.(j2 + j), onde w é um inteiro. (III)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 21
Isso não resolve nossa questão, mas resolveria se (j2 + j) fosse um número par.
Vamos verificar se isso acontece...
Suposição: (j2 + j) é da forma 2t:
Qualquer número j pode ser escrito como 2m ou 2m + 1.
I) Se j = 2m: j2 + j = (2m)2 + (2m) = 2t
II) Se j = 2m + 1: j2 + j = (2m + 1)2 + (2m + 1) = 4m2 + 4m + 1 + 2m + 1 = 2t
Logo, (j2 + j) sempre é um número par. Assim:
8.(j2 + j) = 8.2t = 16t
De (III):
16w + 8.(j2 + j) = 16w + 16t = 16k
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 22
Exercícios
1. Estabeleça as fórmulas abaixo por Indução Matemática
a) 1 + 2 + 3 + ... + n =
n(n + 1)
, para todo n >= 1
2
b) 1 + 3 + 5 + ... + (2n – 1) = n 2 , para todo n >= 1
c) 1*2 + 2*3 + 3*4 + ... + n*(n+1) =
n(n + 1)(n + 2)
, para todo n >= 1
3
2
⎡ n(n + 1) ⎤
d) 1 + 2 + 3 + ... + n = ⎢
, para todo n >= 1
⎣ 2 ⎥⎦
3
3
3
3
2. a) Se r ≠ 1, mostre que, para qualquer n inteiro positivo:
a (r n +1 − 1)
a + ar + ar + ... + ar =
r −1
2
n
b) Prove que, para qualquer inteiro positivo n,
2n > n .
3. Mostre que qualquer inteiro da forma 6k + 5 também é da forma 3j + 2, mas o
inverso não é verdadeiro.
4. Use o Algoritmo da Divisão para estabelecer o seguinte:
a) O quadrado de qualquer inteiro é da forma 3k ou 3k + 1.
b) O cubo de qualquer inteiro é da forma: 9k, 9k + 1 ou 9k + 8.
c) A quarta potência de qualquer inteiro é da forma 5k ou 5k + 1.
d) Prove que nenhum inteiro na seqüência é um quadrado perfeito:
11, 111, 1111, 11111, ......
e) Verifique que, se um inteiro é simultaneamente um quadrado e um cubo
(como 64 = 8 2 = 4 3 ), então ele deve ser da forma 7k ou 7k + 1.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
5. Prove que 3a 2 − 1 nunca é um quadrado perfeito.
6. Para n>=1, prove que
n(n + 1)(2n + 1)
é um inteiro.
6
7. Mostre que o cubo de qualquer inteiro é da forma 7k ou 7k ± 1.
8. Para n>=1, estabeleça que o inteiro n(7n 2 +5) é da forma 6k.
Página 23
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 24
2.2 Máximo Divisor Comum
(Capítulo 2 do Burton)
Definição 2.1: Um inteiro b é dito divisível por um inteiro a diferente de zero, em
símbolos, a|b (a divide b), se existe algum inteiro c, tal que b = ac. Escrevemos
aðb (a não divide b) para indicar que b não é divisível por a. Podemos também
dizer que a é um divisor de b, a é um fator de b, ou que b é um múltiplo de a.
Se a divide b, então –a também divide. Logo, os divisores vêm em pares.
Teorema 2.2: Para inteiros a, b e c, tem-se:
a) a|0, 1|a, a|a
b) a|1, sse, a = ±1
c) Se a|b e c|d, então (ac)|(bd)
d) Se a|b e b|c, então a|c
e) a|b e b|a, sse a = ±b
f) Se a|b e b≠0, então |a| ≤ |b|
g) Se a|b e a|c ⇒ a|(bx + cy), para todo x e y inteiros
Prova de f: Se a|b e b≠0, então |a| ≤ |b|.
Hipóteses:
I)
a|b
II)
b≠0
Conclusão: |a| ≤ |b|
Se a|b, então existe um c tal que b = ac.
b = ac ⇒ |b| = |ac| ⇒ |b| = |a||c|
Como b≠0 e, por definição, a≠0, então c≠0.
c≠0 ⇒ |c| ≥ 1
|c| ≥ 1
|a||c| ≥ |a|
. |a|
(I)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 25
Mas, de (I), |b| = |a||c|. Logo:
|b| ≥ |a| ou |a| ≤ |b|
Prova de g: Se a|b e a|c ⇒ a|(bx + cy), para todo x e y inteiros.
Hipóteses:
I)
a|b
II)
a|c
Conclusão: a|(bx + cy) para todo x e y inteiros.
Se
a|b ⇒ b = ar
e
a|c ⇒ c = as
Logo, bx + cy = (ar)x + (as)y = a(rx + sy) = ak, k inteiro, já que x e y são inteiros.
Assim, bx + cy = ak ⇒ a|(bx + cy), x e y inteiros.
Definição 2.2: Sejam a e b inteiros, com pelo menos um deles diferente de zero.
O Máximo Divisor Comum (Greatest Commom Divisor) de a e b, GCD(a, b), é
o inteiro positivo d, satisfazendo:
a) d|a e d|b
(d é divisor comum)
b) Se c|a e c|b, então c ≤ d
(d é máximo)
Exemplo:
Divisores de -12: 1, 2, 3, 4, 6, 12 (e o negativo desses)
Divisores de 30: 1, 2, 3, 5, 6, 10, 15, 30 (e o negativo desses)
GCD (-12, 30) = 6
Teorema 2.3: Dados inteiros a e b, com pelo menos um deles diferente de zero,
existem inteiros x e y tal que:
GCD(a, b) = ax + by
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 26
Corolário: Se a e b são inteiros dados, com pelo menos um deles diferente de
zero, então o conjunto:
T = {ax + by : x e y são inteiros}
é precisamente o conjunto de todos os múltiplos de d = GCD(a, b)
Definição 2.3: Dois inteiros a e b, com pelo menos um deles diferente de zero,
são ditos relativamente primos entre si sempre que
GCD(a, b) = 1
Teorema 2.4: Sejam a e b inteiros, com pelo menos um deles diferente de zero.
Então a e b são relativamente primos entre si, sse existem inteiros x e y tal que:
1 = ax + by
Prova:
I) Se a e b são relativamente primos entre si, então GCD(a, b) = 1. Então, pelo
Teorema 2.3, existem inteiros x e y, satisfazendo 1 = ax + by.
II) Suponha que 1 = ax + by para algum x e y e que d=GCD(a, b). Como d|a e
d|b, o Teorema 2.2.g diz que d|(ax + by). Como (ax + by) = 1, então d|1. No
caso, o Teorema 2.2.b diz que d = ±1. Como o GCD deve ser um número
positivo, então d = 1.
Corolário 1: Se GCD(a,b) = d, então GCD (a/d, b/d) = 1.
Prova:
Hipótese: GCD (a, b) = d
Conclusão: GCD (a/d, b/d) = 1
Primeiro, como d = GCD(a, b), então d é divisor de a e b. Logo, a/d e b/d são
números inteiros. Do contrário, deve-se provar que essas divisões geram
inteiros.
Como GCD(a,b) = d, é possível encontrar inteiros x e y tais que
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 27
d = ax + by
Dividindo os dois lados por d, temos:
1 = (a/d)x + (b/d)y
Como a/d e b/d são inteiros, temos: GCD (a/d, b/d) = 1.
Corolário 2: Se a|c e b|c, com GCD (a, b) = 1, então (ab)|c.
Hipóteses:
I)
a|c
II)
b|c
III)
GCD(a, b) = 1
Conclusão: (ab)|c
Prova:
a|c ⇒ c = ar
b|c ⇒ c = bs
Como GCD(a, b) = 1 ⇒ 1 = ax + by, para algum x e y inteiro
1 = ax + by
.c
c = acx + bcy
c = a(bs)x + b(ar)y = absx + abry = ab(sx + ry) = abk,
k inteiro
Logo, c = abk ⇒ (ab)|c.
Teorema 2.5: Lema de Euclid. Se a|(bc), com GCD(a,b) = 1, então a|c.
Prova:
Hipótestes:
I)
a|(bc)
II)
GCD(a, b) = 1
Conclusão: a|c
Como GCD (a, b) = 1 ⇒ Existem x e y tal que: 1 = ax + by.
1 = ax + by
.c
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 28
c = acx + bcy
Como a|(ac) e, por hipótese, a|(bc), então:
a|(acx + bcy)
Mas
c = acx + bcy
Logo:
a|c
Teorema 2.6: Sejam a e b inteiros, com pelo menos um deles diferente de zero.
Para um inteiro positivo d, d=GCD(a,b) sse:
a) d|a e d|b
(d é divisor comum)
b) Sempre que c|a e c|b, então c|d.
(d é máximo)
Problema:
1. Prove que 8|(52n + 7), onde n é um inteiro.
Solução:
8|(52n + 7) ⇒ 52n + 7 = 8r, r inteiro
Vamos tentar provar a proposição acima por indução. Ou seja:
n = 1: 52.1 + 7 = 25 + 7 = 32 = 8.4 = 8r, r inteiro (Base da Indução OK)
....
n = k: 52k + 7 = 8r
n = k + 1: 52(k+1) + 7 = ????
52(k+1) + 7 = 52k+2 + 7 = 52k.52 + 7 =
= 52k.52 + 7 + 52.7 - 52.7
= 52(52k + 7) + 7 - 52.7
= 52(8r) + 7 - 25.7
= 25.8r – 168 = 8k.
Logo, 52k + 7 = 8k. Ou seja: 8|(52k + 7)
(Considera-se verdade....)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 29
2.3 Algoritmo Euclidiano
O GCD entre dois números pode ser achado listando todos os seus divisores,
mas esse é um processo dispendioso para grandes números.
Algoritmo Euclidiano: Sejam a e b dois inteiros cujo maior divisor comum
deseja-se encontrar. Como GCD(|a|, |b|) = GCD(a, b), podemos assumir, sem
perda de generalidade, que a ≥ b > 0. O primeiro passo é usar o algoritmo da
divisão em a e b:
a = q1b + r1, 0 ≤ r1 < b
Se r1 = 0, então b divide a e GCD(a, b) = b. Quando r1 ≠ 0, divida b por r1 para
achar q2 e r2 satisfazendo:
b = q2r1 + r2, 0 ≤ r2 < r1
Se r2 = 0, então paramos e GCD(a, b) = r1. Caso contrário, continuamos como
antes para obtermos:
r1 = q3r2 + r3, 0 ≤ r3 < r2
A divisão prossegue até encontrar algum resto zero, digamos, no passo (n + 1)
quando rn-1 é dividido por rn (não serão precisas mais do que b divisões):
GCD(a, b) = rn (o último resto diferente de zero)
Lema: Se a = qb + r, então GCD(a,b) = GCD(b,r).
Prova:
Hipótese: a = qb + r
Conclusão: GCD(a,b) = GCD(b,r)
Como:
a = qb + r ⇒ r = a – qb
Seja d=GCD(a, b). Logo d|a e d|b ⇒ d|(a – qb) ⇒ d|r
Assim, d é um divisor comum de b e r. Por outro lado, se c é um divisor comum
qualquer de b e r:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 30
c|(qb + r) ⇒ c|a
Isso torna c um divisor comum de a e b, tal que c ≤ d (do contrário, c seria o
GCD e não d). Se supusermos que c é o GCD entre b e r, e c é diferente de d,
poderíamos ter:
I) c > d: Isso implica que d não é o GCD entre a e b, já que c divide os dois.
II) c < d: Mas d divide r. Assim, c não pode ser menor que d.
Como c não pode ser maior ou menor que d, ele tem que ser igual a d.
Exemplo:
1. Encontre o GCD entre 12378 e 3054.
Aplicando o algoritmo da divisão:
12378 = 4.3054 + 162
3054 = 18.162 + 138
162 = 1.138 + 24
138 = 5.24 + 18
24 = 1.18 + 6
18 = 3.6 + 0
Como chegamos ao resto zero, o GCD é o último resto diferente de zero: 6.
Logo, GCD(12378, 3054) = 6
Observe que podemos escrever:
6 = 132.12378 + (-535).3054
Teorema 2.7: Se k > 0, então GCD (ka, kb) = k.GCD(a, b).
Prova:
Seja d = GCD(a, b) ⇒ d = ax + by
kd = kax + kby = GCD (ka, kb)
k.GCD(a, b) = GCD(ka, kb)
Exemplo:
GCD (12, 30) = 6.GCD(2, 5) = 6.1 = 1
.k
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 31
Corolário: Para qualquer k ≠ 0, GCD (ka, kb) = |k|.GCD(a, b).
Definição 2.4: O Mínimo Múltiplo Comum de dois inteiros a e b diferentes de
zero, denotado por LCM (a, b) (Least Commom Multiple), é o inteiro positivo m,
satisfazendo:
a) a|m e b|m
(m é múltiplo comum)
b) Se a|c e b|c, com c > 0, então m ≤ c
(m é mínimo)
Teorema 2.8: Para inteiros positivos a e b:
GCD (a, b).LCM(a, b) = a.b
Corolário: Para qualquer escolha de inteiros positivos a e b, LCM(a, b) = ab, sse
GCD(a, b) = 1.
2.4 Equação Diofântica3
Equação Diofântica é qualquer equação com uma ou mais variáveis que deve
ser resolvida no universo dos inteiros. Uma Equação Diofântica Linear pode ser
escrita como:
ax + by = c,
a, b e c inteiros, com a e b diferentes de zero.
O par de inteiros (x, y) é dito uma solução da equação.
Tal equação pode ter um grande número de soluções mesmo no universo dos
inteiros. Suponha a equação 3x + 6y = 18. São possíveis soluções:
3.4 + 6.1 = 18
3.(-6) + 6.6 = 18
3.10 + 6.(-2) = 18
Mas não existe solução (nos inteiros) para a equação: 2x + 10y = 17. O que
distingue as duas equações?
3
Homenagem a Diophantus (250 a.C.)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 32
Teorema 2.9: A Equação Diofântica Linear ax + by = c tem solução sse d|c,
onde d = GCD(a, b). Se (x0, y0) é uma solução particular da equação, então
todas as soluções são dadas por:
x = x0 + (b/d)t
e
y = y0 – (a/d)t
onde t é um inteiro qualquer, atuando como parâmetro para obter a família de
soluções.
Exemplo:
172x + 20y = 1000
Primeiro, precisamos saber se a equação tem solução. Para isso, calculamos o
GCD (172, 20) usando o algoritmo Euclidiano:
172 = 20.8 + 12
(1)
20 = 12.1 + 8
(2)
12 = 8.1 + 4
(3)
8 = 4.2 + 0
Logo, GCD (172, 20) = 4. Como 4|1000, a equação tem solução no universo dos
inteiros. É preciso agora encontrar uma solução particular para a equação.
Vamos aproveitar os cálculos já executados pelo algoritmo Euclidiano para
tentar encontrar essa solução.
A partir de (3) anterior, temos:
12 = 8.1 + 4 ⇒ 4 = 12 – 8.1
(4)
De (2), temos:
8 = 20 – 12.1
(5)
Substituindo (5) em (4):
4 = 12 – (20 – 12.1).1
(6)
Observe que estamos tentando encontrar uma solução para a equação. Esse é
o objetivo a ser seguido. Logo, não há a necessidade de resolver o lado direito
da equação (6). Mas podemos simplificá-lo tendo nosso objetivo como meta:
4 = 12 – 20 + 1.12
4 = 2.12 – 20
(7)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 33
Agora, de (1):
12 = 172 – 20.8
Em (7):
4 = 2.(172 – 20.8) – 20
4 = 2.172 – 20.16 – 20
4 = 2.172 – 17.20
Assim, concluímos que:
172.2 + 20.(-17) = 4
(8)
quando procuramos uma solução para a equação:
172x + 20y = 1000
Ou seja, para atingirmos nosso objetivo, basta multiplicarmos os dois lados de
(8) por 250:
172.(2.250) + 20.(-17.250) = 4.250
172.(500) + 20.(-4250) = 1000
Solução particular: x0 = 500 e y0 = -4250. Assim, as soluções gerais são da
forma:
x = 500 + (20/4)t
e
y = -4250 – (172/4)t
x = 500 + 5t
e
y = -4250 – 43t
Essas equações definem a família de soluções para a equação diofântica linear
proposta. Dependendo das condições iniciais impostas no problema. Por
exemplo, suponha que desejamos apenas as soluções que sejam positivas.
Assim, t deve ser escolhido de forma que satisfaça simultaneamente:
x = 500 + 5t > 0
t > -100
e
y = -4250 – 43t > 0
e
t < - 98,94
-100 < t < -98,84
Como t é um inteiro, t = -99. Isso implica que o único valor de t que gera
soluções positivas é -99. Essas soluções são:
x = 500 + 5.(-99)
e
x=5 e
y = -4250 – 43.(-99)
y=7
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 34
Corolário: Se GCD (a, b) = 1 e se (x0, y0) é uma solução particular da equação
diofântica ax + by = c, todas as outras soluções são dadas por:
x = x0 + bt
e
y = y0 – at
onde t é um inteiro qualquer.
Exemplo: 5x + 22y = 18 tem x0 = 8 e y0 = -1 como uma solução. Pelo corolário,
uma solução completa é dada por:
x = 8 + 22t
e
onde t é um inteiro qualquer.
y = -1 – 5t
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 35
Exercícios
1. Dados os inteiros a,b,c,d, verifique o seguinte:
a) Se a | b, então a | bc
b) Se a | b e a | c, então a 2 | bc
c) a | b se e só se ac | bc, onde c ≠ 0
d) Se a | b e c | d, então ac | bd.
2. Para n >= 1, use a indução matemática para estabelecer cada uma das
seguintes regras de divisibilidade:
a) 8 | (5 2 n + 7)
b) 15 | (2 4 n − 1)
3. a) Prove que se a e b são ambos inteiros ímpares, então 16 | (a 4 + b 4 − 2)
b) Estabeleça que a diferença de dois cubos consecutivos nunca é divisível por
2.
c) Prove que se o GCD(a, b) = 1, então GCD(a + b, ab) = 1.
d) Prove que, para um inteiro positivo n e qualquer inteiro a, GCD(a, a+n) divide
n; assim, GCD(a, a+1) = 1.
e) GCD(2a + 1, 9a + 4) = 1, a inteiro.
f) Se a e b são inteiros diferentes de zero, prove que GCD(2a - 3b, 4a - 5b)
divide b.
4. Determine todas as soluções inteiras positivas da seguinte Equação
Diofântica: 54x + 21y = 906.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 36
3. Primos e sua Distribuição
(Capítulo 3 do Burton)
3.1 Teorema Fundamental da Aritmética
Definição 1: Um inteiro p > 1 é chamado um número primo, se seus únicos
divisores positivos são 1 e p. Um inteiro maior que 1 que não é primo é chamado
composto.
Teorema 1: Se p é primo e p|(ab), então p|a ou p|b ou ambos.
Prova:
Hipóteses:
I)
p é primo
II)
p|(ab)
Conclusão: p|a ou p|b ou ambos.
Se p|a, a solução é clara. Consideremos, então, o caso que pða. Como os
únicos divisores positivos de p são 1 e ele mesmo, então GCD (p, a) = 1. Assim,
de acordo com o Lema de Euclid4, p|b.
Corolário 1: Se p é um primo e p|(a1a2....an), então p|ak para algum k, onde 1 ≤
k ≤ n.
Corolário 2: Se p, q1, q2, ...., qn são todos primos e p|(q1q2....qn), então p = qk
para algum k, onde 1 ≤ k ≤ n.
4
Lembrando: Lema de Euclid: Se a|(bc), com GCD(a, b) = 1, então a|c.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 37
Teorema 2: Teorema Fundamental da Aritmética. Todo inteiro positivo n, n > 1,
pode ser expresso como um produto de primos. Essa representação é única,
não importa a ordem que os fatores apareçam.
Corolário: Qualquer inteiro positivo n, n > 1, pode ser escrito unicamente na
forma canônica:
n = p1k1. p2k2.... prkr
onde, para i = 1, 2, ..., r, cada ki é um inteiro positivo e cada p1 é um primo, com
p1 < p2 < ... < pr.
Teorema 3: Teorema de Pitágoras. O número
2 é um irracional puro.
Prova:
Suponha o contrário,
Se
2 é um racional, i.e.,
2 = a/b, então a =
2 =a/b, com GCD (a, b) = 1.
2 b e b = a/ 2 . Como GCD (a,b) = 1, implica que
existem inteiros r e s satisfazendo:
ar + bs = 1
Multiplicando os dois lados por
2 (ar + bs) =
2
( 2 a)r + ( 2 b)s =
Como a =
2:
2
2 b e b = a/ 2 :
2br + as =
2
Como b, r, a e s são todos inteiros, temos que
absurdo. Logo,
2 é um irracional.
2 é um inteiro o que é um
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 38
Problemas:
1. Prove que o único primo da forma n3 – 1 é 7.
Solução:
n3 – 1 = (n – 1).(n2 + n + 1)
Para que esse número seja um primo, ele só pode ser divisível por 1 e por ele
mesmo. Assim, podemos ter:
(n – 1).(n2 + n + 1)
1 .
p
(I)
p .
1
(II)
(I)
Se n – 1 = 1 ⇒ n = 2
p = n2 + n + 1 = 22 + 2 + 1 = 7
(II)
Se n2 + n + 1 = 1
n2 + n = 0 ⇒ n.(n + 1) = 0 ⇒ n = 0 ou n = -1.
n = 0 ⇒ p = n – 1 = -1
n = -1 ⇒ p = n – 1 = -2
Em ambos os casos, p seria um número negativo o que não é possível. Logo, o
único primo na forma n3 – 1 é 7.
2. Prove que o único primo da forma n2 – 4 é 5.
Solução:
n2 – 4 = (n + 2).(n – 2)
1
.
p
(I)
p
.
1
(II)
(I) n + 2 = 1 ⇒ n = -1 ⇒ p = -3 (Errado !)
(II) n – 2 = 1 ⇒ n = 3 ⇒ p = 5 (OK)
Logo, o único primo da forma n2 – 4 é 5.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 39
3.2 O Crivo5 de Eratóstenes6
Como determinar se um dado inteiro é primo ou não? Uma forma é tentar dividir
o número por todos os seus predecessores e verificar se algum deles o divide
(menos o 1). Esse processo pode ser simplificado da seguinte forma: Se um
inteiro a, a > 1, é composto, podemos escrever a = bc, onde 1 < b < a e 1 < c <
a. Assumindo que:
b ≤ c ⇒ b2 ≤ bc = a
Logo
b≤
a
Como b > 1, o Teorema 2 garante que b tem, pelo menos, um fator primo p.
Então p ≤ b ≤
a . Como p|b e b|a ⇒ p|a. Ou seja, um número composto a
sempre vai possuir um divisor primo p, satisfazendo p ≤
a.
Para testar a primalidade de um inteiro a, a > 1, basta dividir a pelos primos
menores que
a . Seja, por exemplo, a = 509.
509 = 22,56. Assim, precisamos
apenas testar os primos menores que 22, i.e., 2, 3, 5, 7, 11, 13, 17, 19. Como
nenhum deles divide 509, então ele é primo.
Suponha que desejamos encontrar todos os primos abaixo de um número n. O
esquema definido por Eratóstenes lista todos os números de 2 a n em sua
ordem natural e então elimina todos os números múltiplos 2p, 3p, 4p, 5p, ....,
com p ≤
n . Os inteiros que sobrarem na lista (aqueles que não caem no
“crivo”) são primos.
Teorema 4: Euclid. Existe um infinito número de primos.
5
6
Crivo = peneira
Eratóstenes, matemático grego, 276-194 a.C.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 40
Prova: Por contradição, vamos supor que o número de primos é finito. Assim,
teríamos um primo pn que seria o último número primo. Vamos então formar um
número composto P gerado pelo produto de todos os primos:
P = p1. p2. p3.... pn.
Dessa forma, existe um P’ = P + 1. Esse número deve ser composto já que, se
ele fosse primo, ele seria um fator de P o que seria um absurdo. Assim, P’ é
composto. Sendo assim, ele deve ser divisível por um primo pk. Observe que:
pk|P
já que pk deve ser igual a um dos pi’s, 1 ≤ i ≤ n. Assim:
pk|P
e
pk|P’
ou seja
pk|(P’ – P)
pk|(P + 1 – P)
pk|1 ⇒ pk = ±1
Como um número primo deve ser positivo, pk = 1. Mas pk deve ser maior que 1
para ser primo. Como chegamos a uma contradição, a negação da proposição
está errada e a proposição é verdadeira.
Logo, o número de primos é infinito.
3.3 A Conjectura de Goldbach7
Em 1845, Joseph Bertrand apresentou uma teoria que os números primos são
bem distribuídos no sentido que entre n ≥ 2 e 2n existe, pelo menos, um número
primo. Tal teoria não foi provada por Bertrand, mas foi verificada para todo n até
3.000.000. A prova formal veio em 1852 pelo matemático russo Tchebyshev.
7
Citada em 1742 em uma carta enviada a Euler.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 41
Pode-se provar que existem infinitos números primos, mas ainda não se sabe
como eles se distribuem. Não se sabe nem se existem infinitos “primos gêmeos”
(primos da forma p e p + 2 – como 11 e 13, 17 e 19, etc.). Os maiores gêmeos
encontrados até 2002 têm 51.090 dígitos8. Os primos podem estar próximos
(como os gêmeos) ou muito distantes. A maior distância já encontrada entre
primos consecutivos é de 864.
Número de primos gêmeos menores que N
N
atual
estimado
106
8.169
8.248
108
440.312
440.368
1010
27.411.417
27.412.679
A conjectura de Goldbach diz que todo inteiro par maior que 4 pode ser escrito
como a soma de dois primos (podem ser iguais e ele aceita o 1 como primo). A
conjectura nunca foi provada, mas já foi comprovada para números até 4.1011.
A primeira parte da prova só surgiu em 1922 (quase 200 anos depois) por Hardy
e Littlewood. Eles mostraram que qualquer número ímpar grande é a soma de
três primos. Em 1937, o russo Vinogradov comprovou o trabalho de Hardy e
Littlewood.
Aceita-se que a conjectura de Goldbach é verdadeira em quase 100% dos
casos. No entanto, quase 0% de casos falsos não descarta a possibilidade de
infinitos falsos.
8
Maiores informações: http://primes.utm.edu/top20/page.php?id=1
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 42
3.4 Mais sobre primos
Em dezembro de 2005, a Universidade Estadual do Missouri (EUA) anunciou
que um cluster de 700 computadores calculou o maior número primo que se tem
notícia. 9
A monstruosidade numérica tem 9.152.052 dígitos. Era a segunda vez naquele
ano que um número primo de proporções astronômicas é calculado. A iniciativa
faz parte do projeto computacional Gimps (sigla em inglês para Grande Busca
de Número Primo Mersenne na Internet), que oferece um prêmio de US$ 100 mil
a quem chegar a um número primo com dez milhões de dígitos.
O Gimps conta com a participação de 200 mil computadores que oferecem
voluntariamente o seu poder de processamento ocioso para chegar a números
primos Marsenne gigantescos.
Um número primo é um número que só pode ser dividido por um ou por ele
mesmo sem que tenha um resto de divisão. Um Mersenne é um tipo especial de
primo que é definido por dois elevado a uma potência específica, menos um. Por
exemplo, sete é um Mersenne, pois é dois elevado ao cubo menos um. O
número recém-anunciado é dois elevado à 30.402.457ª potência menos 1.
Números primos - e Mersenne especialmente - têm um papel fundamental na
definição de algoritmos computacionais de criptografia Quanto maiores esses
números, mais difíceis de se quebrar o esquema de segurança.
Apesar disso, números gigantescos, como o recém-anunciado, têm um interesse
puramente acadêmico, devido à dificuldade de serem usados em um sistema
comercial. Para se ter uma idéia do que isso representa, seriam necessários 67
9
Maiores informações: http://info.abril.com.br/aberto/infonews/122005/28122005-4.shl
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 43
mil anos de processamento de um computador comandado por um Pentium a 90
MHz para se calcular o número anunciado em dezembro de 2005.
Antes disso, em 2004, Manindra Agrawal, Neeraj Kayal e Nitin Saxena
apresentaram um algoritmo eficiente para definir se um dado número é primo ou
não. Por eficiente diz-se de algoritmos que podem chegar a uma solução com
tempo de processamento definido por uma função polinomial relacionada com a
entrada. O algoritmo é baseado no Pequeno Teorema de Fermat para anéis
polinomiais sobre campos finitos. 10
Exercícios
1. Prove:
a) Qualquer número primo da forma 3n+1 também é da forma 6m+1.
b) O único primo da forma n 3 − 1 é 7.
c) O único primo para o qual 3p+1 é um quadrado perfeito é p = 5.
2. Prove o Teorema 3.2 (Teorema Fundamental da Aritmética)
3. a) Se p >= 5 é um número primo, mostre que p 2 + 2 é composto.
b) Dado que p é primo e que p | a , prove que p | a .
n
n
n
4. Prove:
a) Todo inteiro da forma n 4 + 4 , com n>1, é composto.
b) Se n > 4 é composto, então n divide (n-1)!.
c) Encontre todos os primos que dividem 100!.
5. a) Mostre que
10
p é irracional para qualquer primo p.
http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 44
b) Mostre que qualquer número composto com 3 dígitos deve ter um fator primo
menor ou igual a 31.
6. Se GCD(a,b) = p, um primo, quais são os valores de gcd(a 2 , b 2 ) , gcd(a 2 , b) e
gcd(a 3 , b 2 ) .
7. Faça programas, usando Borland C, que:
a) Calcule os fatores primos de um número n até n = 30.000.
b) Calcule todos os primos abaixo de um número n qualquer, n até 30.000,
usando o Crivo de Eratóstenes.
OBS: Não se preocupem com a eficiência dos programas.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 45
Anexo: Lista de Primos
Os primeiros 1.000 Primos
(o 1.000o é 7919)
Para mais informações sobre primos: http://primes.utm.edu/
2
31
73
127
179
233
283
353
419
467
547
607
661
739
811
877
947
1019
1087
1153
1229
1297
1381
1453
1523
1597
1663
1741
1823
1901
1993
2063
2131
2221
2293
2371
2437
2539
2621
2689
2749
2833
2909
3001
3083
3187
3259
3343
3433
3517
3
37
79
131
181
239
293
359
421
479
557
613
673
743
821
881
953
1021
1091
1163
1231
1301
1399
1459
1531
1601
1667
1747
1831
1907
1997
2069
2137
2237
2297
2377
2441
2543
2633
2693
2753
2837
2917
3011
3089
3191
3271
3347
3449
3527
5
41
83
137
191
241
307
367
431
487
563
617
677
751
823
883
967
1031
1093
1171
1237
1303
1409
1471
1543
1607
1669
1753
1847
1913
1999
2081
2141
2239
2309
2381
2447
2549
2647
2699
2767
2843
2927
3019
3109
3203
3299
3359
3457
3529
7
43
89
139
193
251
311
373
433
491
569
619
683
757
827
887
971
1033
1097
1181
1249
1307
1423
1481
1549
1609
1693
1759
1861
1931
2003
2083
2143
2243
2311
2383
2459
2551
2657
2707
2777
2851
2939
3023
3119
3209
3301
3361
3461
3533
11
47
97
149
197
257
313
379
439
499
571
631
691
761
829
907
977
1039
1103
1187
1259
1319
1427
1483
1553
1613
1697
1777
1867
1933
2011
2087
2153
2251
2333
2389
2467
2557
2659
2711
2789
2857
2953
3037
3121
3217
3307
3371
3463
3539
13
53
101
151
199
263
317
383
443
503
577
641
701
769
839
911
983
1049
1109
1193
1277
1321
1429
1487
1559
1619
1699
1783
1871
1949
2017
2089
2161
2267
2339
2393
2473
2579
2663
2713
2791
2861
2957
3041
3137
3221
3313
3373
3467
3541
17
59
103
157
211
269
331
389
449
509
587
643
709
773
853
919
991
1051
1117
1201
1279
1327
1433
1489
1567
1621
1709
1787
1873
1951
2027
2099
2179
2269
2341
2399
2477
2591
2671
2719
2797
2879
2963
3049
3163
3229
3319
3389
3469
3547
19
61
107
163
223
271
337
397
457
521
593
647
719
787
857
929
997
1061
1123
1213
1283
1361
1439
1493
1571
1627
1721
1789
1877
1973
2029
2111
2203
2273
2347
2411
2503
2593
2677
2729
2801
2887
2969
3061
3167
3251
3323
3391
3491
3557
23
67
109
167
227
277
347
401
461
523
599
653
727
797
859
937
1009
1063
1129
1217
1289
1367
1447
1499
1579
1637
1723
1801
1879
1979
2039
2113
2207
2281
2351
2417
2521
2609
2683
2731
2803
2897
2971
3067
3169
3253
3329
3407
3499
3559
29
71
113
173
229
281
349
409
463
541
601
659
733
809
863
941
1013
1069
1151
1223
1291
1373
1451
1511
1583
1657
1733
1811
1889
1987
2053
2129
2213
2287
2357
2423
2531
2617
2687
2741
2819
2903
2999
3079
3181
3257
3331
3413
3511
3571
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
3581
3659
3733
3823
3911
4001
4073
4153
4241
4327
4421
4507
4591
4663
4759
4861
4943
5009
5099
5189
5281
5393
5449
5527
5641
5701
5801
5861
5953
6067
6143
6229
6311
6373
6481
6577
6679
6763
6841
6947
7001
7109
7211
7307
7417
7507
7573
7649
7727
7841
3583
3671
3739
3833
3917
4003
4079
4157
4243
4337
4423
4513
4597
4673
4783
4871
4951
5011
5101
5197
5297
5399
5471
5531
5647
5711
5807
5867
5981
6073
6151
6247
6317
6379
6491
6581
6689
6779
6857
6949
7013
7121
7213
7309
7433
7517
7577
7669
7741
7853
3593
3673
3761
3847
3919
4007
4091
4159
4253
4339
4441
4517
4603
4679
4787
4877
4957
5021
5107
5209
5303
5407
5477
5557
5651
5717
5813
5869
5987
6079
6163
6257
6323
6389
6521
6599
6691
6781
6863
6959
7019
7127
7219
7321
7451
7523
7583
7673
7753
7867
3607
3677
3767
3851
3923
4013
4093
4177
4259
4349
4447
4519
4621
4691
4789
4889
4967
5023
5113
5227
5309
5413
5479
5563
5653
5737
5821
5879
6007
6089
6173
6263
6329
6397
6529
6607
6701
6791
6869
6961
7027
7129
7229
7331
7457
7529
7589
7681
7757
7873
3613
3691
3769
3853
3929
4019
4099
4201
4261
4357
4451
4523
4637
4703
4793
4903
4969
5039
5119
5231
5323
5417
5483
5569
5657
5741
5827
5881
6011
6091
6197
6269
6337
6421
6547
6619
6703
6793
6871
6967
7039
7151
7237
7333
7459
7537
7591
7687
7759
7877
Cinco primos aleatórios de 200 dígitos
3617
3697
3779
3863
3931
4021
4111
4211
4271
4363
4457
4547
4639
4721
4799
4909
4973
5051
5147
5233
5333
5419
5501
5573
5659
5743
5839
5897
6029
6101
6199
6271
6343
6427
6551
6637
6709
6803
6883
6971
7043
7159
7243
7349
7477
7541
7603
7691
7789
7879
3623
3701
3793
3877
3943
4027
4127
4217
4273
4373
4463
4549
4643
4723
4801
4919
4987
5059
5153
5237
5347
5431
5503
5581
5669
5749
5843
5903
6037
6113
6203
6277
6353
6449
6553
6653
6719
6823
6899
6977
7057
7177
7247
7351
7481
7547
7607
7699
7793
7883
Página 46
3631
3709
3797
3881
3947
4049
4129
4219
4283
4391
4481
4561
4649
4729
4813
4931
4993
5077
5167
5261
5351
5437
5507
5591
5683
5779
5849
5923
6043
6121
6211
6287
6359
6451
6563
6659
6733
6827
6907
6983
7069
7187
7253
7369
7487
7549
7621
7703
7817
7901
3637
3719
3803
3889
3967
4051
4133
4229
4289
4397
4483
4567
4651
4733
4817
4933
4999
5081
5171
5273
5381
5441
5519
5623
5689
5783
5851
5927
6047
6131
6217
6299
6361
6469
6569
6661
6737
6829
6911
6991
7079
7193
7283
7393
7489
7559
7639
7717
7823
7907
3643
3727
3821
3907
3989
4057
4139
4231
4297
4409
4493
4583
4657
4751
4831
4937
5003
5087
5179
5279
5387
5443
5521
5639
5693
5791
5857
5939
6053
6133
6221
6301
6367
6473
6571
6673
6761
6833
6917
6997
7103
7207
7297
7411
7499
7561
7643
7723
7829
7919
• 2039568783564019774057658669290345772801939933143482630947726464532830627227
01277632936616063144088173312372882677123879538709400158306567338328279154499
69836607190676644003707421711780569087279284814911202228633214487618337632651
2083574821647933992961249917319836219304274280243803104015000563790123
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 47
• 5318722890542041841850847343751333994083036139821308566452994649309521786060
45848877129147820387996428175564228204785846141207532462936339834139412401975
33870579464659548732436519479282218947309227399358058796457165967808448415260
3881094176995594813302284232006001752128168901293560051833646881436219
• 3197053047011415391557201372009746646667925260594057925396809749294697835128
21793995613718943171723765238853752439032835985158829038528214925658918372196
74208946468396023991995088235584476605536517993761032612767517885730626095555
0407044463370239890187189750909036833976197804646589380690779463976173
• 2505569523276462144272467774880323517121390946439883947261933473520925266163
05469220133287929222242315761834129196430398011844978805263868522770723615504
74443863838167032161394928053025401460288770796037575201680751060284659049272
4216092721283154099469988532068424757856392563537802339735359978831013
• 2902453291655700251160164872177402875088379132955716094639143487783196544891
18435855243301969001872061575755804802874062021927719647357060447135321577028
92926957857476054726831005505686738687595904511909396797220512427044164845082
5188877095173754196346551952542599226295413057787340278528252358809329
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 48
4. Teoria das Congruências
(Capítulo 4 do Burton)
A Teoria das Congruências apresenta uma outra abordagem ao problema da
divisibilidade. Faremos aqui uma mudança no universo de representação dos
números; um mapeamento de um universo de infinitos números para outro com
uma quantidade limitada de elementos. Aqui, os números são representados
através do resto de uma divisão.
4.1 Propriedades Básicas da Congruência
Definição 1: Seja n um inteiro positivo. Dois inteiros a e b são ditos congruentes
módulo n, simbolizado por:
a ≡ b mod n
se n divide a diferença a – b; i.e., a – b = kn, para algum inteiro k.
Exemplos:
Considere n = 7:
8 ≡ 1 mod 7, pois 8 – 1 = 7 = 1.7
17 ≡ 3 mod 7, pois 17 – 3 = 14 = 2.7
3 ≡ 24 mod 7, pois 3 – 24 = -21 = (-3).7
-31 ≡ 11 mod 7, pois -31 – 11 = -42 = (-6).7
-15 ≡ -64 mod 7, pois -15 – (-64) = 49 = 7.7
Se n não divide a diferença a – b, dizemos que a é incongruente a b módulo n,
no caso, a † b mod n.
Exemplo: 25 † 12 mod 7, pois 25 – 12 = 13 ≠ 7k, para qualquer k inteiro.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 49
Teorema 4.1: Para inteiros quaisquer a e b, a ≡ b mod n, sse, a e b têm o
mesmo resto não-negativo quando divididos por n.
Prova:
a ≡ b mod n ⇒ a = b + kn, para algum inteiro k.
A divisão de b por n gera um resto r, de acordo com o teorema da divisibilidade:
b = qn + r, 0 ≤ r < n
Logo,
a = b + kn
a = (qn + r) + kn
a = n(q + k) + r = q1n + r
Assim, a e b têm o mesmo resto quando divididos por n.
Teorema 4.2: Seja n > 1 e a, b, c e d inteiros quaisquer:
a) a ≡ a mod n
b) Se a ≡ b mod n, então b ≡ a mod n
c) Se a ≡ b mod n e b ≡ c mod n, então a ≡ c mod n
d) Se a ≡ b mod n e c ≡ d mod n, então
a + c ≡ b + d mod n
ac ≡ bd mod n
e) Se a ≡ b mod n, então a + c ≡ b + c mod n e ac ≡ bc mod n
f) Se a ≡ b mod n, então ak ≡ bk mod n, para qualquer inteiro positivo k
Exemplos:
1. Prove que 41| (220 – 1)
Solução:
Vamos tentar resolver o problema tratando casos mais simples. Vamos procurar
primeiro a relação entre 41 e alguma potência de 2. Por exemplo:
25 ≡ -9 mod 41
(25)4 ≡ (-9)4 mod 41
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 50
220 ≡ (-9)4 mod 41
220 ≡ (-9)2.(-9)2 mod 41
220 ≡ 81.81 mod 41
Mas
81 ≡ -1 mod 41
Logo
220 ≡ (-1).(-1) mod 41
220 ≡ 1 mod 41
Do Teorema 4.2.e:
220 – 1 ≡ 1 - 1 mod 41
220 – 1 ≡ 0 mod 41
Assim, 220 – 1 é múltiplo de 41. Logo, 41|(220 – 1).
2. Encontrar o resto da divisão de 1! + 2! + 3! + .... + 100! Quando divididos por
12.
Solução:
Observe que 4! = 24 ≡ 0 mod 12
Assim, para k ≥ 4:
k! = 4!.5.6.7....k = múltiplos de 4!
Logo, k! ≡ 0 mod 12, para k ≥ 4.
Ou seja,
1! + 2! + 3! + .... + 100! ≡ 1! + 2! + 3! mod 12
1! + 2! + 3! + .... + 100! ≡ 1 + 2 + 6 mod 12
1! + 2! + 3! + .... + 100! ≡ 9 mod 12
Logo, o resto da divisão de 1! + 2! + 3! + .... + 100! por 12 é 9.
Teorema 4.3: Se ca ≡ cb mod n, então a ≡ b mod (n/d), onde d = GCD (c, n)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 51
Prova:
Hipótese: ca ≡ cb mod n
Conclusão: a ≡ b mod (n/d), onde d = GCD (c, n)
Como ca ≡ cb mod n, podemos escrever:
ca – cb = kn, para algum inteiro k
Considerando que GCD (c, n) = d (não faz parte da conclusão!), implica que
existem inteiros r e s, tal que c = dr e n = ds, com GCD(r, s) = 1. Logo:
ca – cb = kn
dra – drb = kds
r.(a – b) = ks ⇒ s|[r(a – b)]
Como GCD (r, s) = 1 ⇒ s|(a – b):
a ≡ b mod s
Mas s = n/d. Logo:
a ≡ b mod (n/d)
Corolário 1: Se ca ≡ cb mod n e GCD (c, n) = 1, então a ≡ b mod n.
Corolário 2: Se ca ≡ cb mod p e pðc, onde p é primo, então a ≡ b mod p.
Exemplo:
1. Calcule o resto de 250 quando dividido por 7.
Solução:
Vamos tentar simplificar o problema encontrando alguma relação entre uma
potência de 2 e 7. Sempre que possível, é interessante trabalhar com
congruências com 1.
Observe que:
23 = 8 ≡ 1 mod 7
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 52
Logo
(23)16 ≡ 116 mod 7
248 ≡ 1 mod 7
Pelo Teorema 4.2.e:
22.248 ≡ 22.1 mod 7
250 ≡ 22 mod 7
2. Considere a congruência 33 ≡ 15 mod 9, ou 3.11 ≡ 3.5 mod 9. Como GCD(3,
9) = 3, o Teorema 4.3 conclui que 11 ≡5 mod 3. Outro exemplo pode ser visto
analisando -35 ≡ 45 mod 8. Ou, 5.(-7) ≡ 5.9 mod 8. Como 5 e 8 são
relativamente primos entre si, podemos obter -7 ≡ 9 mod 8.
Outra situação curiosa é conseguida pela teoria das Congruências. O produto de
dois inteiros, nenhum deles congruente com zero, pode gerar um número
congruente com zero. Por exemplo, 4.3 ≡ 0 mod 12, mas 4 ≠ 0 mod 12 e 3 ≠ 0
mod 12. Isso mostra que se a.b ≡ 0 mod n e GCD(a, n) = 1, então b ≡ 0 mod n.
Uma variação acontece quando n é um número primo p. Nesse caso, se a.b ≡ 0
mod p, com p primo, então ou a ≡ 0 mod p ou b ≡ 0 mod p.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 53
Exercícios
1. Prove cada uma das assertivas:
a) Se a ≡ b mod n e m|n, então a ≡ b mod m
b) Se a ≡ b mod n e c > 0, então ca ≡ cb mod cn
c) Se a ≡ b mod n e os inteiros a, b e n são todos divisíveis por d > 0, então a/d ≡
b/d mod n/d
2. Se a ≡ b mod n, prove que o GCD (a, n) = GCD (b, n).
3. Encontre o resto de 4165 quando dividido por 7.
4. Prove que 53103 + 10353 é divisível por 39.
5. Prove que:
a) Se a é um inteiro ímpar, então a2 ≡ 1 mod 8.
b) Para qualquer inteiro a, a3 ≡ 0, 1 ou 6 mod 7.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 54
4.2 Testes Especiais de Divisibilidade
Uma das aplicações da teoria das congruências consiste em encontrar critérios
especiais sob os quais um dado inteiro é divisível por outro. Vamos começar
mostrando que, dado um inteiro b > 0, qualquer inteiro positivo N pode ser
escrito unicamente em termos de potências de b como:
N = ambm + am-1bm-1 + .... + a2b2 + a1b + a0
onde os coeficientes ak podem ser quaisquer valores menores que b, ou seja, 0,
1, 2, ...., b – 1. Pelo algoritmo da divisão, temos q1 e a0 tal que:
N = q1b + a0
0 <= a0 < b
Se q1 >= b, podemos dividir mais uma vez, obtendo:
q1 = q2b + a1
0 <= a1 < b
Substituindo q1 na equação anterior:
N = (q2b + a1)b + a0 = q2b2 + a1b + a0
Enquanto o quociente for maior ou igual a b, a divisão continua com uma
seqüência decrescente de quocientes até que seja alcançada a representação
final:
N = ambm + am-1bm-1 + ... + a1b + a0
fazendo am = qm.
Podemos escrever também que:
N = (am, am-1,..., a1, a0)b
Ou seja, a notação na base b de N. Na verdade, essa notação já é bastante
conhecida. Quando convertemos um número de decimal para binário estamos,
na verdade, representando um número N da base 10 na base 2. Por exemplo:
105 = (1101001)2
de forma abreviada.
Teorema 4.4: Seja P ( x) =
m
∑c
k =0
k
x k uma função polinomial de x com coeficientes
inteiros ck. Se a ≡ b mod n, então P(a) ≡ P(b) mod n.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 55
Se P(x) é um polinômio, dizemos que a é solução da congruência P(x) ≡ 0 mod
n, se P(a) ≡ 0 mod n.
Corolário: Se a é uma solução de P(x) ≡ 0 mod n, e a ≡ b mod n, então b
também é uma solução.
Teorema 4.5: Seja N = am10m + am-110m-1 + ... + a110 + a0 a expansão decimal
do inteiro positivo N, 0 <= ak < 10, e seja S = a0 + a1 + .... + am. Então 9|N, se e
só se, 9|S.
Prova:
Considere P ( x) =
m
∑a
k =0
k
x k um polinômio com coeficientes inteiros. Observe que
10 ≡ 1 mod 9, assim, pelo Teorema 4.4, P(10) ≡ P(1) mod 9. Mas P(10) = N e
P(1) = S, tal que N ≡ S mod 9. Segue que N ≡ 0 mod 9, sse, S ≡ 0 mod 9.
Teorema 4.6: Seja N = am10m + am-110m-1 + ... + a110 + a0 a expansão decimal
do inteiro positivo N, 0 <= ak < 10, e seja T = a0 - a1 + a2 - .... + (-1)mam. Então
11|N, se e só se, 11|T.
Prova:
Similar a anterior, lembrando que 10 ≡ -1 mod 11.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 56
Exercícios
1. Prove as seguintes afirmativas:
a) Para qualquer inteiro a, o dígito das unidades de a2 é 0, 1, 4, 5, 6 ou 9.
b) Qualquer um dos inteiros de 0 a 9 pode ser o dígito das unidades de a3.
c) Para qualquer inteiro a, o dígito das unidades de a4 é 0, 1, 5 ou 6.
99
2. Encontre os dois últimos dígitos de 9 .
3. Sem fazer divisões verifique se os inteiros 176.521.221 e 149.235.678 são
divisíveis por 9 ou 11.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 57
4.3 Congruências Lineares
Uma equação da forma a.x ≡ b mod n é chamada uma congruência linear, e por
uma solução de tal equação entendemos um inteiro x0 para o qual a.x0 ≡ b mod
n. Por definição, a.x0 ≡ b mod n, sse n|(a.x0 – b), ou, da mesma forma, sse, a.x0
– b = n.y0, para algum inteiro y0. Assim, o problema de encontrar todos os
inteiros que satisfazem a congruência linear ax ≡ b mod n é idêntico ao de
encontrar todas as soluções da equação Diofântica ax – ny = b.
Teorema 4.7: A congruência linear ax ≡ b mod n tem solução sse d|b, onde d =
GCD (a, n). Se d|b, então ela tem d soluções mutuamente incongruentes módulo
n.
OBS: Observe que o Teorema 4.7 reflete exatamente o que caracteriza uma
equação diofântica ter solução. A congruência ax ≡ b mod pode ser expressa
como ax – b = nk ou ax –nk = b. Isso é uma equação diofântica que tem solução
quando GCD(a, n) | b (Teorema 2.9).
Corolário: Se GCD (a, n) = 1, então a congruência linear ax ≡ b mod n tem uma
única solução módulo n.
Teorema 4.8: Teorema Chinês dos Restos. Sejam n1, n2, ..., nr inteiros
positivos tais que GCD (ni, nj) = 1 para i ≠ j. Então o sistema de congruências
lineares:
x ≡ a1 mod n1
x ≡ a2 mod n2
....
x ≡ ar mod nr
tem uma solução simultânea, que é única módulo n1.n2...nr.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 58
Exemplo:
1. O primeiro problema a ser resolvido pelo Teorema Chinês dos Restos foi
postulado no início do Século I por Sun Tsu. Ele pediu para que fosse
encontrado um número inteiro que tivesse resto 2, 3 e 2 quando dividido por 3, 5
e 7 respectivamente. Esse problema corresponde ao sistema de três
congruências:
x ≡ 2 mod 3
x ≡ 3 mod 5
x ≡ 2 mod 7
Solução:
Seja n = 3.5.7 = 105. Para cada k = 1, 2, ..., r, seja:
Nk = n/nk
Assim:
N1 = n/3 = 105/3 = 35
N2 = n/5 = 105/5 = 21
N3 = n/7 = 105/7 = 15
Assim, as congruências lineares:
(n/nk)x ≡ 1 mod nk
para todo k, tornam-se
35x ≡ 1 mod 3
21x ≡ 1 mod 5
15x ≡ 1 mod 7
são satisfeitas por x1 = 2, x2 = 1, x3 = 1, respectivamente. Assim, uma solução é
dada por:
x = 2.(n/n1). x1 + 3.(n/n2).x2 + 2.(n/n3).x3
x = 2.35.2 + 3.21.1 + 2.15.1 = 233
A solução é dada por x mod n, ou seja:
x= 233 ≡ 23 mod 105
Observe que:
23 ≡ 2 mod 3, 23 ≡ 3 mod 5 e 23 ≡ 2 mod 7
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 59
2. Vamos resolver a congruência linear 17x ≡ 9 mod 276
Solução:
Como 276 = 3.4.23, isso é equivalente a encontrar a solução para o sistema de
congruências:
17x ≡ 9 mod 3
ou
-x ≡ 0 mod 3 ⇒ x ≡ 0 mod 3
17x ≡ 9 mod 4
ou
x ≡ 1 mod 4
17x ≡ 9 mod 23
ou
17x ≡ 9 mod 23
Pela primeira equação, como x ≡ 0 mod 3, isso implica que x é da forma 3k, k
inteiro. Logo, na segunda equação, podemos escrever que
3k ≡ 1 mod 4
*3
k ≡ 9k ≡ 3 mod 4
tal que k = 3 + 4j, onde j é um inteiro. Então:
x = 3k = 3.(3 + 4j) = 9 + 12j
Para a última congruência:
17x ≡ 9 mod 23
17(9 + 12j) ≡ 9 mod 23
204j ≡ -144 mod 23
3j ≡ 6 mod 23
j ≡ 2 mod 23
j = 2 + 23t, com t um inteiro
Assim, x = 9 + 12j = 9 + 12(2 + 23t) = 33 + 276t
Para t = 0, x = 33 é uma solução.
Exercícios
1. Resolva as seguintes congruências:
a) 25x ≡ 15 mod 29
b) 5x ≡ 2 mod 26
2. Resolva a congruência linear 17x ≡ 3 mod (2.3.5.7).
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 60
5. Teorema de Fermat11
5.1 Método de Fatoração de Fermat
Em um fragmento de carta para o Padre Marin Mersenne em 1643, Fermat
descreveu uma técnica para fatoração de grandes números. Isso representou o
primeiro grande avanço sobre métodos clássicos de busca por fatores de um
número n. Até então, essa busca ainda era feita por divisões por todos os
números menores que a raiz quadrada de n. O método de fatoração de Fermat
parte da idéia de que a busca por fatores de um número inteiro ímpar n (como
números pares são facilmente reconhecidos, não há perda de generalidade
considerar n ímpar) é equivalente a obter soluções x e y da equação:
n = x2 – y2
(n ímpar!!)
Se n é a diferença entre dois quadrados, então n pode ser fatorado em:
n = x2 – y2 = (x + y).(x – y)
Por outro lado, quando n tem fatoração n = a.b, com a ≥ b ≥ 1, então podemos
escrever:
2
⎛a+b⎞ ⎛a−b⎞
n=⎜
⎟
⎟ −⎜
⎝ 2 ⎠ ⎝ 2 ⎠
2
Mais ainda, como n é um inteiro ímpar, a e b são ímpares também, implicando
que (a + b)/2 e (a – b)/2 são inteiros não-negativos.
A busca começa por possíveis valores de x e y que satisfaçam a equação
n = x2 – y2
ou:
x2 – n = y2
11
Pierre de Fermat, matemático francês (1601-1665)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 61
Primeiro, procura-se o primeiro inteiro k tal que k2 ≥ n. Agora, olhamos
sucessivamente para os números:
k2 – n, (k + 1) 2 – n, (k + 2) 2 – n, (k + 3) 2 – n, ...
até que um valor de m ≥ √n seja encontrado tal que m2 – n seja um quadrado. O
processo não pode seguir indefinidamente já que, eventualmente, chegaremos
a:
2
⎛ n +1⎞
⎛ n −1⎞
⎜
⎟ −n =⎜
⎟
⎝ 2 ⎠
⎝ 2 ⎠
2
que é a representação de n correspondendo à fatoração trivial n = n.1. Se esse
ponto for alcançado sem que uma diferença quadrada seja encontrada, então n
não tem outros fatores além de 1 e dele mesmo (n é primo).
Fermat usou esse procedimento para descobrir, em apenas 11 passos, que:
2027651281 = 44021.46061
Exemplo: Vamos fatorar o número 119143.
De uma tabela de quadrados, encontramos que 3452 < 119143 < 3462. Assim,
só precisamos considerar os valores de (k2 – 119143) que satisfaçam a
desigualdade 346 ≤ k < (119143 + 1)/2 = 59572. Os cálculos procedem como
segue:
3462 – 119143 = 119716 – 119143 = 573
3472 – 119143 = 120409 – 119143 = 1266
3482 – 119143 = 121104 – 119143 = 1961
3492 – 119143 = 121801 – 119143 = 2658
3502 – 119143 = 122500 – 119143 = 3357
3512 – 119143 = 123201 – 119143 = 4058
3522 – 119143 = 123904 – 119143 = 4761 = 692
A última linha apresenta a fatoração:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 62
119143 = 3522 – 692 = (352 + 69).(352 – 69) = 421.283
Como os dois fatores são primos, apenas sete passos foram necessários.
O método de Fermat é mais eficiente quando os dois fatores de n são de mesma
magnitude.
Exemplo: Vamos fatorar o número 23449. O menor quadrado excedendo 23449
é 1542, assim a seqüência (k2 – n) começa com:
1542 – 23449 = 23716 – 23449 = 267
1552 – 23449 = 24025 – 23449 = 576 = 242
Assim, os fatores de 23449 são:
23499 = 1552 – 242 = (155 – 24).(155 + 24) = 179.131
Há ainda uma generalização do método de fatoração de Fermat usando o
conceito de congruência. Aqui, procuramos por inteiros x e y tais que x2 – y2 seja
múltiplo de n. Ou seja:
x2≡ y2 mod n
Tendo obtido esses valores de x e y, podemos calcular pelo algoritmo de
Euclides:
d = GCD(x – y, n)
ou
d = GCD(x + y, n)
Sendo d um divisor de n. É importante considerar na prática que n é o produto
de dois primos (n = p.q). Assim, como d | n, então d = 1, p, q ou p.q.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 63
Exemplo: Suponha que desejamos fatorar o inteiro n = 2189.
Primeiro, precisamos encontrar valores de x e y tal que x2 ≡ y2 mod 2189. A
busca por esses quadrados não é tão trivial. Assim, vamos procurar quadrados
perfeitos perto de múltiplos de 2189. Por exemplo:
812 – 3.2189 = 6
e
1552 – 11.2189 = 54 = 2.27
e
1552 ≡ 2.33 mod 2189
que pode ser entendido como:
812 ≡ 2.3 mod 2189
Quando essas congruências são multiplicadas temos:
(81.155)2 ≡ (2.32)2 mod 2189
Mas
81.155 = 12555 ≡ -579 mod 2189
Logo:
5792 ≡ 182 mod 2189
Assim, temos os valores x = 579 e y = 18. Ou seja:
x2 ≡ y2 mod n
5792 ≡ 182 mod n
Calculamos então:
GCD (579 – 18, 2189) = GCD (561, 2189) = ?
Pelo algoritmo Euclidiano:
2189 = 3.561 + 506
561 = 1.506 + 55
506 = 9.55 + 11
55 = 5.11
Logo, GCD (561, 2189) = 11. Sendo esse um dos fatores primos de 2189. O
outro fator é 199 que pode ser obtido procurando:
GCD (579 + 18, 2189) = GCD (597, 2189) = 199
Com isso, temos que:
2189 = 11.199
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 64
Exercícios
1. Use o teorema de Fermat para fatorar cada um dos seguintes números:
a) 2279
b) 10541
c) 340663
2. Fatore o número 211 – 1 usando o método de fatoração de Fermat.
3. Mersenne definiu que quando um número pode ser escrito como a soma de
dois quadrados relativamente primos entre si de duas formas distintas, ele é
composto e pode ser fatorado como segue: Se n = a2 + b2 = c2 + b2, então:
n=
(ac + bd )(ac − bd )
(a + d )(a − d )
Use esse resultado para fatorar:
a) 493 = 182 + 132 = 222 + 32
b) 38025 = 1682 + 992 = 1562 + 1172
4. Aplique o método generalizado de Fermat para fatorar:
a) 2911 (saiba que: 1382 ≡ 672 mod 2911)
b) 4573 (saiba que: 1772 ≡ 922 mod 4573)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 65
5.2 O Pequeno Teorema de Fermat
Teorema 5.1: Teorema de Fermat: Seja p um primo e suponha que pða. Então:
ap-1 ≡ 1 mod p
Prova:
Vamos começar considerar os primeiros p – 1 múltiplos positivos de a; isto é, os
inteiros:
a, 2a, 3a, ...., (p – 1)a
Nenhum desses números é congruente entre si módulo p (já que todos os
coeficientes são menores que p e pða), assim como nenhum deles é congruente
com zero. Se fossem, teríamos:
r.a ≡ s.a mod p
1 ≤ r < s ≤ (p – 1)
Logo:
r ≡ s mod p
O que é impossível. Assim, o conjunto anterior deve congruente módulo p a 1, 2,
3, ...., p – 1. Multiplicando todas essas congruências juntas, encontramos que:
a.2a.3a....(p – 1)a ≡ 1.2.3....(p – 1) mod p
Assim:
ap-1.(p – 1)! ≡ (p – 1)! mod p
Logo:
ap-1 ≡ 1 mod p
Corolário: Se p é um primo, então ap ≡ a mod p para qualquer inteiro a.
Prova: Quando p|a, a proposição é óbvia. Nesse caso, ap ≡ 0 ≡ a mod p. Se pða,
de acordo com o teorema de Fermat ap-1 ≡ 1 mod p. Quando a congruência é
multiplicada por a, concluímos que ap ≡ a mod p.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 66
É importante ressaltar, porém, que o inverso não é necessariamente verdade.
Ou seja, ap ≡ a mod p não implica que p seja primo, como veremos
posteriormente.
Lema: Se p e q são primos distintos com ap ≡ a mod q e aq ≡ a mod p, então apq
≡ a mod pq.
Prova:
Como ap ≡ a mod p, temos que apq ≡ aq mod p.
Por hipótese, temos que
aq ≡ a mod p ⇒ apq ≡ ap mod p
mas
ap ≡ a mod p
logo
apq ≡ a mod p
ou de forma diferente:
p|(apq - a)
Da mesma forma, podemos concluir que q|(apq - a). Assim, pelo corolário 2 do
teorema 2.4 (se a|c e b|c com GCD(a, b) = 1, então (ab)|c):
pq|(apq - a)
que pode ser re-escrito como:
apq ≡ a mod pq
Esse lema serviu para resolver um problema que perdurou por séculos.
Acreditava-se que n é primo, se e somente se, n|(2n – 2). Por exemplo:
22 – 2 = 2 e 2|2 ⇒ 2 é primo
23 – 2 = 6 e 3|6 ⇒ 3 é primo
24 – 2 = 14 e 4ð14 ⇒ 4 não é primo
25 – 2 = 30 e 5|30 ⇒ 5 é primo
26 – 2 = 62 e 6ð62 ⇒ 6 não é primo
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 67
No entanto, vamos checar o que acontece para n = 341 = 11.31.
Pelo Teorema 5.1:
2340 ≡ 1 mod 341
210 = 1024 = 31.33 + 1 ⇒ 210 ≡ 1 mod 31
Assim
211 = 2.210 ≡ 2.1 ≡ 2 mod 31
e
231 = 2.(210)3 ≡ 2.13 ≡ 2 mod 11
Pelo Lema anterior, temos:
211.31 ≡ 2 mod 11.31
ou
2341 ≡ 2 mod 341
que leva a:
2340 ≡ 1 mod 341
Com isso, temos um número n (341) que satisfaz a condição n|(2n – 2), mas não
é primo. De fato, essa condição funciona para todo n ≤ 340.
De fato, um inteiro n é chamado de pseudoprimo sempre que n|(2n – 2). Pode
ser mostrado que existem infinitos pseudoprimos. Os primeiros são 341, 561,
645 e 1105.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 68
Exercícios
1. Use o teorema de Fermat para verificar que 17 divide 11104 + 1.
2.
a) Se GCD (a, 35) = 1, mostre que a12≡1 mod 35.
b) Se GCD (a, 42) = 1, mostre que 168=3*7*8 divide a6 – 1.
c) Se GCD (a, 133) = GCD (b, 133) = 1, mostre que 133|(a18 – b18).
3. Do teorema de Fermat deduza que, para qualquer inteiro n≥0, 13|(1112n+6 + 1).
4. Prove:
a) a21 ≡ a mod 15, para todo a.
b) a7 ≡ a mod 42, para todo a.
c) a13 ≡ a mod (3*7*13), para todo a.
d) a9 ≡ a mod 30, para todo a.
5. Se GCD (a, 30) = 1, mostre que 60 divide a4 + 59.
6. Encontre o dígito das unidades de 3100 usando o Teorema de Fermat.
7. Para um inteiro a, verifique que a5 e a têm o mesmo dígito das unidades.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 69
6. Generalização de Euler12 do Teorema de Fermat
(Capítulo 7 do Burton)
6.1 Função Phi de Euler
Definição: Para n ≥ 1, seja φ(n) o número de inteiros positivos menores que n e
que são relativamente primos a n.
Exemplo:
Ф(30) = 8 já que existem 8 números menores que 30 e que são relativamente
primos a ele (1, 7, 11, 13, 17, 19, 23, 29).
De forma similar, temos:
Ф(1) = 1, Ф(2) = 1, Ф(3) = 2, Ф(4) = 2, Ф(5) = 4, Ф(6) = 2, Ф(7) = 6, .....
Observe que Ф(1) = 1, pois GCD (1, 1) = 1. Enquanto, se n > 1, então GCD(n, n)
= n ≠ 1.
A função Ф é chamada de função phi de Euler.
Se n é primo, então todo inteiro menor que n é relativamente primo a ele. Assim,
φ(n) = n – 1, se n é primo. Se n > 1 é composto, então n tem um divisor d tal que
1 < d < n. Segue que existem, pelo menos, dois inteiros entre 1 e n que não são
relativamente primos a n (d e n), Como resultado, φ(n) ≤ n – 2.
Precisamos agora definir uma maneira de calcular o valor de φ(n) diretamente da
fatoração de n.
Teorema 6.1: Se p é um primo e k > 0, então:
Ф(pk) = pk – pk-1 = pk(1 – 1/p)
12
Leonhard Euler (1707-1783)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 70
Exemplos:
φ(9) = φ(32) = 32 – 3 = 6
φ(16) = φ(24) = 24 – 23 = 16 – 8 = 8
Lema: Dados inteiros a, b e c, o GCD (a, bc) = 1, se e somente se, GCD(a, b) =
1 e GCD (a, c) = 1.
Prova:
Primeiro, suponha que GCD(a, bc) = 1 e defina que d = GCD(a, b). Então d|a e
d|b. Assim, d|a e d|bc. Isso implica que GCD (a, bc) ≥ d. Como GCD (a, bc) = 1,
então 1 ≥ d o que implica d = 1. O mesmo raciocínio pode ser feito para GCD(a,
c) = 1.
Pela outra direção, considere GCD (a, b) = GCD (a, c) = 1 e assuma que GCD
(a, bc) = d1 > 1. Então d1 deve ter um fator primo divisor p. Como d1|bc, segue
que p|bc; em conseqüência, p|b ou p|c. Se p|b e considerando que p|a (já que p
é um fator de d1 que é divisor de a), então GCD(a, b) ≥ p, que é uma contradição
já que GCD (a, b) = 1 e 1 não é primo. Da mesma forma, a condição p|c leva a
uma conclusão igualmente falsa que o GCD (a, b) ≥ p. Assim d1 = 1 e o lema
está provado.
Teorema 6.2: A função φ é uma função multiplicativa. Ou seja, Ф(mn) = Ф(m)
Ф(n), sempre que m e n não têm fator em comum.
Teorema 6.3: Se o inteiro n>1 pode ser fatorado em p1k1. p2k2.... prkr, então:
Ф(n)=(p1k1 - p1k1-1). (p2k2 – p2k2-1)... (prkr – prkr-1) = n(1 – 1/p1). (1 – 1/p2).. (1 – 1/pr).
Teorema 6.4: Para n>2, Ф(n) é um inteiro par.
Prova: Se n é primo Ф(n) = n – 1 que é par. Se n é ímpar, Ф(n) = n2 – n que é
par. Por último, se n é par, então Ф(n) = n2 – n que é par também.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 71
Exercícios
1.Calcule:
a) Ф(1001)
b) Ф(5040)
c) Ф(36.000)
2. Verifique que a igualdade Ф(n) = Ф(n + 1) = Ф(n + 2) é válida para n = 5186.
3. Estabeleça cada uma das afirmativas abaixo:
a) Se n é um inteiro ímpar, então Ф(2n) = Ф(n).
b) Se n é um inteiro par, então Ф(2n) = 2Ф(n).
c) Ф(3n) = 3.Ф(n), se e somente se 3|n.
4. Prove que a equação φ(n) = φ(n + 2) é satisfeita por n = 2(2p – 1) sempre que
p e 2p-1 forem ambos primos.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 72
6.2 Teorema de Euler
Lema: Seja n > 1 e GCD (a, n) = 1. Se a1, a2, ..., aφ(n) são inteiros positivos
menores que n e relativamente primos a n, então
aa1, aa2, ..., aaφ(n)
são congruentes módulo n a a1, a2, ..., aφ(n) em alguma ordem.
Prova:
Observe que nenhum par dentre os inteiros aa1, aa2, ..., aaφ(n) é congruente
módulo n. Do contrário, teríamos
a.ai ≡ a.aj mod n, 1 ≤ i < j ≤ φ(n)
⇒ ai ≡ aj mod n
⇒ ai = aj
já que ai e aj são menores que n. Isso seria uma contradição. Além do mais,
como GCD(ai, n) = 1 para todo i e GCD(a, n) = 1, o lema relacionado ao
Teorema 6.1 garante que cada um dos a.ai é relativamente primo a n.
Vamos fixar em um a.ai particular. Existe um único inteiro b, onde 0 ≤ b < n, para
o qual a.ai ≡ b mod n. Como
GCD (b, n) = GCD (a.ai, n) = 1
então b deve ser um dos inteiros a1, a2, ..., aφ(n). Isso prova que os números a1,
a2, ..., aφ(n) e os números aa1, aa2, ..., aaφ(n) são idênticos (módulo n).
Teorema 6.4: Teorema de Euler: Se n ≥ 1 e GCD (a, n) = 1, então
aφ(n) ≡ 1 mod n.
Corolário: Fermat: Se p é primo e p ð a, então ap-1 ≡ 1 mod p.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 73
Exemplo:
O Teorema de Euler é bastante útil na redução de inteiros grandes módulo n.
Por exemplo, vamos encontrar os últimos dois dígitos na representação decimal
de 3256. Isso é equivalente a obter o menor inteiro não negativo para o qual 3256
é congruente módulo 100.
Como GCD (3, 100) = 1 e
Ф(100) = Ф(22.52) = 100.(1 – 1/2).(1 – 1/5) = 40
O Teorema de Euler leva a:
340 ≡ 1 mod 100
Pelo algoritmo da divisão 256 = 6.40 + 16; assim:
3256 ≡ 36.40 + 16 ≡ (340)6316 ≡ 316 mod 100
Assim, nosso problema se reduz a calcular 316 mod 100:
34 = 81 ≡ -19 mod 100
316 = (34)4 ≡ (-19)4 mod 100
(-19)4 = (361)2 ≡ (61)2 mod 100
(61)2 ≡ 21 mod 100
Exercícios
1. Use o Teorema de Euler para estabelecer as seguintes assertivas:
a) Para qualquer inteiro a, a37 ≡ a mod 1729
(Sugestão: 1729 = 7.13.19)
b) Para qualquer inteiro a, a13 ≡ a mod 2730
(Sugestão: 2730 = 2.3.5.7.13)
2. Encontre o dígito das unidades de 3100 usando o Teorema de Euler.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 74
7. Aplicações - Criptografia
A matemática discreta encontra seu maior nicho de aplicações na Criptografia.
Existem algumas definições de Criptografia. Se a pergunta for “o que é
criptografia?” temos uma resposta curta:
Criptografia é a ciência da cifragem de dados
e a resposta longa
Criptografia é a ciência que lida com métodos de proteção de dados
através de cifragem e processos relacionados.
A palavra Criptografia vem do grego kryptein (esconder) e gráphein (escrita).
Vamos entender alguns elementos básicos antes de vermos uma aplicação real
baseada na Teoria dos Números.
5.1 Conceitos Básicos
Um sistema de criptografia pressupõe que existe uma mensagem sendo
transferida entre dois elementos: o transmissor e o receptor.
Suponha que um transmissor deseja enviar uma mensagem a um receptor. Mais
ainda, é necessário que essa mensagem seja enviada de modo seguro a fim de
que nenhuma outra pessoa que a intercepte tenha acesso ao seu conteúdo.
Comumente, nos estudos de Criptografia, costuma-se atribuir ao transmissor e
ao receptor os nomes “Alice” e “Bob”. A Figura 2 ilustra essa situação.
Fig. 2.Alice como transmissora de uma mensagem ao receptor Bob.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 75
A mensagem é o texto claro o qual contém a informação que se deseja enviar
sem qualquer mecanismo para escondê-la. Essa mensagem passa por um
processo de Cifragem (Encryption) a fim de esconder seu conteúdo. Esse
processo gera o chamado texto cifrado. O processo inverso à cifragem que
recebe o texto cifrado como entrada e devolve o texto claro como saída é
chamado de Decifragem (Decryption). Esse processo é ilustrado na Figura 3.
Fig. 3. Cifragem e decifragem de uma mensagem (texto claro).
A notação usada para os elementos acima é:
M = Texto claro
C = Texto cifrado
Cifragem = E(M) = C
Decifragem = D(C) = D(E(M)) = M
De uma maneira geral, um terceiro elemento pode ser inserido na Figura 2. Ao
enviar uma mensagem para Bob, Alice não quer que outra pessoa acesse às
informações ali contidas. Mas um outro personagem pode estar “escutando” a
transmissão da informação e pode interceptar a mensagem no canal entre Alice
para Bob. Assim, ele teria a mensagem cifrada que Alice enviou a Bob. É
importante que ele não consiga recuperar o texto claro original. Esse terceiro
elemento é chamado de Criptanalista. E o processo de quebra de uma
mensagem cifrada a fim de recuperar o texto claro é chamado de Criptanálise.
Os sistemas de cifragem/decifragem (chamados de sistemas criptográficos)
devem ser capazes de prover algumas propriedades a todo o processo:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 76
1) Autenticação: Deve ser possível para o receptor assegurar-se de sua origem;
um intruso não deve ser capaz de se mascarar;
2) Integridade: Deve ser possível ao receptor verificar que a mensagem não foi
modificada durante a transmissão; um intruso não deve ser capaz de substituir
uma mensagem verdadeira por uma falsa;
3) Não-repudiação: O emissor não pode negar que enviou uma mensagem.
Um algoritmo criptográfico (cifrador) é uma função matemática usada para cifrar
e decifrar. Em geral, a função é inversível. Ou seja, com poucas modificações, a
função usada para cifrar deve ser a mesma usada para decifrar. Tais algoritmos
dividem-se em:
1) Algoritmo restrito: Nesse caso, a segurança é baseada no algoritmo. Ao
conhecer o método de cifragem, é possível descobrir o texto claro.
Notadamente, esses algoritmos devem ser complexos (para que não sejam
fáceis de serem quebrados) e o processo todo é ineficiente já que a descoberta
do algoritmo o torna inútil.
2) Algoritmos baseados em Chaves: Esses são os algoritmos mais fortes e mais
comuns. O método de cifragem é conhecido por todos, mas a quebra de uma
mensagem depende de uma chave a qual é a fonte de todo o segredo. Diferente
do caso anterior, essa chave pode ser alterada em qualquer momento, tornando
mais difícil a descoberta da mensagem.
Em relação a esses dois modelos, o princípio de Kerckhoffs diz que “A
segurança de um sistema de cifragem deve depender apenas na segurança da
chave K, e não na segurança dos algoritmos”. Isso reforça o que dissemos
anteriormente quanto ao uso de algoritmos restritos ou baseados em chaves.
Todo o processo de cifragem e decifragem com chaves é descrito a seguir. É
possível utilizar uma mesma chave para cifrar e decifrar ou uma chave diferente
em cada processo.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 77
1) Algoritmos que usam a mesma chave para cifrar e decifrar: Algoritmos
Simétricos:
Seja K a chave, temos:
Ek(M) = C
Dk (C) = M
Dk (Ek (M)) = M
2) Algoritmos que usam chaves diferentes para cifrar e decifrar: Algoritmos
Assimétricos:
Seja K1 a chave de cifragem e K2 a chave de decifragem:
Ek1(M) = C
Dk2(C) = M
Dk2(Ek1(M)) = M
Nos algoritmos baseados em chave, foco de nosso estudo a partir de agora, a
segurança é completamente baseada no conhecimento dessa chave. O
algoritmo, em si, é amplamente conhecido. O processo agora de cifragem e
decifragem é como descrito na Figura 4. Compare com a Figura 3 anterior.
Fig. 4. Processo de cifragem e decifragem em algoritmos baseados em chaves.
No caso de algoritmos simétricos, a chave de cifragem é a mesma de
decifragem. Para algoritmos assimétricos, elas são diferentes.
Novamente, focando nossos estudos, vamos analisar a classes dos algoritmos
assimétricos. Como ele utiliza duas chaves, uma para cifrar e outra para decifrar,
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 78
é possível tornar-se uma dessas chaves de conhecimento de todos (digamos, a
chave de cifragem) e outra de conhecimento apenas do emissor (digamos, a
chave de decifragem). Tal modelo é conhecido como Algoritmos de Criptografia
de Chave Pública. A idéia aqui é que uma chave seja conhecida e a outra possa
ser encontrada através dessa, mas de forma não trivial. É nessa classe de
algoritmos que se encontra o algoritmo RSA que destacaremos na próxima
Seção.
Como dito, os algoritmos de chave pública são algoritmos assimétricos, onde a
chave de cifragem é conhecida por todos, mas a chave de decifragem é secreta.
Assim, qualquer um pode cifrar uma mensagem, mas só uma pessoa específica
pode decifrá-la. A chave de cifragem é dita uma chave pública e a chave de
decifragem é a chave secreta.
5.2 Sistema Criptográfico RSA
Em um sistema criptográfico de chave pública, a cifragem não usa uma chave
secreta; essa só é necessária na decifragem. Para tanto são usadas as
chamadas “One-Way Trapdoor Functions”. Uma função ft(x): D → R é uma
função one-way (de mão única), se ela for fácil calcular para todo x ∈ D e difícil
de inverter para quase todos os valores em R. Contudo, se a informação
trapdoor (porta dos fundos) t é usada, então, para todo y ∈ R, é fácil calcular
x∈D, satisfazendo y=ft(x).
Em 1978, Rivest, Shamir e Adleman (Figura 5) propuseram o criptossistema de
chave pública RSA baseado em funções modulares em um one-way trapdoor
functions. Além do uso de funções modulares, o algoritmo toma como base
também o uso de números primos grandes e a dificuldade de fatoração de
números com grandes quantidades de dígitos.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 79
Fig. 5. Rivest, Shamir e Adleman – criadores do RSA.
O algoritmo RSA funciona da seguinte forma:
1) Alice escolhe dois números primos aleatórios, p e q, tais que eles
tenham, aproximadamente, o mesmo número de dígitos
2) Calcula: N = p.q
3) Calcula: Ф(N) = (p - 1).(q - 1)
4) Escolhe um inteiro e < Ф(N) tal que GCD (e, Ф(N))=1 e calcula o inteiro
d tal que e.d ≡ 1 mod Ф(N)
A chave pública é (N, e) e d é a chave privada; p, q e Ф(N) não são mais
necessários. Na prática, devem ser destruídos.
Cifragem:
Para enviar uma mensagem cifrada M < N para Bob, Alice calcula o texto cifrado
C:
C ≡ Me mod N
Lembrando que N e e são a chave pública de Bob.
Decifragem:
Para decifrar C, Bob computa:
M ≡ Cd mod N
Lembrando que apenas Bob tem a chave de decifragem d.
Vamos analisar o processo de decifragem:
M ≡ Cd mod N = (Me)d mod N = Med mod N
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 80
ed ≡ 1 mod Ф(N) ⇒ ed ≡ 1 + k.Ф(N)
Logo:
M = M1 + k.Ф(N) mod N = M.Mk.Ф(N) mod N
Pelo Teorema de Lagrange:
MФ(N) ≡ 1 mod N
e
Mk.Ф(N) ≡ 1k mod N ≡ 1 mod N
Exemplo:
p = 7 e q = 13 ⇒ N = 7.13 = 91
Ф(N) = (7 – 1).(13 – 1) = 72
e = 5 ⇒ d = 29, onde
5.29 ≡ 1 mod Ф(N) ≡ 1 mod 72
Seja M = 3, a cifragem torna-se:
C ≡ Me mod N
C = 35 = 243 ≡ 61 mod 91 ⇒ C = 61
e a decifragem seria:
Cd = 6129 ≡ 3 mod 91 = M
Geralmente, os primos p e q são números com cerca de 50 dígitos. Dessa
forma, N, formado pelo produto dos dois, tem cerca de 100 dígitos. Um
criptanalista pode pegar a mensagem C e decifrá-la, algoritmicamente, de forma
simples. O método de decifrar é conhecido e ele tem acesso à chave pública e a
N. Calculado o valor de Ф(N), é relativamente simples encontrar o valor de d. O
problema está no fato de N ser formado por dois fatores primos com cerca de 50
dígitos e essa fatoração ser necessária para calcular Ф(N). Assim, a dificuldade
do RSA depende do problema de fatoração de inteiros
Um RSA construído com dois primos seguros é mais difícil de ser
quebrado. Em 2000, uma coalizão de 9000 workstations, trabalhando em
paralelo conseguiu quebrar um RSA de 512 bits em 4 meses.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 81
PARTE III - Relações e Estruturas Algébricas
1. Relações
(Capítulo 3 do Ross)
1.1 Introdução
Dados conjuntos S e T, uma Relação de S para T é um subconjunto R de SxT,
i.e., um conjunto de pares ordenados (s, t). Dizemos que s é R-relacionada a t
ou que s é relacionada a t por R, no caso, (s, t) ∈ R. Não há garantia que (t, s) ∈
R também !
Se f: S→ T (f uma função), identificamos f com o conjunto:
Rf = {(x, y) ∈ SxT: y = f(x)}
que é uma relação de S para T. Nem todas as relações são funções. Uma
função de S para T é um tipo especial de relação de S para T tal que: para cada
x ∈ S existe exatamente um y ∈ T com (x, y) ∈ R. Assim, o conceito de relação é
muito mais amplo que o de função. Não é preciso, por exemplo, haver um
mapeamento matemático em uma relação como acontece com funções.
Relações são muito comuns em diversas áreas da computação como Banco de
Dados.
Exemplos:
1. Todo conjunto S tem, pelo menos, a relação básica de “igualdade”:
E = {(x, x): x ∈ S}
Dois elementos em S satisfazem esta relação, se e somente se, eles são
idênticos. Ou seja, (x, y) ∈ E, sse x = y.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 82
2. Para o conjunto ú, a relação de desigualdade “≤” pode ser vista como um
subconjunto D de úxú: D = {(x, y): x ≤ y}. Como (x, y) ∈ D, sse x ≤ y,
normalmente, escrevemos a relação como ≤. Essa relação tem algumas
propriedades que são particularmente importantes:
(Reflexividade) x ≤ x, ∀x ∈ ú.
(Anti-Simetria) x ≤ y e y ≤ x, implica que x = y, ∀x,y ∈ ú.
(Transitividade) x ≤ y e y ≤ z, implica que x ≤ z, ∀x, y, z ∈ ú.
Essas propriedades podem ser escritas também como:
(R) (x, x) ∈ R, ∀x ∈ ú.
(AS) (x, y) ∈ R e (y, x) ∈ R, implica que x = y, ∀x, y ∈ ú.
(T) (x, y) ∈ R e (y, z) ∈ R, implicam que (x, z) ∈ R, ∀x, y, z ∈ ú.
3. A relação de desigualdade estrita “<” em ú também é uma relação e
corresponde ao conjunto R = {(x, y): x < y}. Essa relação tem as seguintes
propriedades:
(AR) x < x, nunca ocorre, ∀x ∈ ú.
(T) x < y e y < z, implica que x < z, ∀x, y, z ∈ ú.
Essas podem ser escritas como:
(AR) (x, x) ∉ R, ∀x ∈ ú.
(T) (x, y) ∈ R e (y, z) ∈ R, implica que (x, z) ∈ R, ∀x, y, z ∈ ú.
4. Quanto à relação de congruência “≡”, no conjunto dos inteiros:
(R) m ≡ m mod p, ∀m, p ∈ Z.
(S) m ≡ n mod p implica que n ≡ m mod p, ∀m, n, p ∈ Z.
(T) m ≡ n mod p e n ≡ r mod p implica que m ≡ r mod p, ∀m, n, p, r ∈ Z.
que tornam-se
(R) (m, m), ∀m ∈ Z.
(S) (m, n) ∈ R implica que (n, m) ∈ R, ∀m, n ∈ Z.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 83
(T) (m, n) ∈ R e (n, r) ∈ R, implica que (m, r) ∈ R, ∀m, n, r ∈ Z.
Considere uma relação R de S em T. Isto é, R ⊆ SxT. A relação inversa R← é a
relação inversa de T em S definida por:
(t, s) ∈ R←, sse (s, t) ∈ R.
Ou seja, absolutamente diferente do que acontece com funções, nas relações a
inversão de uma relação dá-se apenas pela inversão dos pares que a formam.
Não há qualquer necessidade de ser mantida alguma referência à relação
original.
Exemplo:
1. A respeito das relações inversas, se, por exemplo, tivermos:
R = {(m, n) ∈ SxS: m – n > 0}
então a relação inversa é dada por:
R← = {(n, m) ∈ SxS: n – m < 0}
Assim, por exemplo, se o par (3, 2) fazia parte de R, o par (2, 3) faz parte de R←.
Observe que não é apenas o complementar da desigualdade “>” que define o
inverso. Nesse caso, o complementar seria “≤”, mas aqui a igualdade não é
permitida já que os pares (x, x) não pertencem à relação original.
Representação Gráfica de Relações
É possível representar os pares que fazem parte de uma relação graficamente.
Vamos analisar essa possibilidade através do exemplo a seguir.
Exemplo:
1. Considere a relação R1 no conjunto {0, 1, 2, 3,} definida por ≤. Assim, o par
(m, n) ∈ R1, sse m ≤ n. Os seguintes pares fazem parte da relação:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 84
(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)
Graficamente, isso pode ser representado da seguinte forma:
Todos os elementos do conjunto são dispostos e as setas indicam a disposição
dos pares. Se existe um par (2, 3) na relação, haverá uma seta direcionada de 2
para 3. Para os pares do tipo (x, x), é criado um chamado laço do elemento para
ele mesmo. Esses laços podem ser direcionados ou não já que, nesse caso, a
direção não importa.
2. Seja R2 a relação em {1, 2, 3, 4, 5} definida por m R2 n, sse m – n é par:
3. A relação inversa R1← é obtida invertendo as setas de R1 sem alterar os laços.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 85
4. A representação gráfica de R2 também é conseguida como a de R2←,
observando que a figura de R2← é igual à de R2, caracterizando uma relação
simétrica.
1.2 Digrafos e Grafos
Um Digrafo G consiste de dois conjuntos: o conjunto não-vazio V(G) de vértices
de G e o conjunto E(G) de arestas de G, junto com uma relação γ (gama) de
E(G) para V(G)xV(G) que diz para onde as arestas vão.
Se e é uma aresta de G e γ(e) = (p, q), então dizemos que e vai de p para q e
chamamos p de vértice inicial e q de vértice terminal de e.
Exemplos:
1. Considere a tabela abaixo e sua representação em digrafos:
e
γ(e)
a
(w,z)
b
(w, x)
c
(x, z)
d
(z, z)
e
(z, x)
f
(z, y)
g
(y, w)
h
(y, x)
Em um grafo, um caminho é uma seqüência de arestas tal que o vértice terminal
de uma aresta é o vértice inicial da próxima (arestas adjacentes). Dizemos que
e1, e2, e3,..., en é um caminho de tamanho n do vértice x1 a xn+1. O caminho é
dito fechado se x1 = xn+1.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 86
2. Na figura anterior, f g a e é um caminho de tamanho 4 de z para x. O caminho
pode também ser definido por uma seqüência de arestas. z y w z x define o
caminho anterior também. f a não define um caminho; f g a é um caminho
fechado.
Um caminho fechado, onde cada vértice aparece apenas uma vez (menos o
primeiro e o último), é chamado de ciclo (ou circuito ou laço). Um digrafo sem
ciclos é chamado acíclico.
Dado um digrafo G e vértices v e w em V(G), v é adjacente a w, se existe uma
aresta em E(G) de v a w.
Um digrafo sem as setas (ou seja, não direcionado) é chamado um grafo. Os
mesmos conceitos de aresta, vértices, caminhos, comprimento de caminhos,
ciclos, etc, são válidos.
Definimos a relação de alcançabilidade R em V(G) por (v, w) ∈ R, se existe um
caminho em G de v para w.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 87
2. Mais sobre Relações
(Capítulo 10 do Ross)
2.1 Conjuntos Parcialmente Ordenados (Partially Ordered Sets –
Posets)
Conjuntos cujos membros podem ser comparados entre si de alguma forma.
Tipicamente, pensamos em um elemento sendo menor do que o outro, em
algum tipo de ordem. A ordem mais conhecida é ≤ em ú que tem as seguintes
propriedades:
(R) x ≤ x, ∀x ∈ ú
(Reflexividade)
(AS) x ≤ y e y ≤ x ⇒ x = y, ∀x, y ∈ ú
(Anti-Simetria)
(T) x ≤ y e y ≤ z ⇒ x ≤ z, ∀x, y, z ∈ ú
(Transitividade)
(L) Dados x e y, tanto x ≤ y ou y ≤ x, ou ambos se x = y
(Linearidade)
A propriedade L garante que dois elementos quaisquer são comparáveis. Uma
relação ≤ em um conjunto que satisfaça as propriedades acima é chamada
ordem total ou ordem linear. O termo L sugere que os elementos podem ser
listados em uma linha.
Qualquer conjunto S cujos elementos podem ser listados pode ser dado uma
ordem, satisfazendo as propriedades (R), (AS), (T) e (L), concordando que um
membro s precede um outro membro t, escrevendo s ≤ t, se s aparece na lista
antes de t ou se s = t.
Em alguns conjuntos, temos elementos não-comparáveis, logo, a propriedade L
não pode ser aplicada. Tais conjuntos são ditos ordenados e a especificação de
como seus membros se comparam entre si é chamada relação de ordem no
conjunto.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 88
Exemplo:
1. Se comparamos os fabricantes de carros, podemos ter um fabricante A
melhor que um Fabricante B, ou casos onde um fabricante C é melhor que um D
em alguns aspectos, mas nada podendo ser dito sobre o todo.
2. Podemos comparar dois números no conjunto {1, 2, 3,...., 73} se um é divisor
do outro. Então 6 e 72 são comparáveis, assim como 3 e 6. Mas 6 e 8 não são já
que 6 não divide 8 e nem vice-versa.
Conjuntos com relações de comparações que permitam a possibilidade de
elementos não-comparáveis são ditos parcialmente ordenados. Uma relação R
em um conjunto S é um subconjunto de SxS. Uma Ordem Parcial em um
conjunto S é uma relação R que é reflexiva, anti-simétrica e transitiva. Essas
condições significam que, se escrevermos x ≤ y como uma notação alternativa
para (x, y) ∈ R, então uma ordem parcial satisfaz:
(R) s ≤ s, ∀s em S;
(AS) s ≤ t e t ≤ s implica em s = t;
(T) s ≤ t e t ≤ u implica em s ≤ u.
Se ≤ é uma ordem parcial em S, o par (S, ≤) é chamado um conjunto
parcialmente ordenado ou poset. Entenda ≤ como um operador genérico de
comparação; ele não é o operador de desigualdade “menor que”.
O inverso de uma ordem parcial ≤ é denotado por ≥. Assim, x ≥ y é o mesmo que
y ≤ x. A relação inversa também é uma ordem parcial. Se virmos ≤ em S como
um subconjunto R de SxS, então ≥ corresponde à relação inversa R←.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 89
Dada uma ordem parcial ≤ em um conjunto S, definimos outra relação < em S
por:
x < y, se e somente se, x ≤ y e x ≠ y.
Exemplo:
Se ≤ é o conjunto inclusão ⊆, então A < B significa um subconjunto de B, i.e., A
⊂ B. A relação < é AR e T:
(AR) s < s é falso para todo s em S
(T) se s < t e t < u, então s < u.
Uma relação que é AR e T é chamada de uma Quasi-Ordem. Cada ordem
parcial em S tem uma quasi-ordem correspondente e vice-versa. Assim, se < é
uma quasi-ordem, então a relação ≤ definida por:
x ≤ y, se e somente se, x < y e x = y
é uma ordem parcial em S. A escolha de uma ordem parcial ou de sua quasiordem associada para descrever comparações entre membros de um Poset
depende do problema em particular.
É possível desenhar um diagrama que mostre a relação de ordem de um Poset
finito. Dada uma ordem parcial ≤ em S, dizemos que o elemento t cobre o
elemento s, no caso s ≤ t, e não existe nenhum elemento u em S tal que s < u <
t. Um diagrama de Hasse13 (lê-se Hah-suh) de um Poset (S, ≤) é uma figura de
um digrafo cujos vértices são membros de S e no qual existe uma aresta de t
para s, se e somente se, t cobre s. Diagramas de Hasse são, geralmente,
desenhados como árvores com a raiz embaixo e as folhas em cima.
Para criação de um digrama de Hasse para um Poset, as seguintes regras
devem ser seguidas:
13
Helmut Hasse (1898-1079): matemático alemão com grandes contribuições para a Teoria dos
Números
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 90
1- Gera o digrafo
2- Elimina os laços dos vértices:
Como é um Poset, ele já é naturalmente reflexivo, logo, os laços são
redundantes.
3- Se (a, b) e (b, c) estão em ordem parcial, remova a aresta (a, c), pois esta
também deve estar:
Novamente, como é um Poset, obrigatoriamente, ele deve ser Transitivo.
4- Re-arranje cada aresta de forma que o vértice inicial fique abaixo do terminal:
Gera a estrutura de árvore.
5- Elimine as setas direcionais; elas são desnecessárias já que sempre estariam
apontando de baixo para cima.
Exemplo:
1. Considere o conjunto S = {1, 2, 3, 4, 5, 6} e a relação R = {(m, n) ∈ RxR: m |
n} (ou seja, m divide n)
Poset (S, |)
Pares que satisfazem a relação:
(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5,
5), (6, 6)
Digrafo:
Seguindo passo-a-passo as regras definidas, geramos o seguinte diagrama de
Hasse:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 91
No entanto, podemos ver pelo diagrama que 1|6 porque, pela transitividade, 1|2
e 2|6. De forma similar, podemos ver que 1|4, pois 1|2 e 2|4.
Teorema: Todo Poset finito tem um diagrama de Hasse.
No entanto, alguns Posets infinitos também possuem diagrama de Hasse. Um
diagrama de Hasse de Z com ordem ≤ é uma linha vertical com pontos
espaçados ao longo dela representando os números. Por outro lado, nenhum
número real cobre qualquer outro número na ordem ≤. Assim, (ú, ≤) não tem
diagrama de Hasse.
Se (P, ≤) é um Poset, diz-se que um elemento x de P é o elemento maximal no
caso de não existir nenhum elemento y em P com x < y. Chamamos x de
elemento minimal, se não existe nenhum y em P com y < x. Pode existir mais de
um elemento maximal ou minimal.
Exemplo:
Considere o diagrama de Hasse abaixo, representando um Poset:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 92
Nessa relação, temos:
Elementos Maximal: d, e, f
Elemento Minimal: a
Um subconjunto S de um Poset P herda a ordem parcial de P e é ele mesmo um
Poset já que as leis (R), (AS) e (T) se aplicam a todos os membros de P.
Chamamos S um Subposet de P.
Exemplo:
Considere o conjunto S = {1, 2, 3, 4, 5, 6} e a relação R = {(m, n) ∈ RxR: m | n}
(ou seja, m divide n)
Poset P(S, |)
Os conjuntos a) {2, 3, 4, 5, 6} e b) {1, 2, 3, 6} são Subposets de P:
a)
b)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 93
Se S é um Subposet de um Poset (P, ≤), então S pode ter um membro M tal que
s ≤ M para todo s em S. Na figura b anterior, temos s ≤ 6 para todo s, enquanto
que não existe tal elemento na figura a anterior. Um elemento M com tal
propriedade é chamado o maior elemento de S ou o máximo de S denotado por
max(S). De forma similar, se S tem um elemento m tal que m ≤ s para todo s em
S, então m é chamado o menor elemento de S ou o mínimo de S,denotado por
min(S). Existe no máximo um único elemento máximo ou mínimo.
Se um Subposet S de um Poset (P, ≤) tem ou não um elemento máximo, devem
existir elementos x no conjunto P tal que s ≤ x para todo s em S. Um tal
elemento é chamado um limite superior para S em P. Se x é um limitte superior
para S em P e é tal que x ≤ y para todo limite superior y para S em P, então x é
chamado menor limite superior de S em P, e escrevemos x = lub(S) (Least
Upper Bound). Da mesma forma, um elemento z em P tal que z ≤ s, para todo s
em S é um limite inferior para S em P. Um menor limite z tal que w ≤ z para todo
menor limite w é chamado um Maior Limite Inferior de S em P, sendo denotado
por glb(S) (Greatest Lower Bound). Pela propriedade da anti-simetria, um
subconjunto de P não pode ter dois diferentes lub ou dois diferentes glb.
Exemplo:
1. No Poset (Z+*, |) onde, como usual, m | n, sse, m divide n, quem são o lub {m,
n} e glb {m, n} ?
lub {m, n} = LCM (m, n)
glb {m, n} = GCD (m, n)
Um limite superior para {m, n} é um inteiro k em Z+* tal que m divide k e n divide
k, i.e., um múltiplo comum de m e n. O menor limite superior lub {m, n} é o
mínimo múltiplo comum de m e n. Da mesma forma, o maior limite inferior glb
{m, n} é o maior divisor comum de m e n, o maior inteiro positivo que divide tanto
m quanto n.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 94
2. Considere o Poset ({1, 2, 3, 4, 5, 6}, |)
O subconjunto {2, 3} tem lub {2, 3} = 6 e glb {2, 3} = 1
O subconjunto {4, 6} não tem lub e tem glb {4, 6} = 2.
O subconjunto {3, 6} tem lub {3, 6} = 6 e tem glb {3, 6} = 3
3. Considere o Poset P mostrado na figura abaixo:
O subconjunto {b, c} tem d, e, g e h como limites superiores em P, e h é um
limite superior para {d, f}. O subconjunto {b, c} não tem menor limite superior em
P, mas h = lub{d, f}. Os elementos a e c são limites inferiores para {d, e, f}. No
entanto a = glb{b, d, e, f}.
A maioria dos posets que têm aplicações práticas tem a propriedade que cada
subconjunto com dois elementos tem tanto um menor limite superior quanto um
maior limite inferior. Um reticulado (lattice) é um poset no qual existe lub{x, y} e
glb{x, y} para todo x e y. Em um reticulado (P, ≤), as equações
x ∨ y = lub{x, y}
e
x ∧ y = glb{x, y}
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 95
definem operações binárias ∨ e ∧ em P. Observe que isso está de acordo com a
Álgebra Booleana já que glb{x, y} = x ∧ y = x, sse, x ≤ y, que é verdade , sse
lub{x, y} = x ∨ y = y.
Exemplos:
1. O poset (P({a, b, c}, ⊆)) abaixo:
é um reticulado. Por instância:
lub ({a}, {c}) = {a} ∨ {c} = {a, c}
lub ({a, b}, {a, c}) = {a, b} ∨ {a, c} = {a, b, c}
glb ({a}, {c}) = {a} ∧ {c} = { }
glb ({a, b}, {b, c}) = {a, b} ∧ {b, c} = {b}
Em geral, para qualquer conjunto S, P(S, ⊆) é um reticulado com o lub(A, B) =
A∪B e glb(A, B) = A∩B.
2. O poset abaixo
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 96
não é um reticulado. Por exemplo, {a, b} e {a, c} não têm menor limite superior.
De fato, eles não têm qualquer limite superior.
2.2 Fechamento de Relações
Algumas vezes, é necessário criar novas relações a partir de outras já
existentes. Ou seja, podemos ter duas relações R1 e R2 em S, que são R, S e T,
e queremos encontrar uma relação equivalente, contendo as duas. O candidato
mais óbvio seria R1 ∪ R2.
Uma outra forma de representar uma relação R em um conjunto S é através da
chamada Matriz Booleana. Cria-se uma matriz nxn, onde n é o número de
elementos do conjunto S. Os membros dessa matriz são números binários
representando a existência de ligação entre elementos (1) ou não (0) –
elementos booleanos. As linhas da matriz indicam o ponto de partida da seta
direcional e as colunas representam o ponto de chegada.
Exemplo:
1. Considere o digrafo abaixo referente à relação R aplicada sobre o conjunto S
= {1, 2, 3, 4}.
Seja A a matriz Booleana:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 97
1 2 3 4
1 0 0 1 1
2 0 1 0 0
3 0 0 1 0
4 1 0 0 0
Como exemplo na matriz, o elemento A(1, 3) tem valor 1, indicando que o par (1,
3) faz parte da relação, ou seja, no digrafo, existe um caminho de 1 para 3. Da
mesma forma, o elemento A(2, 1) tem valor 0 porque o par (2, 1) não faz parte
da relação (não há caminho de 2 para 1 no digrafo).
Vamos chamar t(R) uma relação transitiva; r(R) reflexiva e s(R) simétrica. Seja R
a relação apresentada no exemplo anterior. Analisando o digrafo, observamos
que a relação R não é reflexiva já que nem 1 e nem 4 estão relacionados entre
si. Na matriz booleana A, isso está indicado pelo 0 nas posições A(1, 1) e A(4,
4). Assim, se a relação fosse reflexiva, esses elementos teriam valor 1. Ou seja,
para uma relação reflexiva, toda a diagonal principal da matriz booleana tem
valor 1.
Seja r(R) um operador que, ao ser aplicado a uma relação R, torna-a reflexiva. A
aplicação desse operador acrescenta novos pares à relação de forma a torná-la
aquilo que se busca. Isso independe do comportamento da relação antes da
aplicação do operador MESMO quando a relação é gerada sobre uma função.
Por exemplo, suponha que é aplicada ao conjunto S = {1, 2, 3} a relação R =
{(m, n) ∈ R | m < n}. Obviamente, os pares (x, x), x ∈ S, não fazem parte de R.
No entanto, ao criarmos a relação R1 = r(R), os pares (x, x) são inseridos a fim
de tornar a relação R reflexiva.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 98
2. Vamos aplicar o operador de reflexividade na relação R definida no exemplo
anterior, utilizando seu mesmo conjunto S. Assim, a relação R1 gerada por r(R),
cria o digrafo e a matriz booleana:
1 2 3 4
1 1 0 1 1
2 0 1 0 0
3 0 0 1 0
4 1 0 0 1
Foram incluídos os pares (1, 1) e (4, 4) que correspondem, no digrafo, aos laços
nos elementos 1 e 4 e, na matriz booleana, os elementos (1, 1) e (4, 4) tornamse 1.
De forma similar, os operadores s(R) e t(R) aplicam as propriedades de Simetria
e Transitividade à relação R. As mesmas considerações anteriores são válidas
quanto à aplicação do operador à relação.
Exemplo:
1. Considerando a mesma relação R anterior (não R1 que é gerado por r(R) !!!),
podemos gerar R2 = s(R):
1 2 3 4
1 0 0 1 1
2 0 1 0 0
3 1 0 1 0
4 1 0 0 0
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 99
Nesse caso, foi acrescentado o par (3, 1) que indica um caminho de 3 para 1 no
digrafo e a atribuição do valor 1 à posição (3, 1) da matriz booleana. Em termos
de matriz, a simetria pode ser facilmente observada já que a matriz booleana
gerada é uma matriz simétrica (A = AT)
Vamos agora aplicar à relação R original o operador de transitividade, criando a
relação R3 = t(R). O digrafo e a matriz booleana de R3 são apresentados abaixo:
1 2 3 4
1 1 0 1 1
2 0 1 0 0
3 0 0 1 0
4 1 0 1 1
Observe que a transitividade é um processo mais complicado de ser avaliado.
No momento, não vamos nos deter em como saber se a transitividade foi
alcançada ou não. É preciso definir os caminhos que já existem através do
digrafo e que tornam necessário a criação de outros. Assim, na relação R
original, havia um caminho de 4 para 1 e de 1 para 3, logo deve haver um
caminho de 4 para 3; i.e., deve ser acrescentado o par (4, 3). Da mesma forma,
por causa da transitividade, observe que temos um caminho de 4 para 1 e de 1
para 4; logo, o par (4, 4) teve que ser acrescentado. O mesmo vale para o par
(1, 1) derivado do caminho de 1 para 4 e de 4 para 1.
Vale salientar que a relação R3 final tornou-se reflexiva, mas isso não é uma
condição necessária para a transitividade.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 100
Proposição: Seja R uma relação. Então R = r(R), sse R é reflexiva. R = s(R),
sse R é simétrica e R = t(R), sse R é transitiva. Mais ainda:
r(r(R)) = r(R), s(s(R)) = s(R), t(t(R)) = t(R)
Podemos pensar em r, s e t como funções que mapeiam relações em relações; s
mapeia R em s(R). Funções assim são chamadas operadores. Segundo a
proposição, a repetição da aplicação dos operadores não gera novas relações
(r(r(R))) = r(R) = r(r(r....r(R)...)). Os operadores com essas propriedades são
chamados de operadores de fechamento.
A combinação de dois ou mais operadores diferentes pode levar a novas
relações.
Exemplo:
1. Para a relação R anterior:
1 2 3 4
1 0 0 1 1
2 0 1 0 0
3 0 0 1 0
4 1 0 0 0
temos
r(R) =
s(R) =
1 2 3 4
1 2 3 4
1 1 0 1 1
1 0 0 1 1
2 0 1 0 0
2 0 1 0 0
3 0 0 1 0
3 1 0 1 0
4 1 0 0 1
4 1 0 0 0
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 101
e sr(R) = s(r(R)) =
1 2 3 4
1 1 0 1 1
2 0 1 0 0
3 1 0 1 0
4 1 0 0 1
Lema:
a. Se R é reflexiva, s(R) e t(R) também são.
b. Se R é simétrica, r(R) e t(R) também são. Ou seja, t(s(R)) é transitiva.
c. Se R é transitiva, r(R) também é. Nada pode ser dito sobre s(R).
Teorema: Para qualquer relação R em um conjunto S, tsr(R) é a menor relação
de equivalência14 contendo R. Diz-se que é a menor relação porque uma matriz
booleana composta por 1’s em todas as posições também é s, r e t.
Exemplo: Para a relação anterior temos, rs(R) = sr(R) =
1 2 3 4
1 1 0 1 1
2 0 1 0 0
3 1 0 1 0
4 1 0 0 1
O fechamento transitivo de sr(R) = tsr(R) = t(s(r(R))) =
1 2 3 4
1 1 0 1 1
2 0 1 0 0
3 1 0 1 1
4 1 0 1 1
14
Relação de equivalência: uma relação que é s, r e t ao mesmo tempo.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 102
Seja R1 uma relação em um conjunto finito S com matriz booleana A. Então:
(R) R1 é reflexiva, sse toda a diagonal principal de A é igual a 1.
(AR) R1 é anti-reflexiva, sse toda a diagonal principal de A é igual a 0.
(S) R1 é simétrica se A = AT
(AS) R1 é anti-simétrica, sse A∧AT ≤ I, onde I e a matriz identidade
(T) R1 é transitiva, sse A*A ≤ A
Obs: Para matrizes booleana mxn A1 e A2, dizemos que A1 ≤ A2, se toda entrada
de A1 for menor ou igual à entrada correspondente de A2, i.e., A1[i, j] ≤ A2[i, j],
para todo 1 ≤ i ≤ m e 1 ≤ j ≤ n.
Exemplo: R é uma relação em {1, 2, 3} com matriz booleana:
A=
1 1 1
0 1 0
0 0 1
R é reflexiva, pois toda a diagonal principal de A é igual a 1.
R não é simétrica, pois A ≠ AT
R é transitiva, pois A*A ≤ A:
1 1 1
0 1 0
1 1 1
*
0 0 1
Assim,
A = r(A) = t(A) = tr(A) = rt(A)
s(R) =
1 1 1
1 1 0
1 0 1
0 1 0
0 0 1
1 1 1
≤
0 1 0
0 0 1
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 103
st(R) = s(t(R)) = str(R) = srt(R) = s(R)
1 1 1
1 1 0
1 0 1
Mas, ts(R) =
1 1 1
1 1 1
1 1 1
= tsr(R) = trs(R).
Mas, st(R) = str(R) = str(R) = s(R) ≠ ts(R) = tsr(R) = trs(R).
Logo, tsr(R) pode ser diferente de str(R). A ordem da aplicação dos operadores
pode gerar relações diferentes. Isso vale para os casos onde o operador de
transitividade está envolvido.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 104
Exercícios
1. As figuras abaixo mostram os diagramas de Hasse de três Posets.
A
B
C
a) Quais são os membros maximais dos Posets ?
b) Quais desses Posets têm elementos minimais ?
c) Quais desses Posets têm elemento mínimo (min(S)) ?
d) Que elementos cobrem o elemento e em A?
e) Encontre cada um dos valores a seguir, se existir:
lub{d,c}, lub {w, y, v}, lub {p, m}, glb {a, g}
2. Seja S um conjunto de sub-rotinas de um programa de computador (como
uma função em C). Para A e B em S escreva A < B se A tiver que ser
completada antes que B possa ser completada. Algum tipo de restrição deve ser
colocada na chamada a sub-rotina no programa principal para tornar < uma
quasi-ordem?
3. Defina as relações <, ≤ e * no plano Reais x Reais por:
(x,y) < (z,w) se x 2 + y 2 < z 2 + w 2
(x,y) ≤ (z,w) se (x,y) < (z,w) ou (x,y) = (z,w)
(x,y) * (z,w) se x 2 + y 2 ≤ z 2 + w 2
a) Quais dessas relações são ordens parciais ? Explique.
b) Quais são quasi-ordens ? Explique.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 105
4. Dadas as seguintes matrizes booleanas, correspondendo a relações R em {1,
2, 3}, desenhe diagramas de Hasse, representando cada uma.
5. Seja S = {1, 2, 3} e R = {(2,1), (2,3), (3,2)} uma relação em S.
a) Desenhe o Diagrama de Hasse de R e R².
b) R é Transitiva ?
c) R² é Tansitiva ?
6. Dê a matriz booleana para as seguintes relações em S = {0, 1, 2, 3}.
a) (m,n) ∈ R1 se m + n = 3
b) (m,n) ∈ R2 se m ≡ n (mod 2)
c) (m,n) ∈ R3 se m ≤ n
d) (m,n) ∈ R4 se m + n ≤ 4
e) (m,n) ∈ R5 se Max{m, n} = 3, onde Max{m, n} é o valor máximo entre m e n
7. Para cada relação no exercício anterior, especifique quais as propriedades
(R), (AR), (S), (AS) e (T) são satisfeitas em cada uma.
8. Considere a relação R em {1, 2, 3} com matriz booleana
.
Encontre as matrizes booleanas para :
a) r(R)
b) s(R)
c) rs(R)
d) sr(R)
e) tsr(R)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 106
3. Grupos
(Final do Burton)
3.1 Introdução
Definição: Um grupo <G, • > é uma estrutura algébrica onde G é um conjunto e
• é uma composição nele, tal que as quatro propriedades a seguir sejam
satisfeitas simultaneamente:
(i) (fechamento) g•h está em G, ∀g, h ∈ G
(ii) (associatividade) g•(h•k) = (g•h)•k, ∀g, h, k ∈ G
(iii) (identidade) Existe um elemento e em G tal que e•g = g•e = g, ∀g ∈ G
(iv) (inverso) Para todo g ∈ G, existe um elemento inverso, g-1, pertencente a G,
tal que g•g-1 = g-1•g = e
Diversas são as aplicações da teoria dos grupos. Dentre elas, destaca-se
novamente a criptografia.
Em geral, o par <G, •> é referido como o grupo G para diferenciar do conjunto G.
Definição: Um grupo Abeliano, ou grupo comutativo, é um grupo para o qual o
axioma da comutatividade é válido. Ou seja, g•h = h•g, para todo g e h
pertencentes ao conjunto G.
Definição: A cardinalidade (ou ordem) de um grupo
G,
denotada por |G|, é o
número de elementos no conjunto G.
Exemplos: São grupos:
a) <Q – {0}, *>
(Multiplicação nos racionais menos o zero)
b) <Z, +>
(Adição de inteiros)
c) <ú - {0}, *>
(Multiplicação de reais menos o zero)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
d) <ú, +>
(Adição de reais)
e) <Zn, +n>
(Adição de inteiros módulo n)
Página 107
Observe que nas letras a e c houve a necessidade de exclusão do zero. Se
incluíssemos esse elemento, sob a operação de multiplicação, qual seria seu
inverso? Notadamente, com o operador de composição sendo a operação de
multiplicação, o elemento identidade tem valor 1. É esse elemento que
multiplicado por qualquer outro elemento do conjunto dos reais, gera o próprio
elemento. No caso, se o zero fizer parte do grupo, qual seria o elemento inverso
que multiplicado pelo zero resultasse no elemento identidade 1? Ou seja, quem
é x tal que x*0 = 1? Isso não é possível nos reais... Logo, está justificada a
exclusão do zero para termos um grupo válido de acordo com as propriedades.
Sob a operação de adição, os grupos têm o zero como elemento identidade.
Lema: A identidade de um grupo é única.
Prova:
Vamos supor que um grupo possa ter duas identidades: e1 e e2. Assim:
g•e1 = g = g•e2
Se compusermos pela esquerda ambos os lados com o inverso de g:
g-1•g•e1 = g-1•g•e2
e1•e1 = e2•e2
e1 = e2
Logo, se considerarmos que existem duas identidades, elas devem ser iguais.
Lema: Todo elemento de um grupo tem um único inverso.
Prova:
Vamos supor que um elemento do grupo tenha dois inversos. Ou seja, vamos
supor que h e k são inversos de g. Assim:
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 108
g•h = e = g•k
Novamente, vamos efetuar uma composição pela esquerda de ambos os lados
com o inverso de g:
g-1•g•h = g-1•g•k
e•h = e•k
h=k
Logo, se considerarmos que existem dois inversos para um elemento, eles
devem ser iguais.
Lema: Para todo elemento a e b de um grupo <G, •>, temos (a•b)-1 = b-1•a-1.
Prova:
Note que
(b-1•a-1)•(a•b) = b-1•(a-1•a)•b = b-1•b = e
Da mesma forma
(a•b)•(b-1•a-1) = a•(b•b-1)•a-1 = a•a-1 = e
Assim, (b-1•a-1) é o inverso de a•b e é único como já provado.
Lema: Para qualquer elemento a e b de um grupo <G, •>, a equação a•x = b
tem uma solução única x em G.
Prova:
Efetuando uma composição pela esquerda dos dois lados da equação pelo
inverso de a e usando os axiomas dos grupos obtemos:
a-1•(a•x) = a-1•b
a-1•a•x = a-1•b
e•x = a-1•b
x = a-1•b
Mostrando que a equação tem solução x para todo a e b.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 109
Representação de grupos através de Tabelas de Composição
Uma forma simples de representar completamente um grupo é através das
chamadas Tabelas de Composição. Nelas, todos os elementos do conjunto G
são dispostos assim como o resultado de suas composições. As tabelas de
composição criam uma estrutura matricial onde as células apresentam o
resultado da composição da linha pela coluna.
Exemplos:
a) Grupo com apenas um elemento: Como todo grupo precisa conter o elemento
identidade, um grupo com um elemento contém apenas a identidade.
• e
e e
b) Grupo com dois elementos:
• e g
e e g
g g ?
A composição com o elemento identidade e gera o próprio elemento. O que
precisamos definir agora é qual o resultado da composição de g por ele mesmo.
Pela propriedade de fechamento temos duas possibilidades:
g•g = g
g•g = e
Vamos analisar a primeira delas: g•g = g. Como e•g = g, se g•g = g, teremos
uma situação com duas identidades diferentes. Isso provaria que g = e e
teríamos um grupo com um elemento apenas. Assim, g•g deve ser igual a e. A
tabela de composição para um grupo de ordem 2 fica:
• e g
e e g
g g e
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 110
c) Grupo de ordem 3:
• e h g
e e h g
h h ? ?
g g ? ?
Novamente, temos elementos não determinados na tabela. No caso, precisamos
definir:
h•h = ?
h•g = ?
g•h = ?
g•g = ?
Vamos tratar dos casos mais simples primeiro:
h•g = ?
Pela propriedade do fechamento, essa composição deve ser igual a h, g ou e.
Mas, se for igual a h ou g, teremos a identidade igual a g ou h, respectivamente.
Assim, h•g deve ser igual a e. O mesmo raciocínio vale para g•h o qual é igual a
e também. Dessa forma, temos:
h•h = ?
h•g = e
g•h = e
g•g = ?
Consideremos h•h. Tal composição pode ser igual a h, g ou e. Se h•h for igual a
h, teremos que e = h o que não é válido. Como definimos antes que h•g = e,
então, se h•h = e, teremos g = h (h teria dois inversos). Conclui-se que h•h = g.
De forma similar, pode-se concluir que g•g = h, gerando a tabela de
composição:
• e h g
e e h g
h h g e
g g e h
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 111
Exemplo:
Considere o grupo <Z2, +2>, ou seja, adição módulo 2 nos inteiros. A tabela de
composição é dada por:
+2 0 1
0
0 1
1
1 0
Que tem exatamente a mesma distribuição de elementos que nosso grupo
genérico com dois elementos apresentado na letra b do exemplo anterior.
Ficou claro a dificuldade em criar grupos. À medida que a ordem do grupo
cresce, cresce também a quantidade de dependências que surgem entre a
definição dos valores das composições. Uma forma, porém, de construir grupos
maiores é usar o conhecimento que temos de grupos menores.
Definição: Sejam G e H grupos com composições ° e *, respectivamente. O
Produto Direto de G e H, escrito GxH, é a estrutura <GxH, •>, onde • é uma
composição de GxH definida por:
<g1, h1>•<g2, h2> = <(g1°g2), (h1*h2)>
para todo g1 e g2 pertencentes a G e h1 e h2 pertencentes a H.
Teorema: O produto direto de grupos G e H é também um grupo.
Podemos agora construir, por exemplo, a tabela de composição para um grupo
de ordem 6 como o produto direto de grupos de ordem 2 e 3:
°
e2
g
e2 e2
g
g
e2
g
*
e3
h
k
e3 e3
h
k
h
h
k
e3
k
k
e3
h
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 112
•
e2, e3
e2, h
e2, k
g, e3
g, h
g, k
e2, e3
e2, e3
e2, h
e2, k
g, e3
g, h
g, k
e2, h
e2, h
e2, k
e2, e3
g, h
g, k
g, e3
e2, k
e2, k
e2, e3
e2, h
g, k
g, e3
g, h
g, e3
g, e3
g, h
g, k
e2, e3
e2, h
e2, k
g, h
g, h
g, k
g, e3
e2, h
e2, k
e2, e3
g, k
g, k
g, e3
g, h
e2, k
e2, e3
e2, h
Definição: Um subgrupo de um grupo G é um subconjunto de elementos do
conjunto G que forma um grupo sob a operação de composição do grupo G.
Exemplo:
Na tabela de composição do grupo de ordem 6 anterior, os conjuntos {<e2, e3>,
<e2, k>, <e2, h>} e {<e2, e3>, <g, e3>} formam subgrupos de ordem 3 e 2,
respectivamente.
Teorema: Seja H um subgrupo de G. Então a identidade de H é a mesma de G.
Mais ainda, os inversos dos elementos de H são os mesmos desses elementos
quando em G.
Prova:
Sejam eg e eh as identidades em G e em seu subgrupo H, respectivamente.
Como eh é identidade, eh•h = h• eh = h, para todo h pertencente a H. Como eg é
uma identidade em G, eg•h = h•eg = h. Combinando, temos que eg = eh.
Consequentemente, para todo h em H, seu inverso em H é h-1 (o mesmo inverso
em G) porque eh = h•h-1 = h-1•h = eg.
Não é tão simples encontrar subgrupos de um grupo. Todo grupo tem, pelo
menos, dois subgrupos: um de ordem 1 com o elemento identidade e outro que
é o próprio grupo.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 113
Definição: A ordem de um elemento g do grupo é o menor inteiro r tal que gr =
e.
A notação com potência faz uma analogia à matemática. Assim, por exemplo, g2
= g•g, apenas. Não há necessidade da operação de composição ser produto.
Exemplo:
Em um grupo de ordem 2, g2 = g•g = e. Logo, a ordem do elemento g é 2.
OBS: A ordem de um elemento não é igual à cardinalidade do grupo. Observe
por exemplo <Z4, +4>, onde o elemento 2 tem ordem 2 e o elemento 1 tem
ordem 4.
3.2 Geradores e Grafos de Grupos
Definição: Um subconjunto de elementos de um grupo G é dito um conjunto de
geradores de G, se qualquer elemento de G puder ser expresso como uma
composição dos elementos desse subconjunto e seus inversos. Assim, se g e h
são geradores de um grupo <G, • >, então g•h•g-1 e g•h•g•h são composições
válidas no sentido usado na definição.
Exemplos:
1. Grupo de ordem 2
• e g
e e g
g g e
Possui dois elementos: g e e
{g} é um conjunto de elementos geradores, pois:
g•g = e
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 114
g•g•g = e•g = g
Logo, g consegue gerar todos os elementos do grupo.
2. Para um grupo de ordem 3:
• e h g
e e h g
h h g e
g g e h
Os elementos são: e, h, g
Conjuntos de geradores:
{h} é um conjunto gerador porque temos: {h, h•h = g, h•h•h = e}
{g} também é um conjunto gerador, pois: {g, g•g = h, g•g•g = e}
A partir dos geradores, é possível construir grafos que representam os grupos:
1- Coloque um nó no grafo para cada elemento do grupo G
2- Seja x um gerador do grupo. Então, para cada elemento y em G, desenhe
uma aresta de y para z, onde z = y•x
Exemplos:
1. Grupo de ordem 2: gerador {g}
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 115
2. Grupo de ordem 3: gerador {g}
As arestas do grafo representam operações do ponto de partida com o gerador
do grupo. No exemplo 2 anterior, temos uma aresta indo de h para e. Isso
significa que h•g = e. A operação de composição é representada pela aresta. Da
mesma forma, os caminhos representam todas as composições envolvidas.
Assim, se partirmos de h e chegarmos a g, passamos por g•h e e•g, i.e, g•h•e•g
= e•e•g = g.
3.3 Grupos de Permutações
Definição: Uma permutação de um conjunto X é uma bijeção de X em X. O grau
da permutação é a cardinalidade do conjunto no qual ele está definido (número
de permutações).
Exemplo:
Conjunto {0, 1}
Permutações possíveis:
que podem ser representadas como (0)(1) e (01).
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 116
Definição: Um grupo de permutação é um conjunto de permutações que forma
um grupo com respeito à função de composição.
Exemplo:
Vamos verificar se o grupo de permutações {(1)(2)(3), (123), (132)} forma um
grupo de permutação.
•
(1)(2)(3)
(123)
(132)
(1)(2)(3) (1)(2)(3)
(123)
(132)
(123)
(123)
(132)
(1)(2)(3)
(132)
(132)
(1)(2)(3)
(123)
Vamos analisar uma das operações para entender como as composições se
formam. Considere a composição (123)•(132). Observemos as permutações em
separado:
(123)
E a composição das duas:
(132)
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 117
O resultado da composição é definido pelo caminho existente. Assim, por
exemplo, no diagrama acima, existe um caminho de 1 para 2 e para 1
novamente. Assim, a permutação final é de 1 para 1: (1). Usando o mesmo
raciocínio para as outras operações, temos como resultado final da composição:
(1)(2)(3). Observe que esse é o elemento identidade do grupo.
3.4 Outra Estrutura: Anéis
Definição: Similar a um grupo, um Anel pode ser definido como um conjunto A
com duas operações binárias. Formalmente, um anel é uma tríplice (A, +, *) tal
que:
(i) Associatividade aditiva: ∀ a, b, c ∈ A, (a + b) + c = a + (b + c);
(ii) Comutatividade Aditiva: ∀ a, b ∈ A, a + b = b + a;
(iii) Identidade Aditiva: existe um elemento nulo pertencente a A, 0A, tal que 0A +
a = a + 0A = a;
(iv) Inverso Aditivo: ∀ a ∈ A, existe -a ∈ A, tal que a + (-a) = (-a) + a = 0A;
(v) Associatividade Multiplicativa: ∀ a, b, c ∈ A, (a*b)*c = a*(b*c);
(vi) Distributividade pela direita ou pela esquerda: ∀ a, b, c ∈ A, a*(b + c) = (a*b)
+ (a*c) e (b + c)*a = (b*a) + (c*a).
Um Anel é, assim, um grupo Abeliano sob a adição e um semi-grupo sob a
multiplicação.
Exemplo:
(Z, +, *) é um anel.
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello
Página 118
Exercícios
1. Construa a Tabela de Composição de um grupo não-abeliano de ordem 6.
Como sub-grupos ele tem o grupo de ordem 2 e o grupo de ordem 3.
2. Considere o conjunto de rotações do quadrado unitário (figura abaixo) nele
mesmo Seja I a rotação de 0º, e sejam R, D e L as rotações de 90º, 180º e 270º,
respectivamente. Mostre que esse conjunto de rotações forma um grupo, com a
operação do grupo sendo uma composição de rotações.
3. Verifique se o conjunto de permutações {(1)(2)(3), (12)(3), (132)} forma um
grupo sob a operação de composição de permutações. Justifique.