Um conceito chave em 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 = b c. Nesse 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, 4 é 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 = b c + r, com 0 < r < b.

Definição:

Sejam a e b números inteiros com a não nulo. Dizemos que a divide b (ou que b é divisível pôr a, ou ainda, que b é múltiplo de a se existe um inteiro c tal que b = a × c.

Notação:

a | b para indicar que a divide b. Chamamos a de divisor de b.

O inteiro c nas condições da definição é único. De fato, se existisse outro d tal que b = ad, então teríamos que ac = ad, logo (como a ¹ 0) c = d.

O inteiro assim definido c é chamado de quociente de b por a.

"0" possui infinitos divisores positivos e os inteiros 1 e -1 possuem um único divisor positivo.

Proposição:

Para quaisquer inteiros a, b, c e d (lembrando que os divisores são sempre não nulos), temos que:

Para todo inteiro a tem-se que a|a

Se a|b e b|c, então a|c

Se a|b e c|d, então a × c | b × d

Se a|b e a|c, então a | b + c

Se a|b, então para qualquer n Î , tem-se que a | b × n

Se a|b, e a|c, então para quaisquer m e n Î , tem-se que a | (b × m + c × n).

Divisibilidade e resto

Sejam a e b números inteiros com a não nulo. Então, existem inteiros q e r, únicos, tais que:

b = a × c + r, com 0 £ r < |a|.

Os números q e r são chamados de quociente e resto, da divisão de a pôr b.

Um termo que é dado pela noção de divisibilidade é a de máximo divisor comum (mdc) que definimos a seguir.

Definição:

Sejam a e b números inteiros. Dizemos que um número inteiro d é o máximo divisor comum de a e b se e somente se d|a e d|b e para qualquer inteiro c que divide a e b tem-se que c|d.

Teorema de Bezout

Sejam a e b números inteiros com d = mdc(a, b).

Então, existem inteiros r e s tais que d = a × r + b × s.

Aplicação do Teorema:

Proposição:

Sejam a, b números inteiros, mdc(a, b) = d, e c um inteiro qualquer.

Então mdc(a × c, b × c) = d × |c|.

Teorema de Euclides

Sejam a, b e c números inteiros tais que a | b × c. Se mdc(a, b) = 1, então a|c.

Definição:

Dois números inteiros a e b são ditos relativamente primos se mdc(a, b) = 1.

Donde segue o seguinte resultado:

Proposição:

Sejam a e b números inteiros relativamente primos e c outro inteiro.

Se a ½ c e b ½ c,