Divisibilidade

Estruturas Discretas
Divisibilidade e Aritmética Modular

Divisibilidade
Quando um número inteiro é dividido por um segundo número inteiro, diferente de zero, o quociente pode ou não ser um número inteiro
Exemplo:
12/3 = 4 quociente inteiro
11/4=2,75 quociente não inteiro
Se a e b são números inteiros com a&0, dizemos que a divide b se houver um número inteiro c de modo que b=ac. a é um fator de b b é um múltiplo de a
Notação:
a|b a divide b
08/04/2012

Teorema
Se um número inteiro a divide outros dois números inteiros b e c, ele divide a soma b+c (e a diferença).
6 divide 30 e 48
6 divide 30+48 = 78.
E 6 divide 48-30 = 18

Teorema
Se um número inteiro a divide um número b e se esse número divide c então a divide c.
2 divide 6 e 6 divide 30 logo 2 divide 30
08/04/2012
3

Teorema
Se um número inteiro a divide um número b então a divide bc para qualquer inteiro c.
2 divide 6 logo 2 divide 30 (6.5)

Corolario
Se a,b e c são números inteiros, tal que a|b e a|c, então a|mb+nc sempre que m e n forem números inteiros.
2 divide 6 e 2 divide 4 então 2 divide 38 (3.6 +5.4)
08/04/2012
4

Equação de Euclides
Considere a e d como inteiros , sendo d não negativo. Então haverá inteiros q e r únicos, com 06r<d, tal que a=d*q + r a:dividendo d: divisor q:quociente r:resto
Quando r=0 a é múltiplo de d e q d e q são divisores de a q=a div d e r = a mod d
Exemplo: Qual o quociente e o resto para 101 dividido por 11?
E -11 dividido por 3?

Propriedades
Dividimos dois números por um mesmo divisor. Se a soma
(diferença) dos restos for menor que o divisor ela será igual ao resto da divisão da soma (diferença) dos dois números pelo divisor.
22 = 7 * 3 + 1 e 33 = 7 * 4 + 5
A soma dos restos é 6 (menor que 7).
22+33 = 55
55 = 7 * 7 + 6
A diferença dos restos é 4 (menor que 7)
33-22 = 11
11 =7 * 1 + 4
08/04/2012
5

Observação
Quando efetuando a diferença dos números, se a diferença dos restos for um número