Teoria de números/Divisibilidade: diferenças entre revisões
[edição não verificada] | [edição verificada] |
m hack obsoleto: as fórmulas já aparecem em PNG e não há mais como exibi-las em HTML nem MathML (futuramente teremos MathJax) |
|||
Linha 21: | Linha 21: | ||
|width="80px"| 3 |
|width="80px"| 3 |
||
|width="80px"| 4 |
|width="80px"| 4 |
||
|width="80px"| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots |
|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> |
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}-1-1</math> |
||
Linha 30: | 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</math> |
||
|<math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(1+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>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots</math> |
||
|} |
|} |
||
</center> |
</center> |
||
Linha 57: | Linha 57: | ||
|width="80px"| 11 |
|width="80px"| 11 |
||
|width="80px"| 12 |
|width="80px"| 12 |
||
|width="80px"| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots |
|width="80px"| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots</math> |
||
|- |
|- |
||
| bloco básico |
| bloco básico |
||
| bloco básico |
| bloco básico |
||
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2 |
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 2</math> |
||
| bloco básico |
| bloco básico |
||
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 3 |
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 3</math> |
||
| bloco básico |
| bloco básico |
||
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 2 |
| <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>\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>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}2\cdot 5</math> |
||
| bloco básico |
| bloco básico |
||
| <math>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}(2\cdot 2)\cdot 3 |
| <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>\definecolor{cinza}{RGB}{249,249,249}\pagecolor{cinza}\ldots</math> |
||
|} |
|} |
||
</center> |
</center> |
||
Linha 84: | Linha 84: | ||
{{Definição |
{{Definição |
||
|Dados os inteiros <math>a |
|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''. |
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} |
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>R=\{(a,b) | a \mbox{ divide } b \}</math> |
||
Nesses termos, quando <math>(a,b) \in R</math> costuma-se dizer que ''<math>a |
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 == |
== Propriedades da divisibilidade == |
||
Linha 100: | Linha 100: | ||
:{| border="0" |
:{| border="0" |
||
|- |
|- |
||
|1. <math>a|a |
|1. <math>a|a </math> || ([[w:reflexividade|reflexividade]]) |
||
|- |
|- |
||
|2. <math>a|b |
|2. <math>a|b </math> e <math>b|c</math> implica <math>a|c</math> || ([[w:transitividade|transitividade]]) |
||
|- |
|- |
||
|3. <math>a|b |
|3. <math>a|b</math> e <math>b|a</math> implica <math>a=b</math> ou <math>a=-b</math> || |
||
|- |
|- |
||
|4. <math>c|a |
|4. <math>c|a</math> e <math>c|b</math> implica <math>c|ra + sb</math> || ([[w:linearidade|linearidade]]) |
||
|- |
|- |
||
|5. <math>a|b |
|5. <math>a|b</math> e <math>c|d</math> implica <math>ac|bd</math> || |
||
|- |
|- |
||
|6. <math>a|b |
|6. <math>a|b</math> implica <math>ac|bc</math> || ([[w:multiplicatividade|multiplicatividade]]) |
||
|- |
|- |
||
|7. <math>ac|bc |
|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 |
|8. <math>1|a</math> || (<math>1</math> divide todo número inteiro) |
||
|- |
|- |
||
|9. <math>a|0 |
|9. <math>a|0</math> || (todo número inteiro divide zero) |
||
|- |
|- |
||
|10. <math>0|a |
|10. <math>0|a</math> implica <math>a=0</math> || (zero só divide zero) |
||
|- |
|- |
||
|11. <math>a|1 |
|11. <math>a|1</math> implica <math>a=\pm 1</math> || (os divisores de 1 são 1 e -1) |
||
|- |
|- |
||
|12. <math>a|b |
|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 |
|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 |
{{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: | 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>). |
* 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 |
* 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 == |
== Critérios de divisibilidade no sistema de numeração decimal == |
||
Linha 243: | Linha 243: | ||
{{Teorema |
{{Teorema |
||
|Se <math>a |
|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>a = bq+r</math>, com <math>0\le r\le |b|</math> |
||
}} |
}} |
||
Uma formulação alternativa é a seguinte: |
Uma formulação alternativa é a seguinte: |
||
''Dados os números inteiros <math>a |
''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}} |
{{Wikipedia|Princípio da boa ordenação}} |
||
{{Demonstração |
{{Demonstração |
||
|Considere inicialmente que <math>a>0 |
|Considere inicialmente que <math>a>0</math>. |
||
Se <math>X = \{ a-bt: t\in \mathbb{Z}\} \subseteq \mathbb{Z} |
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' |
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' |
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 |
Suponha que <math>0<b</math>. Neste caso, segue que <math>r<b</math>. |
||
:De fato, se ocorresse <math>r\ge b |
: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' |
: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 |
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>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: |
Quanto à unicidade do quociente e do resto, pode-se proceder da seguinte maneira: |
||
Seja <math>a = mq+r = mq'+r' |
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>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 |
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>r'-r\le r' < m </math> |
||
:<math>r-r'\le r < m |
:<math>r-r'\le r < m </math> |
||
Logo, |
Logo, |
||
:<math>|r'-r| < m |
:<math>|r'-r| < m </math> |
||
Mas o único elemento de <math>m\mathbb{Z} |
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' |
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: | 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, |
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>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 |
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. |
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 |
{{Teorema |
||
|Dado um numero inteiro <math>b |
|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>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 |
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}} |
{{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: |
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>a = q_0 b + a_0</math> |
||
Fazendo o mesmo com <math>q_0 |
Fazendo o mesmo com <math>q_0</math>, resulta: |
||
:<math>q_0 = q_1 b + a_1 |
:<math>q_0 = q_1 b + a_1</math> |
||
Repetindo o procedimento com cada quociente <math>q_i |
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>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 |
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>a</math> |
||
|<math>= q_0 b + a_0 |
|<math>= q_0 b + a_0</math> |
||
| |
| |
||
|- |
|- |
||
| |
| |
||
|<math>=(q_1 b + a_1)b + a_0 |
|<math>=(q_1 b + a_1)b + a_0</math> |
||
|<math>=q_1\cdot b^2 + a_1\cdot b^1 + a_0 |
|<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>=((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>=q_2\cdot b^3 + a_2\cdot b^2 + a_1\cdot b^1 + a_0</math> |
||
|- |
|- |
||
| |
| |
||
|<math>\vdots |
|<math>\vdots</math> |
||
| |
| |
||
|- |
|- |
||
| |
| |
||
|<math>=(( ??? ) b + a_1)b + a_0 |
|<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>=a_n\cdot b^n + \ldots + a_2\cdot b^2 + a_1\cdot b^1 + a_0</math> |
||
|} |
|} |
||
{{esboço}} |
{{esboço}} |
||
Linha 335: | Linha 335: | ||
=== Observações === |
=== Observações === |
||
* Quando a base não é 10, é comum usar a notação <math>(a_n \ldots a_2 a_1 a_0)_b |
* 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. |
* 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. |
* 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: | Linha 349: | ||
}} |
}} |
||
{{Demonstração |
{{Demonstração |
||
|Considere um número inteiro positivo cuja representação decimal é <math>m = a_n \ldots a_2 a_1 a_0 |
|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>10 = 2 \times 5</math> |
||
:<math>100 = 2 \times 50 |
:<math>100 = 2 \times 50</math> |
||
:<math>\ldots |
:<math>\ldots</math> |
||
e em geral: |
e em geral: |
||
:<math>10^n = 2 \times 5\times 10^{n-1} |
:<math>10^n = 2 \times 5\times 10^{n-1}</math> |
||
Portanto: |
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>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, |
Assim, |
||
:<math>m = 2 k + a_0 |
:<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 |
Deste modo, se <math>2|m</math>, então <math>2|m- 2k = a_0</math>. |
||
Reciprocamente, se <math>2|a_0 |
Reciprocamente, se <math>2|a_0</math> tem-se <math>2|2k + a_0 = m</math>. |
||
}} |
}} |
||
Linha 379: | Linha 379: | ||
}} |
}} |
||
{{Demonstração |
{{Demonstração |
||
|Seja <math>m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k |
|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: |
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>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 |
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: |
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>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, |
ou seja, |
||
:<math>m = 3 T + S |
:<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 |
Deste modo, se <math>3|m</math>, então <math>3|m-3T = S</math>. |
||
Analogamente, se <math>3|S |
Analogamente, se <math>3|S</math> tem-se <math>3|3T + S = m</math>. |
||
}} |
}} |
||
Linha 403: | Linha 403: | ||
}} |
}} |
||
{{Demonstração |
{{Demonstração |
||
|Como antes, considere <math>m = a_n \ldots a_2 a_1 a_0 = \sum_{k=0}^{n} a_k 10^k |
|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>10^0 = 11\times 0 + 1 </math> |
||
:<math>10^1 = 11\times 1 - 1 |
:<math>10^1 = 11\times 1 - 1 </math> |
||
:<math>10^2 = 11\times 9 + 1 |
:<math>10^2 = 11\times 9 + 1 </math> |
||
:<math>10^3 = 11\times 91 - 1 |
:<math>10^3 = 11\times 91 - 1 </math> |
||
:<math>10^4 = 11\times 909 + 1 |
:<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 |
É 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: |
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>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}}: |
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> |
:<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: | Linha 420: | ||
Uma vez que o padrão está justificado, o raciocínio é o mesmo do caso anterior: |
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>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, |
ou seja, |
||
:<math>m = 3 B + A |
:<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 |
Deste modo, se <math>11|m</math>, então <math>11|m-11B = A</math>. |
||
Analogamente, se <math>11|A |
Analogamente, se <math>11|A</math> tem-se <math>11|11B + A = m</math>. |
||
}} |
}} |
Revisão das 20h29min de 27 de fevereiro de 2012
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 , sendo que:
O conjunto pode ser definido formalmente a partir do conjunto dos números naturais 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 | |
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:
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 é muito mais sofisticada. Veja alguns exemplos:
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
bloco básico | bloco básico | bloco básico | bloco básico | bloco básico |
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: , 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
- Definição
Dados os inteiros e , diz-se que " divide " e escreve-se , se existe um inteiro tal que . Alternativamente, pode ser lido como " é divisor de ", " é um fator de " ou " é múltiplo de ". Quando não se tem , escreve-se .
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 é qualquer subconjunto do conjunto das partes de , . No caso da divisibilidade, tem-se:
Nesses termos, quando costuma-se dizer que está relacionado com escrevendo-se .
Propriedades da divisibilidade
A relação de divisibilidade possui as seguintes propriedades, para quaisquer (salvo indicação em contrário) inteiros :
1. (reflexividade) 2. e implica (transitividade) 3. e implica ou 4. e implica (linearidade) 5. e implica 6. implica (multiplicatividade) 7. e implica (lei do cancelamento) 8. ( divide todo número inteiro) 9. (todo número inteiro divide zero) 10. implica (zero só divide zero) 11. implica (os divisores de 1 são 1 e -1) 12. e implica (compatibilidade com a ordem "") 13. e implica
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 "". Quando são considerados apenas os números não-negativos (os elementos de ) a conclusão é apenas "", e as propriedades de 1 a 3 fazem da divisibilidade uma relação de ordem parcial sobre . No entanto, essa não é uma ordem total, pois nem todo par de elementos em é comparável, ou seja, existem inteiros não negativos e , para os quais não se tem nem .
- Frequentemente é mais prático trabalhar apenas com o conjunto dos números naturais (o subconjunto dos inteiros não-negativos ) ou com os números naturais não nulos (os inteiros positivos ).
- As propriedades 1 e 8 garantem que todo número inteiro não negativo , diferente de , possui ao menos dois divisores, chamados de divisores triviais: e . 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
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 | ||
é 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 | ||
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 | ||
é 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?
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)
- Teorema
Se e são números inteiros, e , então existe um único par de números inteiros e , tais que:
- , com
Uma formulação alternativa é a seguinte:
Dados os números inteiros e , ou é múltiplo de ou está entre dois múltiplos consecutivos de .
Demonstração |
---|
Considere inicialmente que .
Se , então (pois para tem-se ). Logo, pelo princípio da boa ordenação, possui um menor elemento . Como , segue que , para algum inteiro , e . Suponha que . Neste caso, segue que .
Por outro lado, se , então o algoritmo pode ser aplicado a e (que não é negativo), obtendo:
Por outro lado, como o valor de cada resto está entre e , sua diferença também está. Isto significa que: Logo, Mas o único elemento de com módulo menor que é o . Assim, implica . Consequentemente, de se conclui que , que equivale a , pois .
|
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
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,
Em geral, cada número inteiro não negativo possui uma única representação decimal . 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 (chamado de base), maior do que a unidade, cada inteiro positivo pode ser escrito de uma única maneira como
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:
Fazendo o mesmo com , resulta:
Repetindo o procedimento com cada quociente , será construída uma sequência decrescente:
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 , ou seja, que o algoritmo da divisão fornece . Neste ponto o processo pode ser interrompido, e nota-se que:
Esta página é somente um esboço. Ampliando-a você ajudará a melhorar o Wikilivros. |
Observações
- Quando a base não é 10, é comum usar a notação 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
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
- 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 é . Para mostrar que se, e somente se, , note que:
e em geral: Portanto: Assim,
Deste modo, se , então . Reciprocamente, se tem-se .
|
Divisibilidade por 3
- 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 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: onde é o número que possui todos os seus dígitos iguais a 3. Esta última igualdade é devida à fórmula clássica para a soma dos primeiros termos de uma progressão geométrica). Substituindo essas potências de 10, obtem-se: ou seja,
Deste modo, se , então . Analogamente, se tem-se . |
Divisibilidade por 11
- 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 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:
É razoável esperar que o padrão continue, ou seja, que nas potências pares se tenha para algum inteiro , e nas potências ímpares se tenha para algum inteiro . 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 é primo), é necessário provar que o padrão se repete, qualquer que seja o expoente. Em símbolos, é preciso mostrar que:
Para tal usaremos o binómio de Newton: ou seja, onde Uma vez que o padrão está justificado, o raciocínio é o mesmo do caso anterior: ou seja,
Deste modo, se , então . Analogamente, se tem-se .
|
Exercícios
- Justifique a validade de cada uma das propriedades da divisibilidade apresentadas no texto.
Notas
- ↑ Veja a fatoração de 1294 e outras informações sobre este número no Wolfram Alpha (em inglês).
- ↑ Conforme diversos livros
- ↑ Conforme diversos livros