.Texto_012: Contagem de Divisores – um segundo estudo

Quantos divisores naturais tem o número $~981663141888$ ?

Contagem de divisores

Vamos obter uma propriedade que permitirá resolver não só o problema envolvendo o número $~981663141888$ , mas também muitos outros problemas interessantes. Essa propriedade é uma consequência dos tópicos estudados na Sala sobre Divisibilidade nos Números Naturais; assim, antes mais nada, vamos relembrar um resultado que terá um papel central na nossa discussão: o Teorema Fundamental da Aritmética
O TFA pode ser enunciado a partir de produtos de números primos:

Se $n$ é um número natural, $n\gt 1$ , então existem números primos $p_1, \, p_2, \, p_3, \, \cdots \, , \, p_r$ , com $r\ge 1$ , tais que
$\, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, n=p_1 \, p_2 \, p_3 \, \cdots \, p_r$ .
A menos da ordem dos fatores primos, essa representação é única.

ou a partir de produto de potências de números primos:

Seja $n$ um número natural, $n\gt 1$ .
Então existem números primos $p_1\lt p_2\lt p_3\lt \, \cdots \, \lt p_r$ e, também, números naturais não nulos $n_1, \, n_2, \, n_3, \, \cdots \, , \, n_r$ , com $r\ge 1$ , tais que

$\, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}$ .

Além disso, essa decomposição é única.

Utilizando essa segunda forma do TFA, vamos estabelecer uma relação entre a decomposição de um número natural e as decomposições de seus possíveis divisores. Vamos lá.

Seja

$n$ um número natural, com

$n\gt 1$ , cuja decomposição como produto de potências de primos é

$\, \, \, \, \, \, \, \, \, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}. \, \qquad\qquad (i)$

Se $d$ é um divisor de $n$ , com $d\gt 1$ , o que podemos afirmar sobre os divisores primos de $d$ ?
Como $d\gt 1$ , o TFA garante que $d$ pode ser escrito como produto de números primos; tome, então, um primo $q$ tal que $q\mid d$ . Assim temos que $q\mid d$ e $d\mid n$ ; portanto, pela Propriedade 2 de divisibilidade, $q\mid n$ . Mas lembramos que a decomposição $(i)$ apresentada para $n$ é única, logo $q$ é um dos primos $p_i$ que aparecem nessa decomposição.
Portanto, a unicidade do TFA obriga a que não existam fatores primos de $d$ que não sejam aqueles que aparecem na decomposição de $n$ .

Considerando essa análise, a decomposição de $d$ como produto de potências de primos é da forma:

$\, \, \, \, \, \, \, \, \, d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r}.$

Os primos que comparecem na decomposição de $d$ como produto de potências de primos nós já conhecemos, então, para que essa decomposição seja completamente definida, temos que analisar os expoentes $d_1,\ d_2,\ \cdots,\ d_r$ .

Observamos, por exemplo, que $10=2\cdot 5$ é divisor de $140=2^2\cdot 5\cdot 7$ , assim, nem todos os primos que comparecem na decomposição de $n$ precisam, necessariamente, estar na decomposição de $d$ ; portanto, $d_i \ge 0$ , para cada natural $i$ , $i=1,\ 2,\ \cdots,\ r$ . Se $d_i = 0$ , significa que o primo $p_i$ não comparece efetivamente na decomposição de $d$ .

Pelo até agora exposto, a decomposição de $d$ como produto de potências de primos é:

$\, \, \, \, \, \, \, \, \, d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r} \,$ , com $\, d_1 \ge 0,\ d_2 \ge 0,\ \cdots,\ d_r \ge 0,$

mas a decomposição ainda não está completamente definida.

Finalmente, observamos que, por hipótese, $d$ é divisor de $n$ , logo $n=kd$ , para algum número natural $k$ . Portanto, nenhum fator primo $p_i$ pode comparecer na decomposição de $d$ num número maior de vezes do que comparece na decomposição de $n$ . Assim, para cada $i$ , $i=1,\ 2,\ \cdots,\ r$ , temos que $d_i \le n_i$ .

A nossa discussão garante, então, que:

$n$ é um número natural, com

$n\gt 1$ , cuja decomposição como produto de potências de primos é

$\, \, \, \, \, \, \, \, \, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}$
e se

$d$ é um divisor de

$n$ , com

$d\gt 1$ , então

$\, \, \, \, \, \, \, \, \, \, d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r}$ , com

$0\le d_i \le n_i$ , para

$i=1,\ 2,\ \cdots,\ r$ .

Por outro lado, todo número decomposto como:
$\, \, \, \, \, \, \, \, \, \, m=p_1^{m_1} \, p_2^{m_2} \, p_3^{m_3} \, \cdots \, p_r^{m_r}$ , com $0\le m_i \le n_i$ , para $i=1,\ 2,\ \cdots,\ r$
evidentemente divide $n$ .
Assim, mais do que uma implicação, temos uma equivalência, ou seja:

Lema: Seja

$n$ um número natural, com

$n\gt 1$ , cuja decomposição como produto de potências de primos é

$\, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}$ .
Então, um número natural

$d$ é divisor de

$n$ se, e somente se,

$d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r}$ , com

$0\le d_i \le n_i$ , para

$i=1,\ 2,\ \cdots,\ r$ .

Observem que os extremos da variação $0\le d_i \le n_i$ , para cada $i=1,\ 2,\ \cdots,\ r$ , nos fornecem os “divisores extremos” de $n$ :
• se cada $d_i$ for $0$ , obtemos o menor divisor: $d=1$ ;
• se cada $d_i$ for o respectivo $n_i$ , obtemos o maior divisor: $d=n$ .

Com esse Lema, estamos aptos a determinar a quantidade de divisores de qualquer número natural não nulo. A partir desse resultado, particularmente, obteremos o número de divisores do número $~981663141888$ .

Fórmula do número de divisores (*)

Se $n$ é um número natural não nulo ( $n\in \mathbb{N}^*$ ), é usual representarmos o número de divisores naturais de $n$ por $\tau (n)$ ( $\tau$ : letra grega tau) ou $tau (n)$ . Por exemplo:

$\tau (1)=1$
$\tau (2)=2$ ;
$\tau (3)=2$ ;
$\tau (4)=3$ ;
$\tau (10)=4$ ;
$\tau (12)=6$ ;
se $p$ é primo, então $\tau (p)=2$ , já que os únicos divisores naturais de um número primo são o e o próprio $p$ .

Sabendo-se que a decomposição de $n$ como produto de potências de primos é
$\, \, \, \, \, \, \, \, \, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}$ ,
vamos determinar $\tau (n)$ .
Pelo Lema obtido, sabemos que se $d$ é um divisor de $n$ se, e somente se, $d$ é da forma:
$\, \, \, \, \, \, \, \, \, d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r}$ , com $0\le d_i \le n_i ~$ , $\qquad\qquad (ii)$
logo, para obtermos $\tau (n)$ , basta contarmos quantos números naturais têm essa forma e para isso vamos utilizar uma ferramenta da Análise Combinatória.
Pelo Princípio Fundamental da Contagem ou Princípio Multiplicativo, a quantidade de números $d$ , conforme especificados em $(ii)$ , é dada pelo produto das possibilidades de escolhermos, simultaneamente, um valor para cada $d_i$ , $\, i=1,\ 2,\ \cdots,\ r$ . Mas, para cada $i$ , $i=1,\ 2,\ \cdots,\ r$ , a própria definição de $d_i$ ( $0\le d_i \le n_i$ ) nos mostra as possibilidades de escolha: entre e $n_i$ , temos $n_i+1$ números. Assim:

$\, \, \, \, \, \, \, \, \, \fcolorbox{#4178a1}{#b8c7d9}{$ \, \tau (n)=(n_1+1)\cdot(n_2+1)\cdot(n_3+1)\cdot \, \cdots \, \cdot(n_r+1)$}$ .

(*) Esta discussão aprofunda a abordagem do tema que foi feita no texto Contagem de Divisores

Com essa fórmula, podemos determinar, finalmente, quantos divisores naturais tem o número $~981663141888$ . Para isso devemos decompor esse número como produto de potências de números primos, ou seja, escrevê-lo conforme indicado em $(i)$ . Para tanto, vamos utilizar o Dispositivo Prático 1 apresentado na Sala do TFA. Se você não se lembra, clique AQUI.

A solução

$\begin{array}{r|l}~981663141888 & 2\\ ~490831570944 & 2\\~245415785472 & 2\\ ~122707892736 & 2 \\ ~61353946368 & 2\\ ~30676973184 & 2 \\ ~15338486592 & 2 \\ ~7669243296 & 2 \\ ~3834621648 & 2 \\ ~1917310824 & 2 \\ ~958655412 & 2 \\ ~479327706 & 2 \\ ~239663853 & 3 \\ ~79887951 & 3 \\ ~26629317 & 3 \\ ~8876439 & 3 \\ 2958813 & 3 \\ 986271 & 3 \\ 328757 & 11 \\ 29887 & 11 \\ 2717 & 11 \\ 247 & 13 \\ 19 & 19 \\1 & \boxed{2^{12}\cdot 3^6\cdot 11^3 \cdot 13 \cdot 19}\end{array}$ $\, \, \, \, \, \, \, \, \, \fcolorbox{#4178a1}{#b8c7d9}{$ \, \begin{align*} \tau (~981663141888) & =(12+1)\cdot(6+1)\cdot(3+1)\cdot (1+1) \cdot (1+1) \\ & = 13\times 7 \times 4 \times 2 \times 2 \\ & = 1456\end{align*}$}$

Com divisões simples, conseguimos determinar que $~981663141888$ tem 1456 divisores!

Como $~981663141888$ tem divisores, talvez ninguém tenha se perguntado se existe uma maneira prática de obtermos esses divisores. Mas se tivéssemos calculado o número de divisores de $180=2^2\cdot 3^2\cdot 5$ , que é , ou, até mesmo, o número de divisores de $1980=2^2\cdot 3^2\cdot 5\cdot 11$ , que é 3 ⋅ 3 ⋅ 2 ⋅ 2 = 36, a pergunta de como se obter os 18 ou os 36 divisores seria natural.
Teoricamente, a resposta para esse tipo de pergunta é simples; vejamos.

Quais são os divisores de um número natural?

Se $n$ é um número natural não nulo cuja decomposição em produto de potências de primos é
$\, \, \, \, \, \, \, \, \, n=p_1^{n_1} \, p_2^{n_2} \, p_3^{n_3} \, \cdots \, p_r^{n_r}$ ,
já sabemos que a decomposição em produto de potências de primos de um divisor $d$ de $n$ é
$\, \, \, \, \, \, \, \, \, d=p_1^{d_1} \, p_2^{d_2} \, p_3^{d_3} \, \cdots \, p_r^{d_r}$ , com $0\le d_i \le n_i \qquad\qquad (ii)$ .
Com essa informação, para obtermos todos os números naturais que têm essa forma, basta fazermos as combinações dos possíveis valores de $d_i$ , $i=1, \, 2, \, \cdots, \, r$ .
Por exemplo, os divisores de são da forma $2^x\cdot 3^y\cdot 5^z$ , com $0\le x \le 2$ ; $0\le y \le 2 \,$ e $\, 0\le z \le 1$ . Calculando:

$d_1=2^0\cdot 3^0\cdot 5^0=1$ ;

$d_2=2^1\cdot 3^0\cdot 5^0=2$ ;

$d_3=2^2\cdot 3^0\cdot 5^0=4$ ;

$d_4=2^0\cdot 3^1\cdot 5^0=3$ ;

$d_5=2^1\cdot 3^1\cdot 5^0=6$ ;

$d_6=2^2\cdot 3^1\cdot 5^0=12$ ;

$d_7=2^0\cdot 3^2\cdot 5^0=9$ ;

$d_8=2^1\cdot 3^2\cdot 5^0=18$ ;

$d_9=2^2\cdot 3^2\cdot 5^0=36$ ;

$d_{10}=2^0\cdot 3^0\cdot 5^1=5$ ;

$d_{11}=2^1\cdot 3^0\cdot 5^1=10$ ;

$d_{12}=2^2\cdot 3^0\cdot 5^1=20$ ;

$d_{13}=2^0\cdot 3^1\cdot 5^1=15$ ;

$d_{14}=2^1\cdot 3^1\cdot 5^1=30$ ;

$d_{15}=2^2\cdot 3^1\cdot 5^1=60$ ;

$d_{16}=2^0\cdot 3^2\cdot 5^1=45$ ;

$d_{17}=2^1\cdot 3^2\cdot 5^1=90$ ;

$d_{18}=2^2\cdot 3^2\cdot 5^1=180$ .

Assim, se indicarmos o conjunto dos divisores de por $D(180)$ , então:
$\, \, \, \, D(180)=\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 9,\ 10,\ 12,\ 15,\ 18,\ 20,\ 30,\ 36,\ 45,\ 60,\ 90,\ 180\}.$
Utilizamos essa maneira de combinar os expoentes de 2, 3 e 5, pois ela pode ser facilmente obtida a partir do dispositivo prático da decomposição de 180 em fatores primos. Observe:

$\begin{array}{r|l} 180 & 2 \\90 & 2 \\45 & 3 \\15 & 3 \\ 5 & 5 \\1 \end{array}$

$\begin{array}{c} \hspace{1.8 cm} \end{array} \begin{array}{l} \, \fcolorbox{black}{#C6E2FF}{1} \, \\ \hline \end{array}$
$\begin{array}{r|l} 180 & 2 & \fcolorbox{black}{#C6E2FF}{2}\\90 & 2 & \fcolorbox{black}{#C6E2FF}{4}\\45 & 3 & \fcolorbox{black}{#C6E2FF}{3} \, \, \, \, \fcolorbox{black}{#C6E2FF}{6} \, \, \, \, \, \, \fcolorbox{black}{#C6E2FF}{12}\\15 & 3 & \fcolorbox{black}{#C6E2FF}{9} \, \, \, \, \fcolorbox{black}{#C6E2FF}{18} \, \, \, \, \fcolorbox{black}{#C6E2FF}{36}\\5 & 5 & \fcolorbox{black}{#C6E2FF}{5} \, \, \, \, \fcolorbox{black}{#C6E2FF}{10} \, \, \, \, \fcolorbox{black}{#C6E2FF}{20} \, \, \, \, \fcolorbox{black}{#C6E2FF}{15} \, \, \, \, \fcolorbox{black}{#C6E2FF}{30} \, \, \, \, \fcolorbox{black}{#C6E2FF}{60} \, \, \, \, \fcolorbox{black}{#C6E2FF}{45} \, \, \, \, \fcolorbox{black}{#C6E2FF}{90} \, \, \, \, \fcolorbox{black}{#C6E2FF}{180}\\ 1 \end{array}$

Analisando esse exemplo, percebemos que é possível obter todos os divisores de um número natural $n\gt 1$ de um modo sistemático; assim, definiremos um segundo dispositivo prático para isso.

Os divisores de um número natural $n$ , $n\gt 1$ , podem ser assim obtidos:

Fazemos a decomposição do número $n$ em fatores primos, utilizando o Dispositivo Prático 1.
Feita a decomposição, fazemos um segundo traço vertical, à direita dos fatores primos, obtendo, assim, uma terceira coluna na qual iremos escrever os divisores de $n$ .
Nessa terceira coluna, na linha acima da linha que contém o menor número primo encontrado ( $p_1$ ), escrevemos o número 1, pois ele é divisor de qualquer número.
Multiplicamos sucessivamente cada fator primo pelos divisores já obtidos e escrevemos esses produtos na terceira coluna, ao lado do respectivo fator primo utilizado, eliminando-se as eventuais duplicidades (divisores que já foram encontrados anteriormente).
Prosseguimos com esse procedimento até esgotarmos os fatores primos do número $n$ . O último produto obtido será o próprio $n$ , que é o maior divisor possível.

$\begin{array}{c} \hspace{1.8 cm} \end{array} \begin{array}{l} \, 1 \\ \hline \end{array}$
$\begin{array}{r|l} n & p_1 & d_1=p_1\cdot 1\\a_1 & p_2 & d_2=p_2\cdot 1; \, d_3=p_2\cdot d_1 \\a_2 & p_3 & d_4=p_3\cdot 1; \, d_5=p_3\cdot d_1; \, d_6=p_3\cdot d_2; \, d_7=p_3\cdot d_3 \\a_3 & p_4 & d_8=p_4\cdot 1; \, d_9=p_4\cdot d_1; \, d_{10}=p_4\cdot d_2; \, d_{11}=p_4\cdot d_3; \, d_{12}=p_4\cdot d_4; \\ & & d_{13}=p_4\cdot d_5; \, d_{14}=p_4\cdot d_6; \, d_{15}=p_4\cdot d_7 \\ \vdots & \vdots & \vdots \\ p_j & p_j & p_j\cdot 1; \, \quad \cdots \, \quad ; \, n \\ 1 \, & \, & \end{array}$

Precisam de problemas para praticar?

Aqui vão alguns!

Problemas

Sonia Regina Di Giacomo
Equipe COM – OBMEP