|
Ué . . . |
 |
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:
[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:
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.
[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!
 |
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}{c} \hspace{1.5 cm} \end{array} \begin{array}{l} \, \fcolorbox{black}{#C6E2FF}{1} \, \\ \hline \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.
Precisam de problemas para praticar?
Aqui vão alguns!
Equipe COM – OBMEP