Algebra Aplicada À Computação

Prévia do material em texto

Á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 
 
 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: - 
 
 
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 
 
 
Obrigatória: x 
 
Eletiva : 
Período Indicado: 3º 
Á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, i e S 
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 Página 6 
 
A ∪ B A ∩ B A – B 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 Página 12 
parado := [sab, dom] + feriado; {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 Página 13 
Exemplos: 
 
 
 
 �
Á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] = ??? 
n = k + 1: k2 + 3 + (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: 
 a = q.b + r, 0 ≤ r < b 
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: 
 a = q.b + r, 0 ≤ r < |b| 
 
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) 
II) Para x = 3j + 2: x2 = (3j + 2)2 = 9j2 + 12j + 4 = 3(3j2 + 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ãoresolve 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) 
2
)1(...321 +=++++ nnn , para todo n >= 1 
b) 1 + 3 + 5 + ... + (2n – 1) = 2n , para todo n >= 1 
 
c) 1*2 + 2*3 + 3*4 + ... + n*(n+1) = 
3
)2)(1( ++ nnn , para todo n >= 1 
d) 
2
3333
2
)1(...321 ⎥⎦
⎤⎢⎣
⎡ +=++++ nnn , para todo n >= 1 
 
2. a) Se r ≠ 1, mostre que, para qualquer n inteiro positivo: 
1
)1(...
1
2
−
−=++++
+
r
raararara
n
n
 
 
b) Prove que, para qualquer inteiro positivo n, nn >2 . 
 
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 32 4864 == ), então ele deve ser da forma 7k ou 7k + 1. 
 
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello Página 23 
5. Prove que 13 2 −a nunca é um quadrado perfeito. 
 
6. Para n>=1, prove que 
6
)12)(1( ++ nnn é um inteiro. 
 
7. Mostre que o cubo de qualquer inteiro é da forma 7k ou 7k ± 1. 
 
8. Para n>=1, estabeleça que o inteiro )57( 2 +nn é da forma 6k. 
 
 � 
Á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| (I) 
Como b≠0 e, por definição, a≠0, então c≠0. 
c≠0 ⇒ |c| ≥ 1 
|c| ≥ 1 . |a| 
|a||c| ≥ |a| 
Á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 (Considera-se verdade....) 
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) 
 � 
 
Á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, 
masesse é 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 .k 
kd = kax + kby = GCD (ka, kb) 
k.GCD(a, b) = GCD(ka, kb) 
 � 
Exemplo: 
GCD (12, 30) = 6.GCD(2, 5) = 6.1 = 1 
 � 
Á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 e y = -4250 – 43t > 0 
 t > -100 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 y = -4250 – 43.(-99) 
 x = 5 e 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 y = -1 – 5t 
onde t é um inteiro qualquer. 
 � 
Á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 bca |2 
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) )75(|8 2 +n 
b) )12(|15 4 −n 
 
3. a) Prove que se a e b são ambos inteiros ímpares, então )2(|16 44 −+ ba 
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 inteiraspositivas 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, 2 é um racional, i.e., 2 =a/b, com GCD (a, b) = 1. 
Se 2 = a/b, então a = 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 : 
 2 (ar + bs) = 2 
 ( 2 a)r + ( 2 b)s = 2 
Como a = 2 b e b = a/ 2 : 
 2br + as = 2 
Como b, r, a e s são todos inteiros, temos que 2 é um inteiro o que é um 
absurdo. Logo, 2 é um irracional. 
 � 
 
Á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 Crivo = peneira 
6 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 700computadores 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 13 −n é 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 22 +p é composto. 
b) Dado que p é primo e que nap | , prove que nn ap | . 
 
4. Prove: 
a) Todo inteiro da forma 44 +n , 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 p é irracional para qualquer primo p. 
 
10 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( 22 ba , ),gcd( 2 ba e 
),gcd( 23 ba . 
 
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 3 5 7 11 13 17 19 23 29 
 31 37 41 43 47 53 59 61 67 71 
 73 79 83 89 97 101 103 107 109 113 
 127 131 137 139 149 151 157 163 167 173 
 179 181 191 193 197 199 211 223 227 229 
 233 239 241 251 257 263 269 271 277 281 
 283 293 307 311 313 317 331 337 347 349 
 353 359 367 373 379 383 389 397 401 409 
 419 421 431 433 439 443 449 457 461 463 
 467 479 487 491 499 503 509 521 523 541 
 547 557 563 569 571 577 587 593 599 601 
 607 613 617 619 631 641 643 647 653 659 
 661 673 677 683 691 701 709 719 727 733 
 739 743 751 757 761 769 773 787 797 809 
 811 821 823 827 829 839 853 857 859 863 
 877 881 883 887 907 911 919 929 937 941 
 947 953 967 971 977 983 991 997 1009 1013 
 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 
 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 
 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 
 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 
 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 
 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 
 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 
 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 
 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 
 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 
 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 
 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 
 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 
 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 
 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 
 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 
 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 
 2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 
 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 
 2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 
 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 
 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 
 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 
 2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 
 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 
 2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 
 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079 
 3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 
 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257 
 3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 
 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413 
 3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 
 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571 
Álgebra Aplicada à Computação - Prof. Carlos Alexandre Mello Página 46 
 3581 3583 3593 3607 3613 3617 3623 3631 3637 3643 
 3659 3671 3673 3677 3691 3697 3701 3709 3719 3727 
 3733 3739 3761 3767 3769 3779 3793 3797 3803 3821 
 3823 3833 3847 3851 3853 3863 3877 3881 3889 3907 
 3911 3917 3919 3923 3929 3931 3943 3947 3967 39894001 4003 4007 4013 4019 4021 4027 4049 4051 4057 
 4073 4079 4091 4093 4099 4111 4127 4129 4133 4139 
 4153 4157 4159 4177 4201 4211 4217 4219 4229 4231 
 4241 4243 4253 4259 4261 4271 4273 4283 4289 4297 
 4327 4337 4339 4349 4357 4363 4373 4391 4397 4409 
 4421 4423 4441 4447 4451 4457 4463 4481 4483 4493 
 4507 4513 4517 4519 4523 4547 4549 4561 4567 4583 
 4591 4597 4603 4621 4637 4639 4643 4649 4651 4657 
 4663 4673 4679 4691 4703 4721 4723 4729 4733 4751 
 4759 4783 4787 4789 4793 4799 4801 4813 4817 4831 
 4861 4871 4877 4889 4903 4909 4919 4931 4933 4937 
 4943 4951 4957 4967 4969 4973 4987 4993 4999 5003 
 5009 5011 5021 5023 5039 5051 5059 5077 5081 5087 
 5099 5101 5107 5113 5119 5147 5153 5167 5171 5179 
 5189 5197 5209 5227 5231 5233 5237 5261 5273 5279 
 5281 5297 5303 5309 5323 5333 5347 5351 5381 5387 
 5393 5399 5407 5413 5417 5419 5431 5437 5441 5443 
 5449 5471 5477 5479 5483 5501 5503 5507 5519 5521 
 5527 5531 5557 5563 5569 5573 5581 5591 5623 5639 
 5641 5647 5651 5653 5657 5659 5669 5683 5689 5693 
 5701 5711 5717 5737 5741 5743 5749 5779 5783 5791 
 5801 5807 5813 5821 5827 5839 5843 5849 5851 5857 
 5861 5867 5869 5879 5881 5897 5903 5923 5927 5939 
 5953 5981 5987 6007 6011 6029 6037 6043 6047 6053 
 6067 6073 6079 6089 6091 6101 6113 6121 6131 6133 
 6143 6151 6163 6173 6197 6199 6203 6211 6217 6221 
 6229 6247 6257 6263 6269 6271 6277 6287 6299 6301 
 6311 6317 6323 6329 6337 6343 6353 6359 6361 6367 
 6373 6379 6389 6397 6421 6427 6449 6451 6469 6473 
 6481 6491 6521 6529 6547 6551 6553 6563 6569 6571 
 6577 6581 6599 6607 6619 6637 6653 6659 6661 6673 
 6679 6689 6691 6701 6703 6709 6719 6733 6737 6761 
 6763 6779 6781 6791 6793 6803 6823 6827 6829 6833 
 6841 6857 6863 6869 6871 6883 6899 6907 6911 6917 
 6947 6949 6959 6961 6967 6971 6977 6983 6991 6997 
 7001 7013 7019 7027 7039 7043 7057 7069 7079 7103 
 7109 7121 7127 7129 7151 7159 7177 7187 7193 7207 
 7211 7213 7219 7229 7237 7243 7247 7253 7283 7297 
 7307 7309 7321 7331 7333 7349 7351 7369 7393 7411 
 7417 7433 7451 7457 7459 7477 7481 7487 7489 7499 
 7507 7517 7523 7529 7537 7541 7547 7549 7559 7561 
 7573 7577 7583 7589 7591 7603 7607 7621 7639 7643 
 7649 7669 7673 7681 7687 7691 7699 7703 7717 7723 
 7727 7741 7753 7757 7759 7789 7793 7817 7823 7829 
 7841 7853 7867 7873 7877 7879 7883 7901 7907 7919 
 
Cinco primos aleatórios de 200 dígitos 
• 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últiplosde 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 ∑
=
=
m
k
k
k xcxP
0
)( 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 ∑
=
=
m
k
k
k xaxP
0
)( 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. 
 
2. Encontre os dois últimos dígitos de 
999 . 
 
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 quandodividido 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: 
22
22
⎟⎠
⎞⎜⎝
⎛ −−⎟⎠
⎞⎜⎝
⎛ += baban 
 
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: 
22
2
1
2
1 ⎟⎠
⎞⎜⎝
⎛ −=−⎟⎠
⎞⎜⎝
⎛ + nnn 
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 
que pode ser entendido como: 
 812 ≡ 2.3 mod 2189 e 1552 ≡ 2.33 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: 
))((
))((
dada
bdacbdacn −+
−+= 
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)