Teoria de números/Divisibilidade

Origem: Wikilivros, livros abertos por um mundo aberto.
Ir para: navegação, pesquisa


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 "capítulo específico" do wikilivro sobre álgebra abstrata, ou 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:

-2 -1 0 1 2 3 4 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots
\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}-1-1 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\mathbf{-1} \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}1-1 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\mathbf{1} \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}1+1 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(1+1)+1 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(1+1)+(1+1) \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots

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 construídos 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 básicos" é 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 parêntesis. Não há uma mudança significativa.

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

2 3 4 5 6 7 8 9 10 11 12 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots
bloco básico bloco básico \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2 bloco básico \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 3 bloco básico \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 2 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}3\cdot 3 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 5 bloco básico \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 3 \definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots

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 responder (de forma afirmativa) a esta pergunta, será necessário definir o conceito de divisibilidade, e conhecer de suas algumas propriedades. Este é o conteúdo da próxima seção.


Definição de divisibilidade[editar | editar código-fonte]

Definição

Dados os inteiros a e b, diz-se que "a divide b" e escreve-se a|b , se existe um inteiro c tal que b=a\cdot c. Alternativamente, a|b pode ser lido como "a é divisor de b", "a é um fator de b" ou "b é múltiplo de a". Quando não se tem a|b, escreve-se a\not|b.

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

Lembre-se que uma relação binária 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 a R b.

Propriedades da divisibilidade[editar | editar código-fonte]

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|a 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|\le |b| (compatibilidade com a ordem "\le ")
13. a|b e a\not = 0 implica (b/a)|b
Demonstração
A demonstração dessas propriedades é deixada a cargo do leitor. Deste modo, sinta-se convidado a melhorar este texto acrescentando qualquer dessas demonstrações neste módulo.
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 não negativo a, diferente de 1, possui ao menos dois divisores, chamados de divisores triviais: 1 e 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 no sistema de numeração decimal[editar | editar código-fonte]

Wikipedia
A Wikipédia tem mais sobre este assunto:
Critérios de divisibilidade

Nas aulas de matemática do ensino fundamental, é 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ê identifica rapidamente que um número é par quando nota que o seu último dígito é par, assim como reconhece de imediato os múltiplos de 5, pois sabe que o seu dígito das unidades é sempre 0 ou 5.

O que talvez você não saiba é que podem ser deduzidos critérios de divisibilidade para vários outros números, senão todos, embora nem sempre tais regras sejam simples e fáceis de memorizar. Uma listagem das regras mais populares é apresentada na próxima tabela. Note que as regras descritas transformam um certo número em outro, geralmente menor, que preserva a divisibilidade pelo divisor em questão. Além disso, sempre que não fica claro se um número é múltiplo de certo divisor, a mesma regra pode ser aplicada novamente ao resultado já obtido, até que se torne evidente se determinado resultado é ou não divisível pelo divisor em questão.

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 (ou seja, 0, 2, 4, 6, ou 8). 1 294 é par[1], pois 4 é par.
3 é divisível por 3 a soma dos seus dígitos.[2] 405 é divisível por 3, pois 4 + 0 + 5 = 9, que é múltiplo de 3.
4 é divisível por 4 o dígito das unidades somado com o dobro do dígito das dezenas. 5 096 é múltiplo de 4, pois 6 + (2 × 9) = 24 que é múltiplo de 4
é divisível por 4 o número formado pelos dois últimos dígitos. 70 841 não é divisível por 4, pois 41 não é.
5 o dígito das unidades é 0 ou 5. 123 456 7890 é 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 é múltiplo de 2 e de 3.
é divisível por 6 a soma do dígito das unidades com o quádruplo da soma dos demais dígitos. 12 348 é divisível por 6, pois (1 + 2 + 3 + 4) × 4 + 8 = 48
7 vale qualquer dessas propriedades:
é divisível por 7 a soma alternada dos números formados pelos blocos de três dígitos (da direita para esquerda). 1 369 851 é divisível por 7, pois 851 - 369 + 1 = 483 = 7 × 69
é divisível por 7 a soma do número formado pelos dois últimos dígitos com o dobro do número formado ao desconsiderar estes dígitos. 364 é divisível por 7, uma vez que (3 × 2) + 64 = 70.
é divisível por 7 a soma do quíntuplo do último dígito com o número formado pelos dígitos restantes. 364 é divisível por 7, já que 36 + (4 x 5) = 56.
é divisível por 7 a diferença entre o número formado ao desconsiderar o último dígito e o dobro deste dígito. 364 é divisível por 7, pois 36 − (4 x 2) = 28.
8 vale qualquer dessas propriedades:
o dígito das centenas é par e o número formado pelos dois últimos dígitos é divisível por 8. 12 345 624 é divisível por 8, pois 6 é par e 24 = 3 x 8.
o dígito das centenas é ímpar e o número formado pelos dois últimos dígitos, somado com 4 é divisível por 8. 12 352, é múltiplo de 8, já que 3 é ímpar e 52 + 4 = 56 = 7 x 8.
é divisível por 8 a soma do último dígito com o dobro do número formado pelos demais. 136 é divisível por 8, uma vez que (13 × 2) + 6 = 32.
9 é divisível por 9 a soma dos seus dígitos.[3] 3 753 é múltiplo de 9, pois 3 + 7 + 5 + 3 = 18 e 1 + 8 = 9
10 o último dígito é 0. 135790 é múltiplo de 10, pois seu último dígito é 0.
11 vale qualquer dessas propriedades:
é divisível por 11 a soma alternada dos seus dígitos. 918 082 é múltiplo de 11, pois 9 - 1 + 8 - 0 + 8 - 2 = 22 = 2 x 11.
é múltiplo de 11 a soma dos números formados pelos blocos de dois dígitos (da direita para a esquerda). 627 é múltiplo de 11, pois 6 + 27 = 33 = 3 x 11.
é múltiplo de 11 a diferença entre o número formado ao desconsiderar o último dígito e o último dígito. 627 é múltiplo de 11, já que 62 - 7 = 55 = 5 x 11..


Por que esses critérios funcionam?[editar | editar código-fonte]

Diante de tantas regras, é natural não acreditar de imediato que elas sejam todas infalíveis. Você já deve ter feito (ou ouvido alguém fazer) pelo menos uma pergunta desse tipo:

Quem disse que esses macetes funcionam sempre?
Por acaso alguém já testou algum deles para todos os números, e viu que nunca falham?
Quem é que impôs essas regras?
É possível encontrar um critério para os números que não estão na tabela?

Antes de responder a essas e outras perguntas do gênero, é interessante apresentar um resultado fundamental da teoria de números. O enunciado não deve parecer uma grande novidade, pois formaliza o tão conhecido algoritmo de divisão, aquele processo utilizado ao dividir dois números manualmente. Se estiver um pouco "enferrujado", experimente calcular o resultado da divisão de 39629376 por 321, para relembrar as suas primeiras aulas de matemática...

Algoritmo da divisão (de Euclides)[editar | editar código-fonte]

Teorema

Se a e b são números inteiros, e b\not=0, então existe um único par de números inteiros q e r, tais que:

a = bq+r, com 0\le r < |b|

Uma formulação alternativa é a seguinte:

Dados os números inteiros a e b, ou a é múltiplo de b ou está entre dois múltiplos consecutivos de b.

Wikipedia
A Wikipédia tem mais sobre este assunto:
Princípio da boa ordenação
Demonstração
Considere inicialmente que a>0.

Se X = \{ a-bt: t\in \mathbb{Z}\} \subseteq \mathbb{Z}, então X' = X \cap \mathbb{N} \not=\emptyset (pois para t=0 tem-se a-bt = a >0).

Logo, pelo princípio da boa ordenação, X' possui um menor elemento r = min (X').

Como r \in X', segue que r = a-bq, para algum inteiro q, e r\ge 0.

Suponha que 0<b. Neste caso, segue que r<b.

De fato, se ocorresse r\ge b, então r' = r-b = (a-bq)-b = a-b(q+1) seria elemento de X'.
Além disso, 0\le r' e r'<r (pois 0<b), donde r não seria o menor elemento de X'.

Por outro lado, se b\le 0, então o algoritmo pode ser aplicado a a e -b (que não é negativo), obtendo:

a = (-b)q+r = b(-q)+r, com 0\le r<-b=|b|


Quanto à unicidade do quociente e do resto, pode-se proceder da seguinte maneira: Seja a = mq+r = mq'+r' , com 0\le r <m e 0\le r' <m. Nestas condições, tem-se:

0 = m(q-q') + (r-r'), ou seja, r-r' \in m\mathbb{Z}

Por outro lado, como o valor de cada resto está entre 0 e m, sua diferença também está. Isto significa que:

r'-r\le r' < m
r-r'\le r < m

Logo,

|r'-r| < m

Mas o único elemento de m\mathbb{Z} com módulo menor que m é o 0. Assim, r'-r = 0 implica r'= r.

Consequentemente, de mq+r = mq'+r' se conclui que mq = mq', que equivale a q = q' , pois m \not = 0.


Um último passo antes de apresentar a justificativa formal para os critérios de divisibilidade mostrados anteriormente é entender como funciona o sistema de numeração decimal.

Sistemas de numeração[editar | editar código-fonte]

Conforme é ensinado nos primeiros anos de escola, um número como 726 representa a soma de 7 centenas com 2 dezenas e 6 unidades, ou seja,

726 = \mathbf{7}\cdot 100 + \mathbf{2}\cdot 10 + \mathbf{6}\cdot 1

Em geral, cada número inteiro não negativo possui uma única representação decimal a_n \ldots a_2 a_1 a_0. Este é um resultado de extrema utilidade no cotidiano, pois é graças a tal sistema de numeração que estão a disposição algoritmos tão simples para a realização de adições, subtrações, multiplicações e divisões. Ou você é capaz de se imaginar realizando uma divisão de 646 por 38 utilizando o sistema de numeração inventado pelos romanos? (Experimente: DCXLVI dividido por XXXVIII é igual a...)

Dada a importância do sistema de numeração decimal, é justo enunciar e justificar precisamente o seu funcionamento. Isso é feito no próximo teorema, que garante a existência de representações posicionais em qualquer base, não apenas na base 10.

Teorema

Dado um numero inteiro b (chamado de base), maior do que a unidade, cada inteiro positivo a pode ser escrito de uma única maneira como

a = a_n \cdot b^n + a_{n-1} \cdot b^{n-1} + \ldots + a_1 \cdot b + a_0
de modo que cada inteiro a_i verifique a_i \in [0, b), a_n \not = 0 e n\ge 0.

Utilizando o algoritmo da divisão é possível obter cada dígito de uma tal representação, um após o outro, começando pelo dígito das unidades. De fato, ao dividir o número em questão pelo valor da base, consegue-se:

a = q_0 b + a_0

Fazendo o mesmo com q_0, resulta:

q_0 = q_1 b + a_1

Repetindo o procedimento com cada quociente q_i, será construída uma sequência decrescente:

a > q_0 > q_1 > q_2 > \ldots

Certamente algum termo da sequência deve ser igual a unidade, pois todos são números inteiros e nenhum deles é negativo. Então considere que q_n = 1, ou seja, que o algoritmo da divisão fornece q_{n-1} = 1 \cdot b + 0. Neste ponto o processo pode ser interrompido, e nota-se que:

a = q_0 b + a_0
=(q_1 b + a_1)b + a_0 =q_1\cdot b^2 + a_1\cdot b^1 + a_0
=((q_2 b + a_2) b + a_1)b + a_0 =q_2\cdot b^3 + a_2\cdot b^2 + a_1\cdot b^1 + a_0
\vdots
=(( ??? ) b + a_1)b + a_0 =a_n\cdot b^n + \ldots + a_2\cdot b^2 + a_1\cdot b^1 + a_0

Observações[editar | editar código-fonte]

  • Quando a base não é 10, é comum usar a notação (a_n \ldots a_2 a_1 a_0)_b para explicitar esse fato.
  • Os sistemas que utilizam a base 2 (binário), a base 8 (octal) e a base 16 (hexadecimal) são particularmente úteis na informática e na eletrônica digital.
  • O sistema de numeração com base 60 (sexagesimal) foi inventado pelos Sumérios, e ainda é utilizado para a contagem de minutos e segundos, tanto para indicar períodos de tempo quanto para medir ângulos.

Exemplos[editar | editar código-fonte]

De posse dessas informações, já é possível demonstrar a validade dos critérios de divisibilidade dados pela tabela anterior. Nos próximos exemplos serão demonstrados alguns desses critérios. Os demais são deixados como exercício para o leitor.

Divisibilidade por 2[editar | editar código-fonte]

Proposição

Um inteiro não negativo é par, e somente se, o dígito das unidades é par.

Demonstração
Considere um número inteiro positivo cuja representação decimal é m = a_n \ldots a_2 a_1 a_0. Para mostrar que 2|m se, e somente se, 2|a_0, note que:
10 = 2 \times 5
100 = 2 \times 50
\ldots

e em geral:

10^n = 2 \times 5\times 10^{n-1}

Portanto:

m = a_n 10^n + \ldots + a_2 10^2 + a_1 10 + a_0 = 2 \times ( 5 a_n 10^{n-1} + \ldots + 5 a_2 10^1 + 5 a_1 ) + a_0

Assim,

m = 2 k + a_0, com k = 5 a_n 10^{n-1} + \ldots + 5 a_2 10^1 + 5 a_1

Deste modo, se 2|m, então 2|m- 2k = a_0.

Reciprocamente, se 2|a_0 tem-se 2|2k + a_0 = m.



Divisibilidade por 3[editar | editar código-fonte]

Proposição

Um inteiro não negativo é múltiplo de 3 se, e somente se, a soma de seus dígitos é múltiplo de 3.

Demonstração
Seja m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k um número inteiro positivo. Como no exemplo anterior, o principal é considerar as potências de 10 e os restos de suas divisões por 3.

Primeiramente, note que:

10^k = \underbrace{ 9 \ldots 99 }_{k-1} + 1 = 3 \times \underbrace{ 3 \ldots 33 }_{k-1} + 1 = 3 T_{k-1} + 1

onde T_k = \underbrace{ 3 \ldots 33 }_{k} = 3\times \sum_{i=0}^{k-1} 10^i é o número que possui todos os seus k dígitos iguais a 3. Esta última igualdade é devida à fórmula clássica para a soma dos n primeiros termos de uma progressão geométrica).

Substituindo essas potências de 10, obtem-se:

m = \sum_{k=0}^{n} a_k 10^k = \sum_{k=0}^{n} a_k (3 T_{k-1} + 1) = \sum_{k=0}^{n} 3 a_k T_{k-1} + a_k = 3 \sum_{k=0}^{n} a_k T_{k-1} + \sum_{k=0}^{n} a_k

ou seja,

m = 3 T + S, onde T = \sum_{k=0}^{n} a_k T_{k-1} e S = \sum_{k=0}^{n} a_k é a soma dos dígitos de m.

Deste modo, se 3|m, então 3|m-3T = S.

Analogamente, se 3|S tem-se 3|3T + S = m.

Divisibilidade por 11[editar | editar código-fonte]

Proposição

Um inteiro não negativo é divisível por 11 se, e somente se, a soma alternada dos seus dígitos é divisível por 11.

Demonstração
Como antes, considere m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k um número inteiro positivo. Pode-se proceder como antes para obter o resultado. Primeiramente, observe a relação entre as primeiras potências de 10 e o número 11:
10^0 = 11\times   0 + 1
10^1 = 11\times   1 - 1
10^2 = 11\times   9 + 1
10^3 = 11\times  91 - 1
10^4 = 11\times 909 + 1

É razoável esperar que o padrão continue, ou seja, que nas potências pares se tenha 10^k = 11\times B_k + 1 para algum inteiro B_k, e nas potências ímpares se tenha 10^k = 11\times B_k - 1 para algum inteiro B_k.

No entanto, como a intuição as vezes falha (o próprio Fermat foi vítima de sua intuição, se enganando ao afirmar que todo número da forma F_{n} = 2^{2^{n}} + 1 é primo), é necessário provar que o padrão se repete, qualquer que seja o expoente. Em símbolos, é preciso mostrar que:

10^k = 11\times B_k + (-1)^k , para algum inteiro B_k.

Para tal usaremos o binómio de Newton:

10^k=(11-1)^k = \sum_{i=0}^{k} \binom{k}{i}11^i(-1)^{k-i} = (-1)^k+11(-1)^{k-1}+ 11^2\frac{k!}{2!(k-2)!}(-1)^{k-2}+\ldots+11^k=
(-1)^k+11\left((-1)^{k-1}+ 11\frac{k!}{2!(k-2)!}(-1)^{k-2}+\ldots+11^{k-1}\right),

ou seja, 10^k=(-1)^k + 11\times B_k,onde B_k=\sum_{i=1}^{k} \binom{k}{i}11^{i-1}(-1)^{k-i}.

Uma vez que o padrão está justificado, o raciocínio é o mesmo do caso anterior:

m = \sum_{k=0}^{n} a_k 10^k = \sum_{k=0}^{n} a_k (11\times B_k + (-1)^k) = \sum_{k=0}^{n} 11 a_k B_k + a_k(-1)^k = 11 \sum_{k=0}^{n} a_k B_k + \sum_{k=0}^{n} a_k(-1)^k

ou seja,

m = 11 B + A, onde B = \sum_{k=0}^{n} a_k B_k e A = \sum_{k=0}^{n} a_k(-1)^k é a soma alternada dos dígitos de m.

Deste modo, se 11|m, então 11|m-11B = A.

Analogamente, se 11|A tem-se 11|11B + A = m.


Exercícios[editar | editar código-fonte]

  1. Justifique a validade de cada uma das propriedades da divisibilidade apresentadas no texto.

Notas[editar | editar código-fonte]

  1. Veja a fatoração de 1294 e outras informações sobre este número no Wolfram Alpha (em inglês).
  2. Conforme diversos livros
  3. Conforme diversos livros