Olimpíadas ⇒ (Bulgária 2005) Teoria dos Números Tópico resolvido
Moderador: [ Moderadores TTB ]
-
rean 
- Mensagens: 644
- Registrado em: Seg 26 Mar, 2007 10:31
- Última visita: 27-10-22
- Localização: Recife
- Contato:
Set 2007
27
09:57
(Bulgária 2005) Teoria dos Números
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.
Última edição: MateusQqMD (Seg 06 Jul, 2020 15:48). Total de 2 vezes.
Razão: tex --> tex3
Razão: tex --> tex3
Jul 2020
02
17:25
Re: (Bulgária 2005) Teoria dos Números
Vou provar aqui um resultado e dois corolários que usarei depois:
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]
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]
[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
- Número de divisores de [tex3]m[/tex3] :
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;
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;
[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
[tex3]\color{YellowOrange}\textbf{Não importa o quanto se esforce ou evolua, você sempre estará abaixo do Sol}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
Jul 2020
03
12:52
Re: (Bulgária 2005) Teoria dos Números
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.
[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.
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
Jul 2020
06
15:46
Re: (Bulgária 2005) Teoria dos Números
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
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
Última edição: AnthonyC (Seg 06 Jul, 2020 15:47). Total de 1 vez.
[tex3]\color{YellowOrange}\textbf{Não importa o quanto se esforce ou evolua, você sempre estará abaixo do Sol}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
[tex3]\textbf{Escanor}[/tex3]
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 2 Respostas
- 551 Exibições
-
Última msg por Ornitologo
-
-
Nova mensagem (Bulgária) Trigonometria
por Deleted User 23699 » » em Olimpíadas- 3 Respostas
- 992 Exibições
- Última msg por Ittalo25
- 1 Respostas
- 729 Exibições
-
Última msg por AnthonyC
- 2 Respostas
- 819 Exibições
-
Última msg por Tassandro
- 1 Respostas
- 467 Exibições
-
Última msg por rcompany
-
