Início / Teoria dos números / Divisibilidade, fatoração e primos
Trilha 2

Divisibilidade, fatoração e primos

Este bloco aprofunda a divisibilidade vista na aritmética: fatoração por expoentes, contagem de divisores, propriedades dos primos, MMC, MDC e estrutura dos inteiros.

Divisibilidade

Divisibilidade é a primeira ferramenta para cortar casos. Em vez de calcular tudo, você testa se certa forma de número pode ou não aparecer.

Critérios rápidos
  • 2 último algarismo par
  • 3 soma dos algarismos divisível por 3
  • 4 dois últimos algarismos divisíveis por 4
  • 5 termina em 0 ou 5
  • 8 três últimos algarismos divisíveis por 8
  • 9 soma dos algarismos divisível por 9
  • 11 diferença entre somas alternadas divisível por 11
Algoritmo da divisão: para a e b > 0, existem inteiros q e r tais que a = bq + r e 0 ≤ r < b.

MMC e MDC

MMC e MDC aparecem quando você quer sincronizar repetições ou separar uma estrutura comum. Pela fatoração prima, tudo fica mais automático.

QuantidadeRegra pela fatoração
MMCuse os maiores expoentes de cada primo
MDCuse os menores expoentes comuns
!
Leitura prática: o MMC olha para frente, buscando encontro de ciclos; o MDC olha para trás, buscando a maior estrutura comum.

Primos e fatoração

Todo inteiro maior que 1 pode ser escrito como produto de primos de modo único, a menos da ordem. Esse é o esqueleto da matéria.

Teorema fundamental da aritmética
n = p1a p2b ... pkm
Os pi são primos distintos.
Exemplo
Fatore 360 em primos.
1
Divida por 2 enquanto puder: 360 = 2 . 180 = 22 . 90 = 23 . 45.
2
Agora use 3: 45 = 32 . 5.
360 = 23 . 32 . 5.

Contagem de divisores

Depois da fatoração, várias perguntas viram leitura de expoentes. Essa é uma das técnicas mais úteis da teoria dos números elementar.

Cada divisor é formado escolhendo quantas vezes cada primo da fatoração aparece. Se um primo aparece com expoente máximo a, o divisor pode usar esse primo com expoente 0, 1, 2, ..., a.

Número de divisores positivos
Se n = p1a · p2b · p3c · ... · pkm, então d(n) = (a+1)(b+1)(c+1)...(m+1)

O +1 aparece porque o expoente zero também conta. Se aparece 23 na fatoração, um divisor pode usar 20, 21, 22 ou 23. Isso dá 4 opções, ou seja, 3+1. O expoente zero significa "não usar aquele primo" no divisor.

Exemplo conectado
Quantos divisores positivos tem 360?
1
Pela fatoração anterior, 360 = 23 · 32 · 51.
2
Para 23: opções 20, 21, 22, 23, total de 4 opções.
3
Para 32: opções 30, 31, 32, total de 3 opções.
4
Para 51: opções 50, 51, total de 2 opções.
5
Multiplique as escolhas independentes: 4 · 3 · 2 = 24.
Portanto, d(360) = (3+1)(2+1)(1+1) = 24.

Assim, a fórmula não está contando os primos, mas sim as escolhas possíveis de expoentes para formar divisores.

Exercícios rápidos

Cheque rápido
Se n = 23.32, quantos divisores positivos n tem?
← Anterior Congruências e aritmética modular