Voltar para Sala de Estudo: Um pouco sobre divisibilidade (Parte 2)

Um pouco sobre divisibilidade – Contagem de divisores

Ué . . .
Aqui não é a sala para discussão do problema envolvendo o número [tex]\,981663141888[/tex] ?

Probleminha2

Contagem de divisores


Se você chegou até aqui procurando pela solução do problema que pede para determinar quantos divisores o número [tex]981663141888[/tex] tem, fique tranquilo, você está na Sala certa!
Nesta Sala, vamos obter uma propriedade que permitirá resolver não só o problema do 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], com [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], com [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].

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 [tex]1[/tex] 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 [tex]0[/tex] 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]\qquad\qquad\fcolorbox{#4178a1}{#b8c7d9}{$\,\begin{align*}\tau\left(981663141888\right)&=(12+1)\cdot\left(6+1\right)\cdot\left(3+1\right)\cdot\left(1+1\right)\cdot\left(1+1\right)\\&=13\times\,7\times\,4\times\,2\times\,2\\&=1456\end{align*}$}[/tex]

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

carinha_legal

Como [tex]981663141888[/tex] tem [tex]1456[/tex] 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 é [tex]3\cdot 3\cdot 2=18[/tex], ou, até mesmo, o número de divisores de [tex]1980=2^2\cdot 3^2\cdot 5\cdot 11[/tex], que é [tex]3\cdot 3\cdot 2 \cdot 2=36[/tex], a pergunta de como se obter os [tex]18[/tex] ou os [tex]36[/tex] 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 [tex]180[/tex] 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 [tex]180[/tex] 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 [tex]2[/tex], [tex]3[/tex] e [tex]5[/tex], 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 [tex]1[/tex], 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!



Equipe COM – OBMEP

Voltar para Sala Principal

Link permanente para este artigo: http://clubes.obmep.org.br/blog/teoria-dos-numeros-um-pouco-sobre-divisibilidade-parte-2/um-pouco-sobre-divisibilidade-numero-de-divisores/