Olimpíadas ⇒ (Bulgária 2005) Teoria dos Números Tópico resolvido

[rean]

Ache todos os naturais de quatro algarismos [tex3]m,[/tex3] menores que [tex3]2005[/tex3] e para os quais existe um natural [tex3]n < m[/tex3] tal que [tex3]m - n[/tex3] possui no máximo [tex3]3[/tex3] divisores e [tex3]m\cdot n[/tex3] seja um quadrado perfeito.

[AnthonyC]

Vou provar aqui um resultado e dois corolários que usarei depois:

• Número de divisores de [tex3]m[/tex3]:

Demostração:
Seja [tex3]m[/tex3] escrito através da sua fatoração em primos [tex3]m=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}\cdot\space ... \space \cdot p_n^{k_n}[/tex3], em que [tex3]p_1,p_2,p_3,...,p_n[/tex3] são primos e [tex3]k_1,k_2,k_3,...,k_n\in \mathbb{N}[/tex3].
O número de divisores de [tex3]m[/tex3] pode ser encontrado da seguinte forma: cada combinação dos primos divisores de [tex3]m[/tex3] com expoentes menores ou iguais aos que eles possuem é um possível divisor de [tex3]m[/tex3]. Sendo assim, para [tex3]p_1[/tex3] eu tenho as seguintes possibilidades: [tex3]\{p_1^{1},p_1^{2},...,p_1^{k_1} \}[/tex3] ou seja [tex3]k_1[/tex3] possibilidades. Porém, ainda posso incluir o [tex3]p_1^0[/tex3], dado que isso resulta em 1, e 1 é divisor de todos os números. Assim, eu tenho [tex3]k_1+1[/tex3] possibilidades. Analogamente para [tex3]p_2[/tex3] temos [tex3]k_2+1[/tex3] possibilidades, para [tex3]p_3[/tex3] temos [tex3]k_3+1[/tex3] possibilidades, assim por diante. Sendo assim, pelo Princípio Fundamental da Contagem, o conjunto total de possibilidades é dado pelo produto das possibilidades para cada primo, assim:
[tex3]\text{ nº div}(m)=(k_1+1)(k_2+1)(k_3+1)...(k_n+1)[/tex3]

• Corolário 1: se [tex3]m[/tex3] tem apenas 2 divisores, [tex3]m[/tex3] é primo;

Demonstração:
Sabemos que [tex3]\text{ nº div}(m)=(k_1+1)(k_2+1)(k_3+1)...(k_n+1)[/tex3]. Queremos que esse número seja igual à 2. Como 2 é primo, ele não pode ser fatorado além disso, então para termos um produto de naturais iguais à 2, devemos ter um deles iguais à 2 e o resto igual à 1. Assim, sem perda de generalidade, podemos dizer que:
[tex3]k_1+1=2\implies k_1=1[/tex3]
[tex3]k_i+1=1\implies k_i=0,\space\space i\geq 2[/tex3]
Então, como [tex3]m=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}\cdot\space ... \space \cdot p_n^{k_n}[/tex3], temos:
[tex3]m=p_1^{1}\cdot p_2^{0} \cdot p_3^{0}\cdot\space ... \space \cdot p_n^{0}[/tex3]
[tex3]m=p_1[/tex3]
Como [tex3]p_1[/tex3] é primo, então [tex3]m[/tex3] é primo C.Q.D
[tex3]{}[/tex3]

• Corolário 2: se [tex3]m[/tex3] tem apenas 3 divisores, então [tex3]m[/tex3] é o quadrado de um primo;

Novamente, sabemos que [tex3]\text{ nº div}(m)=(k_1+1)(k_2+1)(k_3+1)...(k_n+1)[/tex3]. Queremos que esse número seja igual à 3. Como 3 é primo, ele não pode ser fatorado além disso, então para termos um produto de naturais iguais à 3, devemos ter um deles iguais à 3 e o resto igual à 1. Assim, sem perda de generalidade, podemos dizer que:
[tex3]k_1+1=3\implies k_1=2[/tex3]
[tex3]k_i+1=1\implies k_i=0,\space\space i\geq 2[/tex3]
Então, como [tex3]m=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}\cdot\space ... \space \cdot p_n^{k_n}[/tex3], temos:
[tex3]m=p_1^{2}\cdot p_2^{0} \cdot p_3^{0}\cdot\space ... \space \cdot p_n^{0}[/tex3]
[tex3]m=p_1^2[/tex3]
Como [tex3]p_1[/tex3] é primo, então [tex3]m[/tex3] é o quadrado de um primo C.Q.D

[Ittalo25MOD]

Se [tex3]m-n=1 [/tex3] tem um divisor, então [tex3]m-n=1 [/tex3]:

[tex3]m \cdot n = m \cdot (m-1)[/tex3] é quadrado perfeito, mas como [tex3]mdc(m,m-1)=1 [/tex3], então ambos são quadrados perfeitos: [tex3]\begin{cases}
m=x^2 \\
m-1=k^2
\end{cases}[/tex3], subtraindo as duas: [tex3]1 = (x-k) \cdot (x+k) [/tex3], mas como [tex3]0<k<x [/tex3], não existe solução para esse caso.


Se [tex3]m-n=1 [/tex3] tem dois divisores, então [tex3]m-n [/tex3] é um primo, digamos p:

[tex3]m\cdot n = m\cdot (m-p) = k^2 [/tex3]
[tex3]m^2-mp = k^2 [/tex3]
Olhando módulo p: [tex3]m^2 \equiv k^2 \equiv u \mod(p)[/tex3]
Se [tex3]u \equiv 0 \mod(p)[/tex3], isso significa que: [tex3]\begin{cases}
m=pc \\
k=pd
\end{cases}[/tex3]
Substituindo:
[tex3]m^2-mp = k^2 [/tex3]
[tex3]p^2c^2-p^2c = p^2d^2 [/tex3]
[tex3]c^2-c = d^2 [/tex3]
[tex3](c+d) \cdot (c-d)= c [/tex3]
Disso teríamos que [tex3]c+d | c [/tex3], absurdo.

Portanto [tex3]u \neq 0 \mod(p)[/tex3], ou seja, [tex3]m \neq 0 \mod(p)[/tex3] e sendo assim: [tex3]mdc(m,p)=1 [/tex3]
Mas [tex3]mdc(m,p)=mdc(m,m-n) = mdc(m,n) = 1 [/tex3]
Como no primeiro caso, para que [tex3]m\cdot n [/tex3] seja quadrado perfeito, então ambos são quadrados: [tex3]\begin{cases}
m=z^2 \\
n=t^2
\end{cases}[/tex3]
Sabemos que: [tex3]m-n = p [/tex3], portanto: [tex3](z-t) \cdot (z+t) = p [/tex3]
[tex3]\begin{cases}
z+t=p \\
z-t=1
\end{cases}[/tex3] [tex3]\rightarrow z^2 = \frac{(p+1)^2}{4}[/tex3]
Usando que [tex3]1000 \leq z^2 < 2005[/tex3], chegamos em [tex3]67 \leq p \leq 83[/tex3]
E portanto [tex3]p \in \{67,71,73,79,83\}[/tex3]
[tex3]\boxed {m \in \{1156,1296,1369,1600,1764\}}[/tex3]
[tex3]n \in \{1089,1225,1296,1521,1681\}[/tex3]
Sendo as soluções em ordem.

Se [tex3]m-n [/tex3] tem três divisores, então [tex3]m-n [/tex3] é um quadrado de um primo, conforme mostrado pelo Anthony.

[tex3]m \cdot n = m \cdot (m-p^2) = m^2 - mp^2 = v^2 [/tex3]
Da mesma forma que no caso anterior, não é possível que [tex3]m^2 \equiv v^2 \equiv 0 \mod(p^2) [/tex3]
Portanto [tex3]mdc(m,n) = 1 [/tex3]
Segue do mesmo modo que: [tex3](z+t) \cdot (z-t) = p^2 [/tex3].
[tex3]\begin{cases}
z+t=p^2 \\
z-t=1
\end{cases}[/tex3] [tex3]\rightarrow z^2 = \frac{(p^2+1)^2}{4}[/tex3]
Usando que [tex3]1000 \leq z^2 < 2005[/tex3], chegamos em [tex3]8 \leq p < 9[/tex3]. Sem solução para esse caso.

[AnthonyC]

Só por diversão, vou acrescentar o caso que faltou ali:
Corolário 3: se [tex3]m[/tex3] tem apenas um divisor, então [tex3]m=1[/tex3];
Sabemos que [tex3]\text{ nº div}(m)=(k_1+1)(k_2+1)(k_3+1)...(k_n+1)[/tex3]. Queremos que esse número seja 3. Porém, a única forma de multiplicar naturais e o resultado ser um, implica que todos eles devem ser iguai à 1, logo:
[tex3]k_i+1=1\implies k_i=0, \,\,\, 1\leq i\leq n[/tex3]
Como [tex3]m=p_1^{k_1}\cdot p_2^{k_2} \cdot p_3^{k_3}\cdot\space ... \space \cdot p_n^{k_n}[/tex3]:
[tex3]m=p_1^{0}\cdot p_2^{0} \cdot p_3^{0}\cdot\space ... \space \cdot p_n^{0}[/tex3]
[tex3]m=1\cdot1 \cdot 1\cdot\space ... \space \cdot1[/tex3]
[tex3]m=1[/tex3]
C.Q.D