Matemática para Ciência de Computadores
1 o Ano - LCC & ERSI
Luı́s Antunes
[email protected]
DCC-FCUP
Luis Antunes DCC-FCUP
Complexidade 2002/03
1
Inteiros e divisão
Definição: Se a e b são inteiros com a 6= 0, dizemos que a divide b se existe um
inteiro c tal que b = ac. Quando a divide b dizemos que a é um factor de b e que
b é um múltiplo de a. a|b denota a divide b.
Exercı́cio 1: diga se 3|7 e se 3|12.
Exercı́cio 2: Sejam n e a inteiros positivos. Quantos inteiros positivos que não
excedem n dividem a?
Luis Antunes DCC-FCUP
Complexidade 2002/03
2
Divisão
Seja a um inteiro e d um inteiro positivo. Então existem inteiros q e r únicos, com
0 ≤ r < q, tal que a = dq + r.
Na equação anterior:
d é o divisor.
a é o dividendo.
q é o quociente (q = a div d).
r é o resto (r = a mod d).
Luis Antunes DCC-FCUP
Complexidade 2002/03
3
Divisão: exemplo
Quando dividimos 17 por 5, temos:
5 é o divisor.
17 é o dividendo.
3 é o quociente (3 = 17 div 5).
2 é o resto (2 = 17 mod 5).
Luis Antunes DCC-FCUP
Complexidade 2002/03
4
Divisão: exemplo
Quando dividimos −11 por 3, temos:
3 é o divisor.
-11 é o dividendo.
-4 é o quociente (−4 = −11 div 3).
1 é o resto (1 = −11 mod 3).
Note que o resto não pode ser negativo!
Luis Antunes DCC-FCUP
Complexidade 2002/03
5
Divisibilidade propriedades
Teorema: Sejam a,b e c inteiros. Então:
1. se a|b e a|c, então a|(b + c).
2. se a|b, então a|bc para todo o inteiro c.
3. se a|b e b|c, então a|c.
Provas:
1. Suponhamos que a|b e a|c, então por definição existem inteiros s e t tais que
b = as e c = at. Logo
b + c = as + at = a(s + t)
Luis Antunes DCC-FCUP
Complexidade 2002/03
6
Números primos
Definição: um inteiro positivo maior do que 1 é chamado número primo se os
únicos factores positivos de p são 1 e p. Um inteiro positivo maior do que 1 que
não seja primo é chamado de composto.
Exercı́cio 1: dos seguintes números identifique os primos, 3, 7, 9, 11 e 14.
Teorema fundamental da aritmética todo o inteiro positivo maior do que 1
pode ser escrito de forma única como o produto de dois ou mais primos.
Exercı́cio 2: Determine a factorização em números primos de: 100, 641, 999 e
1024.
Luis Antunes DCC-FCUP
Complexidade 2002/03
7
Números primos
Teorema:
√ Se n é um inteiro composto, então n tem um divisor primo menor ou
igual a n.
Prova: Se n é um número composto, tem um factor a com 1 < a < n. Logo
n = ab com a e b inteiros positivos maiores do que 1.
Então a ≤
√
n ou b ≤
√
n, caso contrário ab >
√ √
n n = n.
√
Logo n tem um factor menor do que n, este factor ou é um número primo ou
usando o teorema fundamental da aritmética pode ser decomposto num produto
de números primos.
Luis Antunes DCC-FCUP
Complexidade 2002/03
8
Visão crı́tica do resultado anterior
Um inteiro é um número primo se não for divisı́vel por nenhum número primo
menor ou igual a sua raı́z quadrada.
Luis Antunes DCC-FCUP
Complexidade 2002/03
9
Exercı́cios
1. Qual o quociente e o resto da divisão de 19 por 7?
2. Mostre que se a, b e c são inteiros tais que ac|bc então a|b.
3. Mostre que 101 é um número primo.
4. Determine a factorização de 7007.
Luis Antunes DCC-FCUP
Complexidade 2002/03
10
Quantos números primos?
Teorema: Existe uma infinidade de números primos.
Prova:Sup. que existe um número finito de primos p1, p2, ..., pn. Seja
Q = p1 × p2 × ... × pn + 1
T. F. A. Q é primo ou pode ser escrito como o produto de dois ou mais primos.
Contudo, nenhum dos primos pi divide Q, senão pi|(Q − p1 × p2 × ... × pn = 1).
O que é uma contradição, visto que assumimos que p1, p2, ..., pn listava todos os
primos.
Logo existe uma infinidade de números primos.
Luis Antunes DCC-FCUP
Complexidade 2002/03
11
Máximo divisor comum
Definição: Sejam a e b inteiros diferentes de zero. O maior inteiro d tal que d|a e
d|b é chamado de máximo divisor comum de a e b, d = mdc(a, b).
Exercı́cio 1: Calcule mdc(24, 36).
Exercı́cio 2: Calcule mdc(22, 17).
Definição: Os inteiros a e b são primos relativos se o seu máximo divisor comum
é 1.
Luis Antunes DCC-FCUP
Complexidade 2002/03
12
Máximo divisor comum
Uma outra forma de determinar o máximo divisor comum é factorizar os inteiros
a = pa1 1 pa2 2 ...pann
b = pb11 pb22 ...pbnn
todos os números primos presentes na factorização de a e b estão presentes na
fórmula anterior.
Então
min(a1 ,b1 ) min(a2 ,b2 )
n ,bn )
p2
...pmin(a
n
mdc(a, b) = p1
Exercı́cio 1: Calcule mdc(120, 500).
Luis Antunes DCC-FCUP
Complexidade 2002/03
13
Mı́nimo múltiplo comum
Definição: Sejam a e b inteiros positivos, o mı́nimo múltiplo comum entre a e b
é o menor inteiro que é divisı́vel por a e por b, mmc(a, b).
Se
a = pa1 1 pa2 2 ...pann
b = pb11 pb22 ...pbnn
todos os números primos presentes na factorização de a e b estão presentes na
fórmula anterior.
Então
max(a1 ,b1 ) max(a2 ,b2 )
p2
...pnmax(an,bn)
mmc(a, b) = p1
Exercı́cio 1: Calcule mmc(120, 500).
Luis Antunes DCC-FCUP
Complexidade 2002/03
14
Mı́nimo múltiplo comum
Teorema: Sejam a e b inteiros positivos. Então
ab = mdc(a, b)mmc(a, b)
Luis Antunes DCC-FCUP
Complexidade 2002/03
15
Aritmética modular
Definição: Sejam a e b inteiros e m um inteiro positivo, dizemos que a é
congruente com b modulo m se m divide a − b, a ≡ b (mod m).
Teorema: Sejam a e b inteiros e m um inteiro positivo. Então a ≡ b (mod m) se
e só se a mod m = b mod m.
Exercı́cio 1: determine se 17 é congruente com 5 modulo 6.
Luis Antunes DCC-FCUP
Complexidade 2002/03
16
Exercı́cios
1. Quais os inteiros positivos menores do que 12 são primos relativos com 12?
2. Seja m um inteiro positivo. mostre que a ≡ b (mod m) se a mod m = b mod
m.
3. Determine: mdc(1000, 645), mmc(1000, 645).
4. Calcule −17 mod 2, e 144 mod 7.
Luis Antunes DCC-FCUP