Teoria de números/Divisibilidade: diferenças entre revisões

[edição não verificada][edição verificada]
Conteúdo apagado Conteúdo adicionado
Linha 21:
|width="80px"| 3
|width="80px"| 4
|width="80px"| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots\,\!</math>
|-
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}-1-1</math>
Linha 30:
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(1+1)+1</math>
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(1+1)+(1+1)</math>
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots\,\!</math>
|}
</center>
Linha 57:
|width="80px"| 11
|width="80px"| 12
|width="80px"| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots\,\!</math>
|-
| bloco básico
| bloco básico
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2\,\!</math>
| bloco básico
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 3\,\!</math>
| bloco básico
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 2\,\!</math>
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}3\cdot 3\,\!</math>
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 5\,\!</math>
| bloco básico
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 3\,\!</math>
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots\,\!</math>
|}
</center>
Linha 84:
 
{{Definição
|Dados os inteiros <math>a\,\!</math> e <math>b\,\!</math>, diz-se que "<math>a\,\!</math> divide <math>b\,\!</math>" e escreve-se <math>a|b \,\!</math>, se existe um inteiro <math>c\,\!</math> tal que <math>b=a\cdot c</math>. Alternativamente, <math>a|b</math> pode ser lido como "<math>a\,\!</math> é divisor de <math>b\,\!</math>", "<math>a\,\!</math> é um fator de <math>b</math>" ou "<math>b</math> é múltiplo de <math>a</math>". Quando não se tem <math>a|b\,\!</math>, escreve-se <math>a\not|b</math>.
}}
 
O conceito apresentado acima define uma [[w:relação binária|relação binária]] no conjunto dos números inteiros: a ''divisibilidade''.
 
Lembre-se que uma relação binária sobre <math>\mathbb{Z}\,\!</math> é qualquer subconjunto <math>R\,\!</math> do conjunto das partes de <math>\mathbb{Z}</math>, <math>P(\mathbb{Z})</math>. No caso da divisibilidade, tem-se:
:<math>R=\{(a,b) | a \mbox{ divide } b \}\,\!</math>
 
Nesses termos, quando <math>(a,b) \in R</math> costuma-se dizer que ''<math>a\,\!</math> está relacionado com <math>b\,\!</math>'' escrevendo-se <math>a R b\,\!</math>.
 
== Propriedades da divisibilidade ==
Linha 100:
:{| border="0"
|-
|1. <math>a|a \,\!</math> || ([[w:reflexividade|reflexividade]])
|-
|2. <math>a|b \,\!</math> e <math>b|c\,\!</math> implica <math>a|c\,\!</math> || ([[w:transitividade|transitividade]])
|-
|3. <math>a|b\,\!</math> e <math>b|a\,\!</math> implica <math>a=b\,\!</math> ou <math>a=-b\,\!</math> ||
|-
|4. <math>c|a\,\!</math> e <math>c|b\,\!</math> implica <math>c|ra + sb\,\!</math> || ([[w:linearidade|linearidade]])
|-
|5. <math>a|b\,\!</math> e <math>c|d\,\!</math> implica <math>ac|bd\,\!</math> ||
|-
|6. <math>a|b\,\!</math> implica <math>ac|bc\,\!</math> || ([[w:multiplicatividade|multiplicatividade]])
|-
|7. <math>ac|bc\,\!</math> e <math>c\not = 0\,\!</math> implica <math>a|b\,\!</math> || ([[w:lei do cancelamento|lei do cancelamento]])
|-
|8. <math>1|a\,\!</math> || (<math>1</math> divide todo número inteiro)
|-
|9. <math>a|0\,\!</math> || (todo número inteiro divide zero)
|-
|10. <math>0|a\,\!</math> implica <math>a=0\,\!</math> || (zero só divide zero)
|-
|11. <math>a|1\,\!</math> implica <math>a=\pm 1\,\!</math> || (os divisores de 1 são 1 e -1)
|-
|12. <math>a|b\,\!</math> e <math>b\not =0\,\!</math> implica <math>|a|\le |b|\,\!</math> || (compatibilidade com a ordem "<math>\le </math>")
|-
|13. <math>a|b\,\!</math> e <math>a\not = 0\,\!</math> implica <math>(b/a)|b\,\!</math> ||
|}
{{Demonstração|A demonstração dessas propriedades é deixada a cargo do leitor. Deste modo, sinta-se convidado a melhorar este texto {{#ifeq:{{SUBPAGENAME}}|Imprimir
Linha 136:
* Frequentemente é mais prático trabalhar apenas com o conjunto dos números naturais <math>\mathbb{N}</math> (o subconjunto dos inteiros não-negativos <math>\mathbb{Z}_+</math>) ou com os números naturais não nulos <math>\mathbb{N}^*</math> (os inteiros positivos <math>\mathbb{Z}_+^*</math>).
 
* As propriedades 1 e 8 garantem que todo número inteiro não negativo <math>a</math>, diferente de <math>1</math>, possui ao menos dois divisores, chamados de '''divisores triviais''': <math>1\,\!</math> e <math>a\,\!</math>. Os números que possuem ''somente estes divisores'' são de grande interesse na teoria de números, e serão estudados no [[Teoria de números/Números primos|próximo capítulo]].
 
== Critérios de divisibilidade no sistema de numeração decimal ==
Linha 243:
 
{{Teorema
|Se <math>a\,\!</math> e <math>b\,\!</math> são números inteiros, e <math>b\not=0\,\!</math>, então existe um único par de números inteiros <math>q\,\!</math> e <math>r\,\!</math>, tais que:
:<math>a = bq+r\,\!</math>, com <math>0\le r\le |b|\,\!</math>
}}
Uma formulação alternativa é a seguinte:
 
''Dados os números inteiros <math>a\,\!</math> e <math>b\,\!</math>, ou <math>a\,\!</math> é múltiplo de <math>b\,\!</math> ou está entre dois múltiplos consecutivos de <math>b\,\!</math>.''
{{Wikipedia|Princípio da boa ordenação}}
{{Demonstração
|Considere inicialmente que <math>a>0\,\!</math>.
 
Se <math>X = \{ a-bt: t\in \mathbb{Z}\} \subseteq \mathbb{Z}\,\!</math>, então <math>X' = X \cap \mathbb{N} \not=\emptyset\,\!</math> (pois para <math>t=0\,\!</math> tem-se <math>a-bt = a >0\,\!</math>).
 
Logo, pelo ''princípio da boa ordenação'', <math>X'\,\!</math> possui um menor elemento <math>r = min (X')\,\!</math>.
 
Como <math>r \in X'\,\!</math>, segue que <math>r = a-bq\,\!</math>, para algum inteiro <math>q\,\!</math>, e <math>r\ge 0\,\!</math>.
 
Suponha que <math>0<b\,\!</math>. Neste caso, segue que <math>r<b\,\!</math>.
:De fato, se ocorresse <math>r\ge b\,\!</math>, então <math>r' = r-b = (a-bq)-b = a-b(q+1)\,\!</math> seria elemento de <math>X'\,\!</math>.
:Além disso, <math>0\le r'\,\!</math> e <math>r'<r\,\!</math> (pois <math>0<b\,\!</math>), donde <math>r\,\!</math> não seria o menor elemento de <math>X'\,\!</math>.
 
Por outro lado, se <math>b\le 0\,\!</math>, então o algoritmo pode ser aplicado a <math>a\,\!</math> e <math>-b\,\!</math> (que não é negativo), obtendo:
:<math>a = (-b)q+r = b(-q)+r\,\!</math>, com <math>0\le r<-b=|b|\,\!</math>
 
 
Quanto à unicidade do quociente e do resto, pode-se proceder da seguinte maneira:
Seja <math>a = mq+r = mq'+r' \,\!</math>, com <math>0\le r <m\,\!</math> e <math>0\le r' <m\,\!</math>. Nestas condições, tem-se:
:<math>0 = m(q-q') + (r-r')\,\!</math>, ou seja, <math>r-r' \in m\mathbb{Z}\,\!</math>
Por outro lado, como o valor de cada resto está entre <math>0\,\!</math> e <math>m\,\!</math>, sua diferença também está. Isto significa que:
:<math>r'-r\le r' < m \,\!</math>
:<math>r-r'\le r < m \,\!</math>
Logo,
:<math>|r'-r| < m \,\!</math>
Mas o único elemento de <math>m\mathbb{Z}\,\!</math> com módulo menor que <math>m\,\!</math> é o <math>0\,\!</math>. Assim, <math>r'-r = 0\,\!</math> implica <math>r'= r\,\!</math>.
 
Consequentemente, de <math>mq+r = mq'+r' \,\!</math> se conclui que <math>mq = mq'\,\!</math>, que equivale a <math>q = q' \,\!</math>, pois <math>m \not = 0\,\!</math>.
 
}}
Linha 286:
 
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,
:<math>726 = \mathbf{7}\cdot 100 + \mathbf{2}\cdot 10 + \mathbf{6}\cdot 1\,\!</math>
 
Em geral, cada número inteiro não negativo possui uma única representação decimal <math>a_n \ldots a_2 a_1 a_0\,\!</math>. 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 [[w:Numeração romana|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 <math>b\,\!</math> (chamado de base), maior do que a unidade, cada inteiro positivo <math>a\,\!</math> pode ser escrito de uma única maneira como
:<math>a = a_n \cdot b^n + a_{n-1} \cdot b^{n-1} + \ldots + a_1 \cdot b + a_0\,\!</math>
de modo que cada inteiro <math>a_i\,\!</math> verifique <math>a_i \in [0, b)\,\!</math>, <math>a_n \not = 0\,\!</math> e <math>n\ge 0\,\!</math>.
}}
{{Demonstração/Início}}
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:
:<math>a = q_0 b + a_0\,\!</math>
 
Fazendo o mesmo com <math>q_0\,\!</math>, resulta:
:<math>q_0 = q_1 b + a_1\,\!</math>
 
Repetindo o procedimento com cada quociente <math>q_i\,\!</math>, será construída uma sequência decrescente:
:<math>a > q_0 > q_1 > q_2 > \ldots \,\!</math>
 
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 <math>q_n = 1\,\!</math>, ou seja, que o algoritmo da divisão fornece <math>q_{n-1} = 1 \cdot b + 0\,\!</math>. Neste ponto o processo pode ser interrompido, e nota-se que:
:{|
|-
|<math>a\,\!</math>
|<math>= q_0 b + a_0\,\!</math>
|
|-
|
|<math>=(q_1 b + a_1)b + a_0\,\!</math>
|<math>=q_1\cdot b^2 + a_1\cdot b^1 + a_0\,\!</math>
|-
|
|<math>=((q_2 b + a_2) b + a_1)b + a_0\,\!</math>
|<math>=q_2\cdot b^3 + a_2\cdot b^2 + a_1\cdot b^1 + a_0\,\!</math>
|-
|
|<math>\vdots\,\!</math>
|
|-
|
|<math>=(( ??? ) b + a_1)b + a_0\,\!</math>
|<math>=a_n\cdot b^n + \ldots + a_2\cdot b^2 + a_1\cdot b^1 + a_0\,\!</math>
|}
{{esboço}}
Linha 335:
=== Observações ===
 
* Quando a base não é 10, é comum usar a notação <math>(a_n \ldots a_2 a_1 a_0)_b\,\!</math> para explicitar esse fato.
* Os sistemas que utilizam a base 2 ([[w:Sistema binário (matemática)|binário]]), a base 8 ([[w:Sistema octal|octal]]) e a base 16 ([[w:Sistema hexadecimal|hexadecimal]]) são particularmente úteis na informática e na eletrônica digital.
* O sistema de numeração com base 60 ([[w:Sistema sexagesimal|sexagesimal]]) foi inventado pelos [[w:Sumérios|Sumérios]], e ainda é utilizado para a contagem de minutos e segundos, tanto para indicar períodos de tempo quanto para medir ângulos.
Linha 349:
}}
{{Demonstração
|Considere um número inteiro positivo cuja representação decimal é <math>m = a_n \ldots a_2 a_1 a_0\,\!</math>. Para mostrar que <math>2|m\,\!</math> se, e somente se, <math>2|a_0\,\!</math>, note que:
:<math>10 = 2 \times 5\,\!</math>
:<math>100 = 2 \times 50\,\!</math>
:<math>\ldots\,\!</math>
 
e em geral:
 
:<math>10^n = 2 \times 5\times 10^{n-1}\,\!</math>
 
Portanto:
 
:<math>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\,\!</math>
 
Assim,
 
:<math>m = 2 k + a_0\,\!</math>, com <math>k = 5 a_n 10^{n-1} + \ldots + 5 a_2 10^1 + 5 a_1\,\!</math>
 
Deste modo, se <math>2|m\,\!</math>, então <math>2|m- 2k = a_0\,\!</math>.
 
Reciprocamente, se <math>2|a_0\,\!</math> tem-se <math>2|2k + a_0 = m\,\!</math>.
 
}}
Linha 379:
}}
{{Demonstração
|Seja <math>m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k\,\!</math> 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:
:<math>10^k = \underbrace{ 9 \ldots 99 }_{k-1} + 1 = 3 \times \underbrace{ 3 \ldots 33 }_{k-1} + 1 = 3 T_{k-1} + 1\,\!</math>
 
onde <math>T_k = \underbrace{ 3 \ldots 33 }_{k} = 3\times \sum_{i=0}^{k-1} 10^i \,\!</math> é o número que possui todos os seus <math>k\,\!</math> dígitos iguais a 3. Esta última igualdade é devida à fórmula clássica para a soma dos <math>n\,\!</math> primeiros termos de uma [[Matemática elementar/Progressões#Soma Limitada|progressão geométrica]]).
 
Substituindo essas potências de 10, obtem-se:
:<math>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\,\!</math>
 
ou seja,
 
:<math>m = 3 T + S\,\!</math>, onde <math>T = \sum_{k=0}^{n} a_k T_{k-1}\,\!</math> e <math>S = \sum_{k=0}^{n} a_k\,\!</math> é a soma dos dígitos de <math>m\,\!</math>.
 
Deste modo, se <math>3|m\,\!</math>, então <math>3|m-3T = S\,\!</math>.
 
Analogamente, se <math>3|S\,\!</math> tem-se <math>3|3T + S = m\,\!</math>.
}}
 
Linha 403:
}}
{{Demonstração
|Como antes, considere <math>m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k\,\!</math> 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:
:<math>10^0 = 11\times 0 + 1 \,\!</math>
:<math>10^1 = 11\times 1 - 1 \,\!</math>
:<math>10^2 = 11\times 9 + 1 \,\!</math>
:<math>10^3 = 11\times 91 - 1 \,\!</math>
:<math>10^4 = 11\times 909 + 1 \,\!</math>
 
É razoável esperar que o padrão continue, ou seja, que nas potências pares se tenha <math>10^k = 11\times B_k + 1 \,\!</math> para algum inteiro <math>B_k\,\!</math>, e nas potências ímpares se tenha <math>10^k = 11\times B_k - 1 \,\!</math> para algum inteiro <math>B_k\,\!</math>.
 
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 [[w:Número de Fermat|número da forma <math>F_{n} = 2^{2^{n}} + 1</math>]] é [[../Números primos#Definição de número primo|primo]]), é necessário provar que o padrão se repete, qualquer que seja o expoente. Em símbolos, é preciso mostrar que:
:<math>10^k = 11\times B_k + (-1)^k \,\!</math>, para algum inteiro <math>B_k\,\!</math>.
Para tal usaremos o {{w|Binómio de Newton|binómio de Newton}}:
:<math>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=</math>
Linha 420:
 
Uma vez que o padrão está justificado, o raciocínio é o mesmo do caso anterior:
:<math>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\,\!</math>
 
ou seja,
 
:<math>m = 3 B + A\,\!</math>, onde <math>B = \sum_{k=0}^{n} a_k B_k\,\!</math> e <math>S = \sum_{k=0}^{n} a_k(-1)^k\,\!</math> é a soma alternada dos dígitos de <math>m\,\!</math>.
 
Deste modo, se <math>11|m\,\!</math>, então <math>11|m-11B = A\,\!</math>.
 
Analogamente, se <math>11|A\,\!</math> tem-se <math>11|11B + A = m\,\!</math>.
 
}}