Expansão de naturais na base \(b\)
Números naturais são escritos normalmente como sequências de algarismos na base decimal. Por exemplo, a sequência \(1056\) significa o número \[
1\cdot 1000+0\cdot 100+5\cdot 10+6.
\] Mais geralmente, a sequência \([a_na_{n-1}\cdots a_1a_0]\) denota o número \[
\sum_{k=0}^n a_k\cdot 10^k.
\]
É possível fazer a mesma coisa em uma outra base \(b\) assumindo que \(b\geq 2\).
Teorema 12.1 Assuma que \(a\) e \(b\) são números naturais e \(b\geq 2\). Então \(a\) pode ser escrito unicamente na forma \[
a=[a_na_{n-1}\cdots a_0]_b=\sum_{k=0}^n a_kb^k
\] onde \(n\geq 0\) e \(a_k\in\{0,\ldots,b-1\}\) para todo \(k\)
Os números \(a_k\) são chamados de algarismos de \(a\) na base \(b\).
Comprovação. Existência. Usaremos indução por \(a\). Se \(a\in\{0,\ldots,b-1\}\) então \(a\) pode ser escrito como \([a]_b\). Assuma agora que \(a\geq b\) e os números menores que \(a\) podem ser escritos na base \(b\). Usando o Teorema de Divisão de Euclides, escreva \(a=qb+a_0\) onde \(0\leq a_0\leq b-1\). Como \(b\geq 2\), temos que \(q<a\), e a hipótese de indução é válida para \(q\). Portanto existem \(a_n,\ldots,a_1\in\{0,\ldots,b-1\}\) tais que \[
q=[a_na_{n-1}\cdots a_1]_b=\sum_{k=1}^n a_kb^{k-1}
\] e \[
a=bq+a_0=b\left(\sum_{k=1}^n a_kb^{k-1}\right)+a_0=\sum_{k=0}^n a_kb^{k}=[a_na_{n-1}\cdots a_1a_0]_b
\] Então a expressão desejada para \(a\) existe.
Unicidade. Provaremos esta parte também por indução em \(a\). Se \(a\in\{0,\ldots,b-1\}\), então \(a=[a]_b\) é a única expansão de \(a\) na base \(b\). Assuma que \(a\geq b\) e assuma também que todo número menor que \(a\) possui única expansão na base \(b\). Suponha que \(a\) possui duas expansões \[
a=[a_n\cdots a_1a_0]_b=\sum_{k=0}^n a_kb^k
\] e \[
a=[c_m\cdots c_1c_0]_b=\sum_{k=0}^m c_kb^k.
\] Como acima, escreva \(a=qb+r\) onde \(0\leq r\leq b-1\) e note que os números \(q\) e \(r\) são únicos. Pelas duas expressões para o número \(a\) obtemos que \[
a=\sum_{k=0}^n a_kb^k=b\cdot\left(\sum_{k=1}^n a_kb^{k-1}\right)+a_0
\] e \[
a=\sum_{k=0}^m c_kb^k=b\cdot\left(\sum_{k=1}^m c_kb^{k-1}\right)+c_0.
\] Pela unicidade do resto no Teorema de Euclides, obtemos que \(r=a_0=c_0\); ou seja, os últimos algarismos são determinados unicamento.
Agora, \[
q=(a-r)/b=\sum_{k=1}^n a_kb^{k-1}=\sum_{k=1}^m c_kb^{k-1};
\] ou seja \[
q=[a_n\cdots a_1]_b=[c_m\cdots c_1]_b.
\] A hipótese de indução aplica-se para o número \(q\), e assim as as sequências \([a_n\cdots a_1]_b\) e \([c_m\cdots c_1]_b\) são iguais. Portanto as duas expansões para o número \(a\) são iguais como foi afirmado.
Exemplo 12.1 Seguindo a demonstração do teorema anterior, obtemos um algoritmo para determinar a sequência dos dígitos de um número natural em uma base \(b\). Tome o número \(a=168\) e seja \(b=5\).
Passo 1: \[
168=33\cdot 5+3,
\] portanto o último algarismo de \(168\) é \(3\) e os demais algarismos são os algarismos de \(33\).
Passo 2: \[
33 = 6\cdot 5+3.
\] Logo o penúltimo algarismo é \(3\) e os demais algarismos são os algarismos de \(6\).
Passo 3: \[
6=1\cdot 5+1;
\] ou seja, o seguinte algarismo é \(1\) e os demais algarismos são os algarismos de \(1\).
Passo 4: \[
1=0\cdot 5+1
\] que diz que \(1=[1]_5\).
Juntando as peças, obtemos que \(168=[1133]_5\).
Critérios de divisibilidade
Seja \(a\) um número natural escrito na base \(10\) (decimal) como \[
a=[a_na_{n-1}\cdots a_1a_0]_{10}=[a_na_{n-1}\cdots a_1a_0].
\] É bem conhecido que, para alguns valores de \(b\), a divisibilidade de \(a\) por \(b\) pode ser determinado olhando apenas os dígitos de \(a\).
Exercício 12.1 Demonstre que para todo \(i\geq 0\), existe \(q_i\in\N_0\) tal que \(10^i=3q_i+1\)
Teorema 12.2 (Critérios de divisibilidade) As seguintes afirmações são verdadeiras para um número natural \(a=[a_na_{n-1}\cdots a_1a_0]\) escrito na base decimal.
- \(2\mid a\) se e somente se \(2\mid a_0\);
- \(3\mid a\) se e somente se \(3\mid a_n+a_{n-1}+\cdots+a_0\);
- \(4\mid a\) se e somente se \(4\mid [a_1a_0]\);
- \(5\mid a\) se e somente se \(5\mid a_0\);
- \(7\mid a\) se e somente se \(7\mid [a_n\cdots a_1]-2a_0\);
- \(8\mid a\) se e somente se \(8\mid [a_2a_1a_0]\);
- \(9\mid a\) se e somente se \(9\mid a_n+a_{n-1}+\cdots+a_0\);
- \(10\mid a\) se e somente se \(10\mid a_0\) (ou seja, \(a_0=0\));
- \(11\mid a\) se e somente se \(11\mid (-1)^na_n+(-1)^{n-1}a_{n-1}+\cdots-a_1+a_0\);
Comprovação. Demonstraremos algumas destas afirmações, o resto será exercício.
Considere que \[\begin{align*}
a&=[a_na_{n-1}\cdots a_1a_0]=\sum_{k=0}^n10^ka_k=10\left(\sum_{k=1}^n10^{k-1}a_k\right)+a_0\\&=10q+a_0
\end{align*}\] com \[
q=\sum_{k=1}^n10^{k-1}a_k\in\mathbb N.
\] Como \(2\mid 10\), obtemos que o número \(a\) é divisível por \(2\) se e somente se o algarismo \(a_0\) é divisível por \(2\).
Temos, pelo exercício antes do teorema, para todo \(i\geq 0\), existe \(q_i\in\N_0\) tal que \(10^i=3q_i+1\). Agora considere \[\begin{align*}
a&=[a_n\cdots a_1a_0]=\sum_{k=0}^n 10^ka_k=\sum_{k=0}^n (3q_k+1)a_k\\&=3\sum_{k=0}^nq_ka_k+
\sum_{k=0}^na_k.
\end{align*}\] No última expressão, a primeira parcela é um múltiplo de \(3\). Logo \(a\) é divisível por \(3\) se e somente se a segunda parcela na última expressão é divisível por \(3\), mas esta segunda parcela é justamente a soma dos dígitos de \(a\).