Teoria de números/Divisibilidade

A teoria de números é a área da matemática em que é estudado o anel dos números inteiros. O conjunto dos números inteiros é denotado por $\mathbb {Z}$, sendo que:

$\mathbb {Z} =\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}$

O conjunto $\mathbb {Z}$ pode ser definido formalmente a partir do conjunto dos números naturais $\mathbb {N} =\{0,1,2,3,\ldots \}$ e estes, a partir dos axiomas de Peano. Para maiores detalhes sobre o assunto pode ser consultado o livro de Milies & Coelho (2003).

O conjunto dos números inteiros é definido juntamente com duas operações: a adição e a multiplicação.

A estrutura aditiva dos números inteiros é trivial. Acompanhe os exemplos:

$\mathbf {-2} =-1-1$

$\mathbf {-1}$

$\mathbf {0} =1-1$

$\mathbf {1}$

$\mathbf {2} =1+1$

$\mathbf {3} =2+1=(1+1)+1$

$\mathbf {4} =2+2=(1+1)+(1+1)$

Como se pode observar, qualquer número inteiro pode ser "formado aditivamente" a partir do número 1. Nesse sentido, a unidade é o "bloco básico" a partir do qual são construidos todos os números inteiros, usando-se as propriedades da operação de adição (como por exemplo a associatividade e a existência de elemento oposto).

Além disso, dado um número inteiro, sua decomposição em "blocos basicos" é essencialmente uma só. Por exemplo, se considerarmos o número 5, teremos:

$\mathbf {5} =2+2+1=(1+1)+(1+1)+1$

$\mathbf {5} =2+1+2=(1+1)+1+(1+1)$

No entanto, a única diferença entre duas representações do 5 é a posição dos parentesis. Não há uma mudança significativa.

Já a estrutura multiplicativa de $\mathbb {Z}$ é muito mais sofisticada. Veja alguns exemplos:

$\mathbf {2} =$ bloco básico

$\mathbf {3} =$ bloco básico

$\mathbf {4} =2\cdot 2$

$\mathbf {5} =$ bloco básico

$\mathbf {6} =2\cdot 3$

$\mathbf {7} =$ bloco básico

$\mathbf {8} =2\cdot 2\cdot 2$

$\mathbf {9} =3\cdot 3$

$\mathbf {10} =2\cdot 5$

$\mathbf {11} =$ bloco básico

$\mathbf {12} =2\cdot 2\cdot 3$

Como deve ter percebido, quando se trata da operação de multiplicação, não existe um único bloco básico que gere todos os outros números. Por exemplo, os números 2, 3, 5, 7 e 11 não têm como ser obtidos a partir da multiplicação de dois números inteiros (além de 1 e eles próprios), mas permitem gerar outros números: $6=2\cdot 3$, $10=2\cdot 5$ e assim por diante. Parece razoável que todos os inteiros podem ser gerados dessa maneira, bastando encontrar os blocos básicos adequados.

Mas será que mesmo sendo necessários mais "blocos básicos" para a estrutura multiplicativa que para a aditiva, um número inteiro sempre será decomposto de forma única em tais blocos?

Como foi visto, isso é o que acontece na estrutura aditiva. No entanto, para reponder (afirmamente) esta pergunta, será necessário definir o conceito de divisibilidade, e conhcer de suas algumas propriedades. Este é o conteúdo da próxima seção.

Definição de divisibilidade

Definição

Insira o texto da definição.

O conceito apresentado acima define uma relação binária no conjunto dos números inteiros: a divisibilidade.

Lembre-se que uma relação binaria sobre $\mathbb {Z} \,\!$ é qualquer subconjunto $R\,\!$ do conjunto das partes de $\mathbb {Z}$, $P(\mathbb {Z} )$. No caso da divisibilidade, tem-se:

$R=\{(a,b)|a{\mbox{ divide }}b\}\,\!$

Nesses termos, quando $(a,b)\in R$ costuma-se dizer que $a\,\!$ está relacionado com $b\,\!$ escrevendo-se $aRb\,\!$.

Propriedades da divisibilidade

A relação de divisibilidade possui as seguintes propriedades, para quaisquer (salvo indicação em contrário) inteiros $a,b,c,d,r,s$:

1. $a|a\,\!$	(reflexividade)
2. $a|b\,\!$ e $b|c\,\!$ implica $a|c\,\!$	(transitividade)
3. $a|b\,\!$ e $b|c\,\!$ implica $a=b\,\!$ ou $a=-b\,\!$
4. $c|a\,\!$ e $c|b\,\!$ implica $c|ra+sb\,\!$	(linearidade)
5. $a|b\,\!$ e $c|d\,\!$ implica $ac|bd\,\!$
6. $a|b\,\!$ implica $ac|bc\,\!$	(multiplicatividade)
7. $ac|bc\,\!$ e $c\not =0\,\!$ implica $a|b\,\!$	(lei do cancelamento)
8. $1|a\,\!$	($1$ divide todo número inteiro)
9. $a|0\,\!$	(todo número inteiro divide zero)
10. $0|a\,\!$ implica $a=0\,\!$	(zero só divide zero)
11. $a|1\,\!$ implica $a=\pm 1\,\!$	(os divisores de 1 são 1 e -1)
12. $a|b\,\!$ e $b\not =0\,\!$ implica $|a|\leq |b|\,\!$	(compatibilidade com a ordem "$\leq$")
13. $a|b\,\!$ e $a\not =0\,\!$ implica $(b/a)|b\,\!$

A demonstração dessas propriedades é deixada a cargo do leitor. No entanto, sinta-se convidado a melhorar este texto acrescentando qualquer dessas demonstrações.

Observações

• A terceira propriedade seria chamada de anti-simetria, se não fosse necessário considerar o caso "$a=-b$". Quando são considerados apenas os números não-negativos (os elementos de $\mathbb {Z} _{+}$) a conclusão é apenas "$a=b$", e as propriedades de 1 a 3 fazem da divisibilidade uma relação de ordem parcial sobre $\mathbb {Z} _{+}$. No entanto, essa não é uma ordem total, pois nem todo par de elementos em $\mathbb {Z} _{+}$ é comparável, ou seja, existem inteiros não negativos $a$ e $b$, para os quais não se tem $a|b$ nem $b|a$.

• Frequentemente é mais prático trabalhar apenas com o conjunto dos números naturais $\mathbb {N}$ (o subconjunto dos inteiros não-negativos $\mathbb {Z} _{+}$) ou com os números naturais não nulos $\mathbb {N} ^{*}$ (os inteiros positivos $\mathbb {Z} _{+}^{*}$).

• As propriedades 1 e 8 garantem que todo número inteiro $a$ possui ao menos dois divisores, chamados de divisores triviais: $\pm 1\,\!$ e $\pm a\,\!$. Os números que possuem somente estes divisores são de grande interesse na teoria de números, e serão estudados no próximo capítulo.

Critérios de divisibilidade

Em sua formação básica, é possível que você tenha aprendido algumas regras (ou critérios) para saber rapidamente se um certo número é divisível por outro. Por exemplo, você deve saber que um número é par quando seus seu último dígito for par (e somente nessa situação). Outra regra bastante conhecida é a que permite saber se um número é divisível por $5\,\!$: basta conferir se o último dígito é zero ou $5\,\!$.

O que talvez você não saiba é que podem ser deduzidos critérios de divisibilidade para outros números, embora nem sempre eles sejam tão simples e fáceis de memorizar. Uma relação com algumas dessas regras é apresentada na tabela a seguir:

Um número é divisível por...	quando...	Exemplos
1	Sempre!	Qualquer número inteiro é divisível por 1.
2	Seu dígito das unidades é par (0, 2, 4, 6, ou 8).	1 294 é par, pois 4 é par.
3	A soma dos seus dígitos é um múltiplo de 3.	405 é divisível por 3, pois 4 + 0 + 5 = 9, que é múltiplo de 3.
4	O dígito das unidades somado com o dobro do dígito das dezenas é múltiplo de 4.	5 096 é múltiplo de 4, pois 6 + (2 × 9) = 24 que é múltiplo de 4
	Os dois últimos dígitos formam um número divisível por 4.	70841 não é divisível por 4, pois 41 não é.
5	O dígito das unidades é 0 ou 5.	1234567890 é divisível por 5, já que seu último dígito é 0.
6	É divisível por 2 e por 3.	24 é divisível por 6, já que seu é multiplo de 2 e de 3.
	A soma do dígito das unidades com o quádruplo da soma dos demais dígitos for divisível por 6.	12348 é divisível por 6, pois (1 + 2 + 3 + 4) × 4 + 8 = 48
7	The number obtained from these examples must be divisible by 7, as follows:
	Form the alternating sum of blocks of three from right to left.	1,369,851: 851 - 369 + 1 = 483 = 7 × 69
	Double the number with the last two digits removed and add the last two digits.	364: (3 × 2) + 64 = 70.
	Add 5 times the last digit to the rest.	364: 36 + (5 × 4) = 56.
	Subtract twice the last digit from the rest.	364: 36 − (2 × 4) = 28.
8	The number obtained from these examples must be divisible by 8, as follows:
	If the hundreds digit is even, examine the number formed by the last two digits.	624: 24.
	If the hundreds digit is odd, examine the number obtained by the last two digits plus 4.	352: 52 + 4 = 56.
	Add the last digit to twice the rest.	56: (5 × 2) + 6 = 16.
9	The sum of the digits is divisible by 9. For larger numbers, digits may be summed iteratively. Result at the final iteration will be 9.	2,880: 2 + 8 + 8 + 0 = 18: 1 + 8 = 9.
10	The last digit is 0.	130: the last digit is 0.
11	The number obtained from these examples must be divisible by 11, as follows:
	Form the alternating sum of the digits.	918,082: 9 - 1 + 8 - 0 + 8 - 2 = 22.
	Add the digits in blocks of two from right to left.	627: 6 + 27 = 33.
	Subtract the last digit from the rest.	627: 62 - 7 = 55.

Note que as regras acima transformam um certo número em outro, geralmente menor, que preserva a divisibilidade pelo divisor em questão. Sempre que o não fica claro se um número é múltiplo de certo divisor, a regra pode ser repetida para repetidamente ao resultado.