Divisibilidade
Divisibilidade e a primeira ferramenta para cortar casos. Em vez de calcular tudo, voce testa se certa forma de numero pode ou nao aparecer.
Criterios rapidos
- 2 ultimo algarismo par
- 3 soma dos algarismos divisivel por 3
- 4 dois ultimos algarismos divisiveis por 4
- 5 termina em 0 ou 5
- 8 tres ultimos algarismos divisiveis por 8
- 9 soma dos algarismos divisivel por 9
- 11 diferenca entre somas alternadas divisivel por 11
Algoritmo da divisao: 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 voce quer sincronizar repeticoes ou separar uma estrutura comum. Pela fatoracao prima, tudo fica mais automatico.
| Quantidade | Regra pela fatoracao |
|---|---|
| MMC | use os maiores expoentes de cada primo |
| MDC | use os menores expoentes comuns |
Leitura pratica: o MMC olha para frente, buscando encontro de ciclos; o MDC olha para tras, buscando a maior estrutura comum.
Primos e fatoracao
Todo inteiro maior que 1 pode ser escrito como produto de primos de modo unico, a menos da ordem. Esse e o esqueleto da materia.
Teorema fundamental da aritmetica
n = p1a p2b ... pkm
Os pi sao 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 fatoracao, varias perguntas viram leitura de expoentes. Essa e uma das tecnicas mais uteis da teoria dos numeros elementar.
Numero de divisores
Se n = pa qb rc..., entao d(n) = (a+1)(b+1)(c+1)...
Cada expoente pode variar de 0 ate o maximo daquela fatoracao. O produto das escolhas da a quantidade de divisores positivos.
Exercicio rapido
Cheque rapido
Se n = 23.32, quantos divisores positivos n tem?