.Problema: Número Prático

Problema
(Indicado a partir do 7º ano do E. F.)


(Canadian Mathematical Olympiad) Um número inteiro positivo [tex]n[/tex] é dito prático se cada número inteiro positivo menor do que ou igual a [tex]n[/tex] pode ser escrito como a soma de divisores positivos distintos de [tex]n[/tex].
Por exemplo, os divisores positivos de [tex]6[/tex] são [tex]1,\ 2,\ 3[/tex] e [tex]6[/tex]. Como

  • [tex]1=1,[/tex]
  • [tex]2=2,\ 3=3,[/tex]
  • [tex]4=3+1,[/tex]
  • [tex]5=2+3,[/tex]
  • [tex]6=6,[/tex]

podemos afirmar que [tex]6[/tex] é prático.

Prove que o produto de dois números práticos também é prático.

explicador_p

Ajuda

Algoritmo de Euclides ou Algoritmo da Divisão

Sejam [tex]z[/tex] e [tex]y[/tex] números naturais, com [tex]y\ne 0.[/tex]

[tex]\qquad \qquad \begin{array}{r}
z \, \end{array} \begin{array}{|r}
\, y \, \, \, \\ \hline
\end{array}[/tex]
[tex]\qquad \qquad\begin{array}{r}
r
\end{array}\begin{array}{r}
\, \, \, q
\end{array}\qquad \qquad[/tex]
Ao dividirmos [tex]z[/tex] por [tex]y[/tex] encontraremos um quociente [tex]q [/tex] e um resto [tex]r [/tex], naturais e únicos, tais que:
[tex] \, \, \, \\(1) \, \, \, \, \, \, 0 \le r \lt y \, \, \, \, \, \, \, (2) \, \, z=q \, y+r.[/tex]

Solução


Sejam [tex]p_1[/tex] e [tex]p_2[/tex] números práticos e considere [tex]k[/tex] um inteiro positivo tal que [tex]k\le p_1p_2.[/tex]
Utilizando o algoritmo de Euclides, podemos escrever que:

[tex]k=q \, p_2+r[/tex] com [tex] 0\le r\lt p_2.\qquad \qquad \textcolor{#800000}{(i)}[/tex]

Mas [tex]k\le p_1p_2[/tex]; assim, segue que [tex]0\le q \le p_1[/tex] e, portanto, podemos reescrever a relação [tex] \textcolor{#800000}{(i)}[/tex] como:

[tex]k=q \, p_2+r[/tex] com [tex] 0\le r\lt p_2 \, [/tex] e [tex] \, 0\le q \le p_1.\qquad \qquad \textcolor{#800000}{(ii)}[/tex]

Como [tex]p_1[/tex] e [tex]p_2[/tex] são números práticos, temos que

[tex]q=c_1+c_2+\cdots+c_m \, \, \, \, \, \, \, \, \, \, \, \, \, \, r=d_1+d_2+\cdots+d_n[/tex]

em que os [tex]{c_i}’s[/tex] são alguns dos distintos divisores de [tex]p_1[/tex] e os [tex]{d_i}’s[/tex] são alguns dos distintos divisores de [tex]p_2[/tex].
Dessa forma, podemos reescrever o número [tex]k[/tex] como

[tex]\begin{align}k&=(c_1+c_2+\cdots+c_m)p_2+(d_1+d_2+\cdots+d_n)\\
&=c_1p_2+c_2p_2+\cdots +c_mp_2\ +d_1+\cdots +d_n.\end{align}\\
\, \, [/tex]

Observe que:

  • cada [tex]c_ip_2[/tex] e cada [tex]d_j[/tex] dividem [tex]p_1p_2[/tex];
  • como [tex]d_j\lt p_2\le c_ip_2 \, \, [/tex] para todos [tex]i,\ j \, [/tex], os números [tex]c_1p_2,c_2p_2,\cdots ,c_mp_2[/tex] e os números [tex]d_1,\cdots ,d_n[/tex] são distintos.

Assim, podemos concluir que [tex]p_1p_2[/tex] é um número prático.


Solução elaborada pelos Moderadores do Blog.

Link permanente para este artigo: http://clubes.obmep.org.br/blog/desafio-antigo-problema/