Problema
(Indicado a partir do 2º ano do E. M.)
Seja [tex]n[/tex] um número inteiro positivo menor ou igual a [tex]24[/tex].
Para quantos valores de [tex]n[/tex] a divisão de [tex]n ![/tex] por [tex]1 + 2 + \ldots + n[/tex] resulta em um número inteiro?
Solução
Como [tex]1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}[/tex], o problema equivale a determinar para quais números inteiros positivos ímpares o valor de [tex]\dfrac{n!}{\frac{n(n+1)}{2}}[/tex] é inteiro.
Mas
[tex]\qquad\qquad\dfrac{n!}{\dfrac{n(n+1)}{2}}= \dfrac{2 n!}{n(n+1)}=\frac{2 n(n-1)!}{n(n+1)}=\dfrac{2 (n-1)!}{n+1}[/tex]
assim, basta termos para [tex]1 \le n \le 24[/tex] um valor inteiro para [tex]\dfrac{2(n-1)!}{n+1}[/tex].
(*) Essa fração é um número inteiro, exceto quando [tex]n+1[/tex] é um número primo ímpar.
Temos oito números primos ímpares menores ou iguais a [tex]25[/tex], portanto há [tex]24 – 8 = 16[/tex] números menores ou iguais a [tex]24[/tex] que satisfazem a condição inicial do problema.
Solução elaborada pelos Moderadores do Blog.
Discutindo a afirmação (*)
A afirmação (*) é consequência da seguinte proposição:
Proposição: Para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro se, e somente se, [tex]n+1[/tex] não é um número primo ímpar.
Demonstração da proposição: Para provarmos esta proposição, podemos dividir a demonstração em duas partes. Antes de começarmos, perceba que [tex]n[/tex] inteiro positivo indica que [tex]n\ge 1[/tex] e, assim, [tex]n+1\ge 2[/tex], o que garante que [tex]n+1\ne 1[/tex] e, portanto, ou é primo ou é composto.
- Inicialmente, podemos mostrar que, para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro somente se [tex]n+1[/tex] não é um número primo ímpar, ou seja,
- se [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro, então [tex]n+1[/tex] não é um número primo ímpar.
Perceba que isto equivale a mostrar que se [tex]n+1[/tex] é um número primo ímpar, então é impossível termos [tex]\frac{2(n-1)!}{n+1}[/tex] inteiro.
De fato, se [tex]n+1[/tex] é primo ímpar, o denominador da fração é divisível apenas por [tex]1[/tex] e por [tex]n+1[/tex]. Entretanto, o numerador não possui o fator primo ímpar [tex]n+1[/tex] em sua decomposição, ou seja, a fração não representa um número inteiro.
Realmente, é possível provar (foge dos objetivos desta demonstração fazê-lo, mas podemos utilizar o resultado) que, se [tex]p[/tex] é um primo e se uma multiplicação de inteiros é divisível por [tex]p[/tex], então pelo menos um daqueles inteiros é divisível por [tex]p[/tex]. Como [tex]n+1[/tex] é um primo ímpar, dizer que [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro equivale a dizer que ao menos um dos inteiros [tex]1,2,\cdots,(n-1)[/tex], que formam o produto [tex]2(n-1)![/tex] é divisível por [tex]n+1[/tex], o que não procede.
Sendo assim: Para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro somente se [tex]n+1[/tex] não é um número primo ímpar.
- Agora, temos ainda que mostrar que, para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro se [tex]n+1[/tex] não é um número primo ímpar, ou seja, se [tex]n+1[/tex] não é um número primo ímpar (se ele é igual a [tex]2[/tex] – o único primo par-, ou é composto), então [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro.
Bem, se [tex]n+1=2[/tex], temos [tex]n-1=0[/tex] e [tex]\frac{2(n-1)!}{n+1}=\frac{2\cdot 0!}{2}=0!=1[/tex] (inteiro).
Agora, se [tex]n+1[/tex] é um número composto, podemos considerar dois casos distintos:
a) [tex]n+1[/tex] é da forma [tex]p^2[/tex], com [tex]p[/tex] primo;
b) [tex]n+1[/tex] não é da forma [tex]p^2[/tex], com [tex]p[/tex] primo.
No caso b), [tex]n+1[/tex] possui mais de [tex]1[/tex] divisor positivo diferentes de [tex]1[/tex] e de [tex]n+1[/tex], o que significa que podemos escrever [tex]n+1[/tex] como a multiplicação de dois fatores inteiros positivos distintos menores que [tex]n[/tex], já que [tex]n[/tex] não é divisor de [tex]n+1[/tex] (do contrário existiria [tex]k[/tex] inteiro positivo tal que [tex]n+1=kn[/tex], ou seja, [tex]n(1-k)=-1[/tex], donde teríamos [tex]1-k=-1[/tex] e [tex]n=1[/tex], já que [tex]1\cdot(-1)[/tex] é a única forma de representar [tex]-1[/tex] como produto de dois números inteiros – convença-se disso. Mas consideramos [tex]n+1>2\iff n>1[/tex] nesta parte da demonstração, logo [tex]n\not=1[/tex] e [tex]n[/tex] não é divisor de [tex]n+1[/tex]).
Veja que [tex](n-1)![/tex] contém esses dois fatores, de onde concluímos que [tex]n+1\mid(n-1)![/tex], digo, que [tex](n-1)!=(n+1)q[/tex] para algum [tex]q\in\mathbb{Z}[/tex] e, assim, [tex]\frac{2(n-1)!}{n+1}=2q[/tex] (inteiro).
Para o caso a), observe que [tex]n+1=p^2=p\cdot (p-1)+p[/tex] e, como [tex]p\ge2[/tex] (pois [tex]p[/tex] é primo!), [tex]n+1-p=p\cdot (p-1)\le n-1[/tex], ou seja, [tex]n-1\ge p\cdot (p-1)[/tex]. Assim, o produto representado por [tex](n-1)![/tex] contém pelo menos [tex]p-1[/tex] múltiplos positivos de [tex]p[/tex], donde [tex](n-1)![/tex] é divisível por [tex]p^{p-1}[/tex].
Se [tex]p>2[/tex], [tex]p-1\ge2[/tex] e [tex](n-1)![/tex] ser divisível por [tex]p^{p-1}[/tex] implica que [tex](n-1)![/tex] é divisível por [tex]p^2=n+1[/tex], donde [tex]\frac{2(n-1)!}{n+1}\in\mathbb{Z}[/tex]. De fato, busque entender que se um inteiro [tex]b[/tex] é divisível por uma potência de um inteiro [tex]a[/tex], [tex]a^x[/tex], então [tex]b[/tex] é divisível por todo [tex]a^y[/tex], com [tex]0\le y\le x[/tex], [tex]x,y\in\mathbb{N}[/tex], e busque compreender como aplicamos isso acima.
Por fim, se [tex]p=2[/tex], [tex]n+1=2^2=4[/tex] e [tex]n-1=2[/tex], donde [tex]\frac{2(n-1)!}{n+1}=\frac{2\cdot 2!}{4}=1[/tex] (inteiro), completando a demonstração.
Portanto, temos que para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro somente se [tex]n+1[/tex] não é um número primo ímpar e [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro se [tex]n+1[/tex] não é um número primo ímpar.
Logo, a proposição que fizemos é verdadeira: Para [tex]n[/tex] inteiro positivo, [tex]\frac{2(n-1)!}{n+1}[/tex] é inteiro se, e somente se, [tex]n+1[/tex] não é um número primo ímpar.