DIVISIBILIDADE
Neste momento inicial, nosso interesse será em determinar quando a divisão entre dois números inteiros é exata, ou seja, quando o resto da divisão é 0.
Antes de mais nada, vamos à definição crucial desta parte:
DEFINIÇÃO
Dizemos que o inteiro a é divisível pelo inteiro b (ou ainda que a é múltiplo de b) se existe um inteiro c tal que a = bc.
Exemplos:
15 é múltiplo de 3
33 é múltiplo de 11
17 não é múltiplo de 2
Vejamos agora alguns critérios de divisibilidade importantes que ajudam a ganhar tempo em diversos problemas.
CRITÉRIOS DE DIVISIBILIDADE
DIVISIBILIDADE POR 2
Um número é múltiplo de 2 se, e somente se, seu último algarismo é par.
Resto na divisão por 2: se o último algarismo é par, o resto é 0 e se o último algarismo é ímpar, o resto é 1.
Exemplo:
2344 é múltiplo de 2, pois 4 é par, mas 31441 não é múltiplo de 2, pois 1 é ímpar. O resto de 31441 na divisão por 2 é 1.
DIVISIBILIDADE POR 3
Um número é múltiplo de 3 se, e somente se, a soma de seus algarismos é múltipla de 3.
Resto na divisão por 3: resto da soma dos algarismos do número na divisão por 3.
Exemplo:
3459 é múltiplo de 3, pois 3 + 4 + 5 + 9 = 21 e 2 + 1 = 3, que é múltiplo de 3, mas 121 não é múltiplo de 3, pois 1 + 2 + 1 = 4 não o é. O resto de 121 na divisão por 3 é 1.
DIVISIBILIDADE POR 4
Um número é múltiplo de 4 se, e somente se, o número formado por seus dois últimos algarismos é múltiplo de 4.
Resto na divisão por 4: resto do número formado pelos dois últimos algarismos na divisão por 4.
Exemplo:
15684 é múltiplo de 4, pois 84 é múltiplo de 4, mas 14234 não é múltiplo de 4, já que 34 não o é. O resto de 14234 na divisão por 4 é 2.
DIVISIBILIDADE POR 5
Um número é múltiplo de 5 se, e somente se, seu último algarismo é 0 ou 5.
Resto na divisão por 5: resto do último algarismo na divisão por 5.
Exemplo:
995 é múltiplo de 5, pois o último algarismo é 5, mas 1003 não é múltiplo de 5, pois o último algarismo é 3. O resto de 1003 na divisão por 5 é 3.
DIVISIBILIDADE POR 6
Um número é múltiplo de 6 se, e somente se, é múltiplo de 2 e de 3. Resto na divisão por 6: resto por 6 da soma do algarismo das unidades com o quádruplo da soma dos algarismos anteriores.
Exemplo:
6|120, mas 722 não é múltiplo de 6. O resto de 722 na divisão por 6 é o resto de 2 + 4 (7 + 2) = 2 + 36 = 38 na divisão por 6, que é 2.
DIVISIBILIDADE POR 7
Um número é múltiplo de 7 se, e somente se, a soma das classes ímpares menos a soma das classes pares é múltipla de 7.
Resto na divisão por 7: resto da soma das classes ímpares menos a soma das classes pares na divisão por 7.
Exemplo:
7|1638931720888, pois a soma das classes ímpares é
888 + 931 + 1 = 1820 e a soma das classes pares é 720 + 638 = 1358,
donde a diferença é 462 = 66 ⋅ 7, que é múltipla de 7.
DIVISIBILIDADE POR 8
Um número é múltiplo de 8 se, e somente se, o número formado pelos três últimos algarismos é múltiplo de 8.
Resto na divisão por 8: resto do número formado pelos três últimos algarismos na divisão por 8.
Exemplo:
271824 é múltiplo de 8, pois 824 é múltiplo de 8, mas 31442 não é múltiplo de 8, pois 442 = 55 ⋅ 8 + 2, donde o resto de 31442 na divisão por 8 é 2.
DIVISIBILIDADE POR 9
Um número é múltiplo de 9 se, e somente se, a soma de seus algarismos é múltipla de 9.
Resto na divisão por 9: resto da soma dos algarismos do número na divisão por 9.
Exemplo:
1233 é múltiplo de 9, pois 1 + 2 + 3 + 3 = 9 é múltiplo de 9, mas 727 não é múltiplo de 9, pois 7 + 2 + 7 = 16 e 16 = 9 . 1 + 7, donde o resto de 727 na divisão por 9 é 7.
DIVISIBILIDADE POR 10
Um número é múltiplo de 10 se, e somente se, seu algarismo das unidades é 0. Resto na divisão por 10: o resto de um número na divisão por 10 é o algarismo das unidades.
Exemplo:
880 é múltiplo de 10, pois 880 termina em 0, mas 1003 não é múltiplo de 10 e seu resto na divisão por 10 é 3.
DIVISIBILIDADE POR 11
Um número é múltiplo de 11 se, e somente se, a diferença entre a soma dos algarismos de ordem ímpar e a soma dos algarismos de ordem par é múltipla de 11.
Resto na divisão por 11: resto da diferença entre a soma dos algarismos de ordem ímpar e a soma dos algarismos de ordem par na divisão por 11.
Exemplo:
407 é múltiplo de 11, pois 7 + 4 – 0 = 11 é múltiplo de 11, mas 300 não é múltiplo de 11, pois 0 + 3 – 0 = 3 não o é. Seu resto na divisão por 11 é 3.
DIVISIBILIDADE POR 2K
Um número é múltiplo de 2k se, e somente se, o número formado pelos seus k últimos algarismos é múltiplo de 2k .
Resto na divisão por 2k : resto do número formado pelos k últimos algarismos na divisão por 2k .
DIVISIBILIDADE POR 5K
Um número é múltiplo de 5k se, e somente se, o número formado pelos seus k últimos algarismos é múltiplo de 5k
.
Resto na divisão por 5k : resto do número formado pelos k últimos algarismos na divisão por 5k .
DIVISIBILIDADE POR 10K
Um número é múltiplo de 10k se, e somente se, seus k últimos algarismos são zeros.
Resto na divisão por 10k : o resto é o número formado pelos k últimos algarismos.
PROPRIEDADES IMPORTANTES
I. O resto de uma soma na divisão por um determinado número N é igual ao resto da soma dos restos de cada parcela na divisão por N.
Exemplo:
Calcular o resto de 123 + 441 + 1829 na divisão por 5. Basta calcular o resto de 3 + 1 + 4 = 8 na divisão por 5, que é 3.
II. O resto de um produto na divisão por um determinado número N é igual ao resto do produto dos restos de cada
fator na divisão por N.
Exemplo:
Calcular o resto de 765 · 423 · 112 na divisão por 11. Basta calcular o resto de 6 ⋅ 5 ⋅ 2 = 60 na divisão por 11, que é 5.
III. Para achar o resto de uma potência na divisão por um determinado número N, calcula-se primeiramente o resto da base na divisão por N e depois eleva-se esse resto ao expoente dado. Obtido esse número, calcula-se o resto na divisão por N.
Exemplo:
Calcular o resto de 349 na divisão por 7.
O resto de 34 na divisão por 7 é 6. Então, precisamos calcular o resto de 69 na divisão por 7. Mas 62 = 36 deixa resto 1 na divisão por 7. Assim, 68 deixa resto 1 na divisão por 7 e, portanto 69 = 68 ⋅ 61 deixa resto 6 na divisão por 7.
FATORAÇÃO EM NÚMEROS PRIMOS
Vejamos uma definição inicial:
DEFINIÇÃO
Um número inteiro p é dito um número primo quando possui exatamente quatro divisores inteiros: ±p, ±1. Por outro lado, um inteiro é dito composto quando não é primo.
Exemplo:
2,3,5,7,11 são números primos, mas 6,15,21,42 são números compostos.
Observação
O único número primo par é o 2.
O resultado mais importante referente a números primos é o chamado teorema fundamental da Aritmética:
TEOREMA FUNDAMENTAL DA ARITMÉTICA
Todo inteiro maior do que 1 pode ser expresso de maneira única (a menos da ordem) como produto de fatores primos.
Exemplo:
5544 = 23 ⋅ 32 ⋅ 7 ⋅ 11
DIVISORES DE UM NÚMERO
Os divisores de um número inteiro n são todos os inteiros m tais que n é múltiplo de m.
MÁXIMO DIVISOR COMUM (MDC)
DEFINIÇÃO
Dados dois inteiros a e b não nulos, o máximo divisor comum de a e b (denotado por mdc(a,b)) é o maior inteiro positivo que divide a e b simultaneamente.
Exemplo:
Os divisores naturais de 30 são: 1, 2, 3, 5, 6, 10, 15, 30
Os divisores naturais de 12 são: 1, 2, 3, 4, 6, 12
Veja que o maior inteiro que aparece nas duas listas é o 6. Assim, mdc(30,12) = 6.
Observação
Dois números a e b com mdc igual 1 a são ditos primos entre si.
Você deve estar se perguntando agora: será que existe uma maneira mais prática de calcular o mdc de dois números? A resposta é SIM. Vejamos agora como:
ALGORITMO DE EUCLIDES
Dados A e B (A > B), dividimos A por B, obtendo quociente q1 e resto r1 . Colocamos q1 acima de B e r1 abaixo de A e ao lado de B (r1 será agora o novo divisor e o novo dividendo é B). Feito isso, dividimos B por r1 , obtendo quociente q2 e resto r2 . Colocamos q2 acima de r1 e r2 abaixo de B e ao lado de r1 (r2 será agora o novo divisor e o novo dividendo é r1 ). Repetimos este processo até obter resto 0. O último divisor, rn , será o mdc.
O método acima normalmente é apresentado através do dispositivo de cálculo a seguir:
MÉTODO DA DECOMPOSIÇÃO CANÔNICA
Neste método, encontramos inicialmente a fatoração em primos dos números de interesse: a = p1 α1 · p2 α2 · … · pn
αn e b = p1 β1 · p2 β2 · … · pn βn (alguns expoentes podem ser NULOS!).
Desta forma, temos que mdc(a,b) = p1 min{α1,β1} · p2 min{α2,β2} · … · pn min{αn,βn} , ou seja, mdc(a,b) é o produto dos fatores primos comuns às duas decomposições tomados com seus menores expoentes.
Exemplo:
665 = 5 ⋅ 7 ⋅ 19 e 280 = 23 ⋅ 5 ⋅ 7.
Logo, mdc(665,280) = 5 . 7 = 35.
ProBizu
Se mdc(a,b) = d, podemos escrever a = du, b = dv, com u,v primos entre si.
MÍNIMO MÚLTIPLO COMUM (MMC)
DEFINIÇÃO
O mmc entre dois inteiros não nulos a e b é o menor inteiro positivo que é divisível por a e b.
Exemplo:
Os múltiplos positivos de 30 são: 30, 60, 90, 120, 150, …
Os múltiplos positivos de 12 são: 12, 24, 36, 48, 60, 72, …
Veja que 60 é o menor número comum às duas listas. Desta forma, mmc(30, 12) = 60.
Assim como no mdc, vejamos um método de calcular o mmc entre dois números.
Observação
O mmc de dois números primos entre si é igual ao produto entre estes números. Por exemplo, 3 e 5 são primos entre si e, portanto, mmc (3,5) = 3 x 5 = 15.
MÉTODO DA DECOMPOSIÇÃO CANÔNICA Tal qual no mdc, encontramos primeiramente a fatoração dos
números de interesse: a = p1 α1 · p2 α2 · … · pn αn e b = p1 β1 · p2 β2 · … · pn βn (alguns expoentes podem ser NULOS!).
Desta forma, temos que mmc(a,b) = p1 min{α1,β1} · p2 min{α2,β2} · … · pn min{αn,βn} ou seja, mmc(a,b) é o produto dos fatores primos comuns e não comuns às duas decomposições tomados com seus maiores
expoentes.
Exemplo:
665 = 5 ⋅ 7 ⋅ 19 e 280 = 23 ⋅ 5 ⋅ 7.
Logo, mmc(665,280) = 23 ⋅ 5 ⋅ 7 ⋅ 19 = 5320.
Observação
O seguinte resultado é bastante útil: dados inteiros a,b não nulos, vale que ab = mmc(a,b) · mdc(a,b)
