.Texto_012: Contagem de Divisores – um segundo estudo

Quantos divisores naturais tem o número [tex]~981663141888 [/tex] ?

Probleminha2

Contagem de divisores


Vamos obter uma propriedade que permitirá resolver não só o problema envolvendo o número [tex]~981663141888 [/tex], 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 [tex]n[/tex] é um número natural, [tex]n\gt 1[/tex], então existem números primos [tex]p_1,~p_2,~p_3,~\cdots~,~p_r[/tex], com [tex]r\ge 1[/tex], tais que
[tex]~~~~~~~~~~~~~~~~~~~~~~~~~~n=p_1~p_2~p_3~\cdots~p_r[/tex].
A menos da ordem dos fatores primos, essa representação é única.

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

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

[tex]~~~~~~~~~~~~~~~~~~~~~~~~~~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}[/tex].

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 [tex]n[/tex] um número natural, com [tex]n\gt 1[/tex], cuja decomposição como produto de potências de primos é

[tex]~~~~~~~~~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}.~\qquad\qquad (i)[/tex]

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

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

[tex]~~~~~~~~~d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}.[/tex]

Os primos que comparecem na decomposição de [tex]d[/tex] 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 [tex]d_1,\ d_2,\ \cdots,\ d_r[/tex].

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

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

[tex]~~~~~~~~~d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}~[/tex], com [tex]~d_1 \ge 0,\ d_2 \ge 0,\ \cdots,\ d_r \ge 0,[/tex]

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

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

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

Se [tex]n[/tex] é um número natural, com [tex]n\gt 1[/tex], cuja decomposição como produto de potências de primos é
[tex]~~~~~~~~~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}[/tex]
e se [tex]d[/tex] é um divisor de [tex]n[/tex], com [tex]d\gt 1[/tex], então
[tex]~~~~~~~~~~d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}[/tex], onde [tex]0\le d_i \le n_i [/tex], para [tex]i=1,\ 2,\ \cdots,\ r[/tex].

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

Lema: Seja [tex]n[/tex] um número natural, com [tex]n\gt 1[/tex], cuja decomposição como produto de potências de primos é [tex]~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}[/tex].
Então, um número natural [tex]d[/tex] é divisor de [tex]n[/tex] se, e somente se, [tex]d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}[/tex], com [tex]0\le d_i \le n_i [/tex], para [tex]i=1,\ 2,\ \cdots,\ r[/tex].

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

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 [tex]~981663141888 [/tex].

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

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

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

Sabendo-se que a decomposição de [tex]n[/tex] como produto de potências de primos é
[tex]~~~~~~~~~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}[/tex],
vamos determinar [tex]\tau (n)[/tex].
Pelo Lema obtido, sabemos que se [tex]d[/tex] é um divisor de [tex]n[/tex] se, e somente se, [tex]d[/tex] é da forma:
[tex]~~~~~~~~~d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}[/tex], com [tex]0\le d_i \le n_i \qquad\qquad (ii)[/tex],
logo, para obtermos [tex]\tau (n)[/tex], 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 [tex]d[/tex], conforme especificados em [tex](ii)[/tex], é dada pelo produto das possibilidades de escolhermos, simultaneamente, um valor para cada [tex] d_i [/tex], [tex]~i=1,\ 2,\ \cdots,\ r[/tex]. Mas, para cada [tex]i[/tex], [tex]i=1,\ 2,\ \cdots,\ r[/tex], a própria definição de [tex]d_i[/tex] ([tex]0\le d_i \le n_i[/tex]) nos mostra as possibilidades de escolha: entre 0 e [tex]n_i[/tex], temos [tex]n_i+1[/tex] números. Assim:

[tex]~~~~~~~~~\fcolorbox{#4178a1}{#b8c7d9}{$~\tau (n)=(n_1+1)\cdot(n_2+1)\cdot(n_3+1)\cdot~\cdots~\cdot(n_r+1)$}[/tex] .

(*) 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 [tex]~981663141888 [/tex]. Para isso devemos decompor esse número como produto de potências de números primos, ou seja, escrevê-lo conforme indicado em [tex](i)[/tex]. 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

[tex]\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}[/tex] [tex]~~~~~~~~~\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*}$}[/tex]

Com 23 divisões simples, conseguimos determinar que [tex]~981663141888 [/tex] tem 1456 divisores!

carinha_legal

Como [tex]~981663141888 [/tex] tem 1456 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 [tex]180=2^2\cdot 3^2\cdot 5[/tex], que é 3 ⋅ 3 ⋅ 2 = 18, ou, até mesmo, o número de divisores de [tex]1980=2^2\cdot 3^2\cdot 5\cdot 11[/tex], 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 [tex]n[/tex] é um número natural não nulo cuja decomposição em produto de potências de primos é
[tex]~~~~~~~~~n=p_1^{n_1}~p_2^{n_2}~p_3^{n_3}~\cdots~p_r^{n_r}[/tex],
já sabemos que a decomposição em produto de potências de primos de um divisor [tex]d[/tex] de [tex]n[/tex] é
[tex]~~~~~~~~~d=p_1^{d_1}~p_2^{d_2}~p_3^{d_3}~\cdots~p_r^{d_r}[/tex], com [tex]0\le d_i \le n_i \qquad\qquad (ii)[/tex].
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 [tex]d_i[/tex], [tex]i=1,~2,~\cdots,~r[/tex].
Por exemplo, os divisores de 180 são da forma [tex]2^x\cdot 3^y\cdot 5^z[/tex], com [tex]0\le x \le 2 [/tex]; [tex]0\le y \le 2 ~[/tex] e [tex]~0\le z \le 1 [/tex]. Calculando:

[tex]d_1=2^0\cdot 3^0\cdot 5^0=1[/tex];
[tex]d_2=2^1\cdot 3^0\cdot 5^0=2[/tex];
[tex]d_3=2^2\cdot 3^0\cdot 5^0=4[/tex];
[tex]d_4=2^0\cdot 3^1\cdot 5^0=3[/tex];
[tex]d_5=2^1\cdot 3^1\cdot 5^0=6[/tex];
[tex]d_6=2^2\cdot 3^1\cdot 5^0=12[/tex];
[tex]d_7=2^0\cdot 3^2\cdot 5^0=9[/tex];
[tex]d_8=2^1\cdot 3^2\cdot 5^0=18[/tex];
[tex]d_9=2^2\cdot 3^2\cdot 5^0=36[/tex];
[tex]d_{10}=2^0\cdot 3^0\cdot 5^1=5[/tex];
[tex]d_{11}=2^1\cdot 3^0\cdot 5^1=10[/tex];
[tex]d_{12}=2^2\cdot 3^0\cdot 5^1=20[/tex];
[tex]d_{13}=2^0\cdot 3^1\cdot 5^1=15[/tex];
[tex]d_{14}=2^1\cdot 3^1\cdot 5^1=30[/tex];
[tex]d_{15}=2^2\cdot 3^1\cdot 5^1=60[/tex];
[tex]d_{16}=2^0\cdot 3^2\cdot 5^1=45[/tex];
[tex]d_{17}=2^1\cdot 3^2\cdot 5^1=90[/tex];
[tex]d_{18}=2^2\cdot 3^2\cdot 5^1=180[/tex].

Assim, se indicarmos o conjunto dos divisores de 180 por [tex]D(180)[/tex], então:
[tex]~~~~~~~~~D(180)=\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 9,\ 10,\ 12,\ 15,\ 18,\ 20,\ 30,\ 36,\ 45,\ 60,\ 90,\ 180\}[/tex].
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:

 
[tex]\begin{array}{r|l} 180 & 2 \\90 & 2 \\45 & 3 \\15 & 3 \\ 5 & 5 \\1 \end{array}[/tex]

[tex]\begin{array}{c} \hspace{1.5 cm} \end{array} \begin{array}{l}~\fcolorbox{black}{#C6E2FF}{1}~ \\ \hline \end{array}[/tex]
[tex] \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}[/tex]

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

Os divisores de número natural [tex]n[/tex], [tex]n\gt 1[/tex], podem ser assim obtidos:

  • Fazemos a decomposição do número [tex]n[/tex] 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 [tex]n[/tex].
  • Nessa terceira coluna, na linha acima da linha que contém o menor número primo encontrado ([tex]p_1[/tex]), 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 [tex]n[/tex]. O último produto obtido será o próprio [tex]n[/tex], que é o maior divisor possível.

[tex]\begin{array}{c} \hspace{1.5 cm} \end{array} \begin{array}{l}~1 \\ \hline \end{array}[/tex]
[tex] \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}[/tex]

Precisam de problemas para praticar?

Aqui vão alguns!



Sonia Regina Di Giacomo
Equipe COM – OBMEP

Link permanente para este artigo: http://clubes.obmep.org.br/blog/texto_012-contagem-de-divisores-um-segundo-estudo/