Mostrar código-fonte de Teoria de números/Divisibilidade



A ''teoria de números'' é a área da [[w:matemática|matemática]] em que é estudado o [[w:Anel (álgebra)|anel]] dos números inteiros.
O conjunto dos números inteiros é denotado por <math>\mathbb{Z}</math>, sendo que:
:<math>\mathbb{Z} = \{ \ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \}</math>

O conjunto <math>\mathbb{Z}</math> pode ser definido formalmente a partir do conjunto dos números naturais <math>\mathbb{N} = \{0, 1, 2, 3, \ldots \}</math> e estes, a partir dos ''[[w:Axiomas de Peano|axiomas de Peano]]''. Para maiores detalhes sobre o assunto pode ser consultado o "[[Álgebra abstrata/Números naturais|capítulo específico]]" do wikilivro sobre [[álgebra abstrata]], ou o livro de [[../Bibliografia#Milies & Coelho (2003)|Milies & Coelho (2003)]].

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

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

<center>
{| class="wikitable" style="text-align:center"
|-
|width="80px"| -2
|width="80px"| -1
|width="80px"| 0
|width="80px"| 1
|width="80px"| 2
|width="80px"| 3
|width="80px"| 4
|width="80px"| <math>\ldots</math>
|-
|<math>-1-1</math>
|<math>\mathbf{-1}</math>
|<math>1-1</math>
|<math>\mathbf{1}</math>
|<math>1+1</math>
|<math>(1+1)+1</math>
|<math>(1+1)+(1+1)</math>
|<math>\ldots</math>
|}
</center>

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 [[w:associatividade|associatividade]] e a existência de [[w:elemento oposto|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:
:<math>\mathbf{5}=2+2+1=(1+1)+(1+1)+1</math>
:<math>\mathbf{5}=2+1+2=(1+1)+1+(1+1)</math>
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 <math>\mathbb{Z}</math> é muito mais sofisticada. Veja alguns exemplos:

<center>
{| class="wikitable" style="text-align:center"
|-
|width="80px"| 2
|width="80px"| 3
|width="80px"| 4
|width="80px"| 5
|width="80px"| 6
|width="80px"| 7
|width="80px"| 8
|width="80px"| 9 
|width="80px"| 10
|width="80px"| 11
|width="80px"| 12
|width="80px"| <math>\ldots</math>
|-
| bloco básico
| bloco básico
| <math>2\cdot 2</math>
| bloco básico
| <math>2\cdot 3</math>
| bloco básico
| <math>(2\cdot 2)\cdot 2</math>
| <math>3\cdot 3</math>
| <math>2\cdot 5</math>
| bloco básico
| <math>(2\cdot 2)\cdot 3</math>
| <math>\ldots</math>
|}
</center>

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: <math>6=2\cdot 3</math>, <math>10=2\cdot 5</math> 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 <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 ==

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

:{| 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/Início}} 
1. Como <math>a = 1.a</math> segue da definição que <math>a|a </math>.

2. Se <math> a | b</math> e <math> b | c </math>, então existem <math>q_1, q_2 \in \mathbb{Z}</math> tais que <math>b = aq_1</math> e <math> c = bq_2 </math>, logo <math> c = aq_1q_2 </math> e portanto <math> a|c </math>.

3. <math> a | b </math> implica que <math> a \geq b </math>. E se <math> b | a </math>, então <math> b \geq a </math>. Logo como <math> a </math> não pode ser menor que <math> b </math> e <math> b </math> não pode ser menor que <math> a </math> ao mesmo tempo, temos que <math> a = b </math>. <math> a = -b </math> e <math> -b = a </math> também são possíveis, já que a diferença entre <math> b/a </math> e <math> b/-a </math> é somente o sinal do quociente. O mesmo vale para <math> b/a </math> e <math> -b/a </math>.

4. Como <math> c | a </math> e <math> c | b </math> temos que <math> a = q_1c </math> e <math> b = q_2c </math> com <math>q_1</math> e <math>q_2</math> <math>\in \mathbb{Z}.</math>. Multiplicando a primeira igualdade por <math>r</math> e a segunda por <math>s</math>, temos <math>ra = rq_1c</math> e <math>sb = sq_2c</math>. Somando membro a membro e colocando <math> c </math> em evidência: <math> ra + sb = (rq_1 + sq_2)c </math> daí como <math>rq_1 + sq_2</math> é inteiro segue por definição que <math>c | ra + sb</math>. 

5. Tendo <math> a|b </math> e <math> c|d </math>, podemos transformar <math> a|b </math> e <math> c|d </math> em equações: <math> b/a = x </math> e <math> d/c = y </math>, sendo <math> x </math> e <math> y </math> os quocientes das divisões. Multiplicando ambas as equações temos: <math> bd/ac = xy </math>. Assim, já que <math> xy </math> é o quociente da divisão <math> bd/ac </math> (cujo  resto <math>= 0 </math>), temos que <math> ac|bd </math>.

6. Adicionando fatores comuns no dividendo e divisor da equação <math> b/a = x </math> (divisão exata), que implica em <math> a|b </math>; não altera o resultado da divisão, pois:
<math> bc/ac = (b/a)(c/c) </math>. Como <math> c/c = 1 </math>: <math> (b/a)(c/c) = 1(b/a) = b/a </math>. Assim <math> b/a = bc/ac </math>, que implica em <math> ac|bc </math>. 

7.  Como <math> a|b </math> vem de <math> b/a = x </math> (c = quociente), <math> ac|bc </math> vem de <math> bc/ac = x </math>, no qual podemos tirar <math> c </math> da divisão, já que ele é um fator comum no dividendo e divisor de <math> bc/ac </math>. Assim <math> ac|bc = a|c </math>.

8. <math> 1a = a </math> implica que <math> a/1 = a </math>. Assim <math> 1|a </math>.
 
9. <math> 0a = 0 </math> implica que <math> 0/a = 0 </math>. Logo <math> a|0 </math>.

10. <math> a|0 </math> pode ser transformado em <math> a/0 = x </math>. Como não existe divisão por 0 (já que tendo <math> 0x = 0 </math> e não existe número que multiplicado por 0 dê x </math>), o único número que pode estar no dividendo é 0. Logo <math>0|a</math> implica em <math> a = 0</math>.

11. <math> a|1 </math> implica que <math> 1/a </math>. Como os divisores de <math> 1 = 1; -1 </math>, temos que <math> a = \pm 1 </math>.

12. Como <math> a|b </math> e <math>b \neq 0</math> podemos escrever <math>b = aq</math> com <math>q \neq 0</math>. Assim, <math>|q| \geq 1</math> e  <math>|b|= |a||q| \geq |a|</math>.

13. Transformando <math> a|b </math> em equação, temos <math> b/a = c </math>. Utilizando-se da propriedade da divisão: tendo <math> b/a = c </math> podemos inverter o quociente e o divisor (já que <math> (quociente)(divisor) = dividendo </math>, e os fatores podem ser reordenados sem mudar o resultado) para termos: <math> b/c = a </math>. Assim:<math> b/a = c </math> e <math> b/c = a </math> implicam em <math> c|b = (b/a)|b </math>.{{Demonstração/Fim}}

;Observações:
* A terceira propriedade seria chamada de anti-simetria, se não fosse necessário considerar o caso "<math>a=-b</math>". Quando são considerados apenas os números não-negativos (os elementos de <math>\mathbb{Z}_+</math>) a conclusão é apenas "<math>a=b</math>", e as propriedades de 1 a 3 fazem da divisibilidade uma ''relação de [[w:ordem parcial|ordem parcial]]'' sobre <math>\mathbb{Z}_+</math>. No entanto, essa não é uma ordem total, pois nem todo par de elementos em <math>\mathbb{Z}_+</math> é [[w:comparável|comparável]], ou seja, existem inteiros não negativos <math>a</math> e <math>b</math>, para os quais não se tem <math>a|b</math> nem <math>b|a</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</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 ==

{{Wikipedia|Critérios de divisibilidade}}
Nas aulas de matemática do [[w:Ensino fundamental|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 é [[wikt:par#Adjetivo|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.

{| class="wikitable"
|-
!Um&nbsp;número&nbsp;é<br>divisível&nbsp;por...
!quando...
!Exemplos
|-
|'''1'''
|sempre!
|Qualquer número inteiro é divisível por 1.
|-
|'''2'''
|seu dígito das [[wikt:unidade|unidades]] é par (ou seja, 0, 2, 4, 6, ou 8).
|1 29<u>4</u> é par<ref name="wa1294">Veja a {{WolframAlpha|1294|fatoração de 1294}} e outras informações sobre este número no [[w:Wolfram Alpha|Wolfram Alpha]] (em inglês).</ref>, pois 4 é par.
|-
|'''3'''
|é divisível por 3 a soma dos seus dígitos.<ref name="div3">Conforme [http://books.google.com/books?id=-9pg-4Pa19IC&qtid=5c7e7983&hl=pt-BR&source=gbs_quotes_r&cad=8 diversos livros]</ref>
|405 é divisível por 3, pois 4 + 0 + 5 = 9, que é múltiplo de 3.
|-
|rowspan=2|'''4'''
|é divisível por 4 o <u>dígito das unidades</u> somado com o <u>[[wikt:dobro|dobro]] do dígito das [[wikt:dezena|dezenas]]</u>.
|5 0<u>96</u> é 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 8<u>41</u> não é divisível por 4, pois 41 não é.
|-
|'''5'''
|o dígito das unidades é 0 ou 5.
|123 456 789<u>0</u> é divisível por 5, já que seu último dígito é 0.
|-
|rowspan=2|'''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 <u>dígito das unidades</u> com o <u>[[wikt:quádruplo|quádruplo]] da soma dos demais dígitos</u>.
|<u>12 34</u>8 é divisível por 6, pois (1 + 2 + 3 + 4) <u>× 4</u> + 8 = 48
|-
|rowspan=5|'''7'''
|colspan="2" style="border-bottom: hidden; background: #EEEEEE" |vale qualquer dessas propriedades:
|-
| style="border-bottom: hidden;" |é divisível por 7 a <u>soma alternada</u> dos números formados pelos blocos de três dígitos (da direita para esquerda).
| style="border-bottom: hidden;" |1 369 851 é divisível por 7, pois  851 - 369 + 1 = 483 = 7 × 69
|-
| style="border-bottom: hidden;" |é divisível por 7 a soma do <u>número formado pelos dois últimos dígitos</u> com o <u>dobro do número formado ao desconsiderar estes dígitos</u>.
| style="border-bottom: hidden;" |<u>3</u>64 é divisível por 7, uma vez que (3 <u>× 2</u>) + 64 = 70.
|-
| style="border-bottom: hidden;" |é divisível por 7 a soma do <u>quíntuplo do último dígito</u> com o <u>número formado pelos dígitos restantes</u>.
| style="border-bottom: hidden;" |36<u>4</u> é divisível por 7, já que 36 + (4 <u>x 5</u>) = 56.
|-
| é divisível por 7 a diferença entre o <u>número formado ao desconsiderar o último dígito</u> e o <u>dobro deste dígito</u>.
|36<u>4</u> é divisível por 7, pois 36 − (4 <u>x 2</u>) = 28.
|-
|rowspan=4|'''8'''
| colspan="2" style="border-bottom: hidden; background: #EEEEEE" |vale qualquer dessas propriedades:
|-
| style="border-bottom: hidden;" |o <u>dígito das [[wikt:centena|centenas]]</u> é par e o <u>número formado pelos dois últimos dígitos</u> é divisível por 8.
| style="border-bottom: hidden;" |12 345 6<u>24</u> é divisível por 8, pois 6 é par e 24 = 3 x 8.
|-
| o <u>dígito das centenas</u> é ímpar e o <u>número formado pelos dois últimos dígitos, somado com 4</u> é divisível por 8.
|12 3<u>52</u>, é múltiplo de 8, já que 3 é ímpar e 52 <u>+ 4</u> = 56 = 7 x 8.
|-
|é divisível por 8 a soma do <u>último dígito</u> com o <u>dobro do número formado pelos demais</u>.
|13<u>6</u> é divisível por 8, uma vez que (13 <u>× 2</u>) + 6 = 32.
|-
|'''9'''
|é divisível por 9 a soma dos seus dígitos.<ref name="div9">Conforme [http://books.google.com/books?id=qFNZIUQ_MYUC&qtid=a37e7846&hl=pt-BR&source=gbs_quotes_r&cad=6 diversos livros]</ref>
|3 753 é múltiplo de 9, pois 3 + 7 + 5 + 3 = 18 e 1 + 8 = 9
|-
|'''10'''
|o último dígito é 0.
|13579<u>0</u> é múltiplo de 10, pois seu último dígito é 0.
|-
|rowspan=4|'''11'''
|colspan="2" style="border-bottom: hidden; background: #EEEEEE" |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).
|6<u>27</u> é múltiplo de 11, pois  6 + 27 = 33 = 3 x 11.
|-
|é múltiplo de 11 a diferença entre o <u>número formado ao desconsiderar o último dígito</u> e o <u>último dígito</u>.
|62<u>7</u> é 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 ''{{wikt|macete#Substantivo|macetes}}'' funcionam sempre?''
:''Por acaso alguém já testou algum deles para <u>todos</u> os números, e viu que nunca falham?''
:''Quem é que {{wikt|impor#Verbo|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 <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 < |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>.

}}

Um último passo antes de apresentar a justificativa formal para os critérios de divisibilidade mostrados anteriormente é entender como funciona o [[w:Sistema de numeração decimal|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,
:<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>
|}
{{Demonstração/Fim}}

=== 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.

== 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 é <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>.

}}


=== 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 <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>.
}}

=== 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 <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>
:<math>(-1)^k+11\left((-1)^{k-1}+ 11\frac{k!}{2!(k-2)!}(-1)^{k-2}+\ldots+11^{k-1}\right),</math>
ou seja, <math>10^k=(-1)^k + 11\times B_k,</math>onde <math>B_k=\sum_{i=1}^{k} \binom{k}{i}11^{i-1}(-1)^{k-i}.</math>

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 = 11 B + A</math>, onde <math>B = \sum_{k=0}^{n} a_k B_k</math> e <math>A = \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>.

}}

== Exercícios ==

# Justifique a validade de cada uma das [[#Propriedades da divisibilidade|propriedades da divisibilidade]] apresentadas no texto.

{{AutoCat}}

[[en:Number Theory/Elementary Divisibility]]

== Notas ==
<references/>