TEORIA DOS NÚMEROS - DIVISIBILIDADE

Divisibilidade

Um conceito chave na Teoria dos Números é o conceito de divisibilidade. Enquanto nos números reais, por exemplo, pode-se dividir qualquer número por outro (não nulo), obtendo como resultado um número real, nos inteiros é diferente. Um inteiro a só é divisível pelo inteiro b quando existir um inteiro c tal que a=bc. Neste caso, diz-se também que b é um divisor de a ou que b divide a, ou ainda que a é múltiplo de b.
Por exemplo, 8 é divisível por 2, mas não é por 3. Mesmo que a não seja divisível por b, pode-se sempre encontrar, de modo único, inteiros c (quociente) e r (resto) tais que a=bc+r, com 0 < r < b.
Existem muitos aspectos interessantes referentes à divisão de números inteiros. Antes que possam ser analisados, é necessário que conceitos básicos como divisor e divide estejam bem claros.
É lógico que podemos efetuar as quatro operações com números inteiros. Somar e subtrair é como correr pela linha onde os inteiros estão dispostos. Multiplicar é como se fosse correr mais depressa.
DIVIDIR já nos traz uma dor de cabeça: nem sempre podemos dar passos completos e a gente acaba tropeçando nos restos.

Divisores

Os divisores ou fatores de um número inteiro positivo são inteiros que dividem o número uniformemente. Por exemplo, os divisores de 28 são 1, 2, 4, 7, 14 e 28. Claro que 28 também é divisível pelos opostos de cada um dos divisores (-1, -2, etc) mas, geralmente, consideramos como "divisores" apenas os positivos. Veja a definição clássica de número primo: aquele cujos únicos divisores são 1 e ele próprio. Nadinha de negativos...
Muitas funções da teoria dos números estão relacionadas a divisores de n. Por exemplo, τn ou tau(n) é o número de divisores de n e σn ou sigma(n) é a soma dos divisores de n.
Existe um outro uso para a palavra divisor: quando dividimos um número inteiro a por um inteiro b diferente de zero para obter um quociente e um resto (veja o algoritmo da divisão), b é o divisor e a é o dividendo.

Divide

Dizemos que um inteiro divide outro inteiro quando ele o faz uniformemente, ou seja, quando o resto da divisão for zero. Algumas vezes dizemos "sem resto", mas isto não é tecnicamente correto. Os matemáticos escrevem isto com um pouco mais de formalidade:

Se a e b são inteiros e a for diferente de zero, dizemos que a divide b se houver um inteiro c de modo que b = ac.

Este conceito é usado com tanta frequência que tem até seus próprios símbolos:

a | b	significa que a divide b
a b	significa que a não divide b

Finalmente, suponha que p seja um número primo e que k seja um inteiro positivo. Uma notação que rapidamente está ganhando aceitação é escrever p^k || a para indicar que p^k divide a, porém p^k+1 não.
Propriedades da Divisão

• a | 0, 1 | a e a | a
• a | 1 se, e somente se a=±1
• Se a | b e c | d então ac | bd
• Se a | b e b | c então a | c
• a | b e b | a se, e somente se a=±b
• Se a | b e b não for zero, então |a| < |b|
• Se a | b e a | c então a | (bx+cy) para todos os inteiros x e y

O