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.
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.