Aula16

Matem´ atica para Ciˆ encia de Computadores
1 o Ano - LCC & ERSI
Lu´ıs Antunes

[e-mail]
DCC-FCUP

Luis Antunes DCC-FCUP

Complexidade 2002/03

1

Inteiros e divis˜ ao Defini¸c˜ ao: Se a e b s˜ao inteiros com a = 0, dizemos que a divide b se existe um inteiro c tal que b = ac. Quando a divide b dizemos que a ´ e um factor de b e que b´ e um m´ ultiplo 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˜ao excedem n dividem a?

Luis Antunes DCC-FCUP

Complexidade 2002/03

2

Divis˜ ao Seja a um inteiro e d um inteiro positivo. Ent˜ao existem inteiros q e r u
´nicos, com
0 ≤ r < q, tal que a = dq + r.
Na equa¸c˜ao anterior: d ´e o divisor. a ´e o dividendo. q ´e o quociente (q = a div d). r ´e o resto (r = a mod d).
Luis Antunes DCC-FCUP

Complexidade 2002/03

3

Divis˜ ao: exemplo

Quando dividimos 17 por 5, temos:
5 ´e o divisor.
17 ´e o dividendo.
3 ´e o quociente (3 = 17 div 5).
2 ´e o resto (2 = 17 mod 5).

Luis Antunes DCC-FCUP

Complexidade 2002/03

4

Divis˜ ao: exemplo

Quando dividimos −11 por 3, temos:
3 ´e o divisor.
-11 ´e o dividendo.
-4 ´e o quociente (−4 = −11 div 3).
1 ´e o resto (1 = −11 mod 3).
Note que o resto n˜ao pode ser negativo!

Luis Antunes DCC-FCUP

Complexidade 2002/03

5

Divisibilidade propriedades
Teorema: Sejam a,b e c inteiros. Ent˜ao:
1. se a|b e a|c, ent˜ao a|(b + c).
2. se a|b, ent˜ao a|bc para todo o inteiro c.
3. se a|b e b|c, ent˜ao a|c.
Provas:
1. Suponhamos que a|b e a|c, ent˜ao por defini¸c˜ao 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´ umeros primos

Defini¸c˜ ao: um inteiro positivo maior do que 1 ´e chamado n´ umero primo se os u ´nicos factores positivos de p s˜ao 1 e p. Um inteiro positivo maior do que 1 que n˜ao seja primo ´e chamado de composto.
Exerc´ıcio 1: dos seguintes n´ umeros identifique os primos, 3, 7, 9, 11 e 14.