Seja [tex3]n[/tex3]
um inteiro positivo tal que [tex3]n[/tex3]
é um divisor da soma
[tex3]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1 + (1^{n-1} + 2^{n-1} + \dots + {(n-1)}^{n-1}).[/tex3]
Prove que [tex3]n[/tex3]
não é divisível por qualquer quadrado maior que [tex3]1[/tex3]
.
Olimpíadas ⇒ (Olimpíada Indiana) Teoria dos Números Tópico resolvido
Moderador: [ Moderadores TTB ]
-
Deleted User 24633
- Última visita: 31-12-69
Set 2020
02
16:39
(Olimpíada Indiana) Teoria dos Números
Editado pela última vez por Deleted User 24633 em 02 Set 2020, 16:40, em um total de 1 vez.
-
Ittalo25
- Mensagens: 2349
- Registrado em: 18 Nov 2013, 22:11
- Última visita: 27-03-24
- Agradeceu: 299 vezes
- Agradeceram: 1401 vezes
Set 2020
02
22:32
Re: (Olimpíada Indiana) Teoria dos Números
Seja n = pq, onde p é primo. Então:
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(-2)}^{n-1}+ {(-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(p-2)}^{n-1}+ {(p-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
Seja x uma raiz primitiva módulo p, então:
[tex3]1 + 1 + x^{n-1} + \dots + x^{(p-3)(n-1)}+ {x}^{(p-2)(n-1)} \equiv 0 \mod(p)[/tex3]
Se [tex3]p-1| n-1 [/tex3] , então pelo pequeno teorema de fermat:
[tex3]1 + 1\cdot (p-1) \equiv p \equiv 0 \mod(p)[/tex3]
se [tex3]p-1 [/tex3] não divide [tex3]n-1 [/tex3] , então:
[tex3]1 + \frac{(x^{n-1})^{p-1}-1}{x^{n-1}-1}\equiv 1 \mod(p)[/tex3]
Portanto existe o p, desde que [tex3]p-1| n-1 [/tex3] , assim:
[tex3]1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv -1 \mod(p)[/tex3]
Ou seja:
[tex3]1+1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 1+q\sum_{i=1}^{p-1}i^{n-1}\equiv 1-q \mod(p)[/tex3]
Ou seja: [tex3]p | q-1 [/tex3]
Mas se [tex3]p|q [/tex3] , não teria como [tex3]p | q-1 [/tex3] , portanto mdc(p,q) = 1 e está provado
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(-2)}^{n-1}+ {(-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(p-2)}^{n-1}+ {(p-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
Seja x uma raiz primitiva módulo p, então:
[tex3]1 + 1 + x^{n-1} + \dots + x^{(p-3)(n-1)}+ {x}^{(p-2)(n-1)} \equiv 0 \mod(p)[/tex3]
Se [tex3]p-1| n-1 [/tex3] , então pelo pequeno teorema de fermat:
[tex3]1 + 1\cdot (p-1) \equiv p \equiv 0 \mod(p)[/tex3]
se [tex3]p-1 [/tex3] não divide [tex3]n-1 [/tex3] , então:
[tex3]1 + \frac{(x^{n-1})^{p-1}-1}{x^{n-1}-1}\equiv 1 \mod(p)[/tex3]
Portanto existe o p, desde que [tex3]p-1| n-1 [/tex3] , assim:
[tex3]1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv -1 \mod(p)[/tex3]
Ou seja:
[tex3]1+1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 1+q\sum_{i=1}^{p-1}i^{n-1}\equiv 1-q \mod(p)[/tex3]
Ou seja: [tex3]p | q-1 [/tex3]
Mas se [tex3]p|q [/tex3] , não teria como [tex3]p | q-1 [/tex3] , portanto mdc(p,q) = 1 e está provado
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
Deleted User 24633
- Última visita: 31-12-69
Set 2020
03
17:40
Re: (Olimpíada Indiana) Teoria dos Números
Ittalo25 acho que você cometeu um erro aqui. Se [tex3]n=pq[/tex3] então cada classe de equivalência [tex3]\pmod p[/tex3] aparece [tex3]q[/tex3] vezes; então ficariaIttalo25 escreveu: ↑02 Set 2020, 22:32 Seja n = pq, onde p é primo. Então:
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(-2)}^{n-1}+ {(-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(p-2)}^{n-1}+ {(p-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
Seja x uma raiz primitiva módulo p, então:
[tex3]1 + 1 + x^{n-1} + \dots + x^{(p-3)(n-1)}+ {x}^{(p-2)(n-1)} \equiv 0 \mod(p)[/tex3]
Se [tex3]p-1| n-1 [/tex3] , então pelo pequeno teorema de fermat:
[tex3]1 + 1\cdot (p-1) \equiv p \equiv 0 \mod(p)[/tex3] [...]
[tex3]1 + q( 1+ x^{n-1} +.... + x^{(p-3)(n-1)} + x^{(p-2)(n-1}) \equiv 0 \pmod p[/tex3] e se [tex3]p-1 \mid n-1:[/tex3]
[tex3]1+q(p-1) \equiv 0 \pmod p \iff q-1 \equiv 0 \pmod p[/tex3] ou seja [tex3]p \mid q-1.[/tex3]
Editado pela última vez por Deleted User 24633 em 03 Set 2020, 17:52, em um total de 5 vezes.
-
Ittalo25
- Mensagens: 2349
- Registrado em: 18 Nov 2013, 22:11
- Última visita: 27-03-24
- Agradeceu: 299 vezes
- Agradeceram: 1401 vezes
Set 2020
03
17:57
Re: (Olimpíada Indiana) Teoria dos Números
A raiz primitiva x nada tem a ver com n ou q.pedro1729 escreveu: ↑03 Set 2020, 17:40Ittalo25 acho que você cometeu um erro aqui. Se [tex3]n=pq[/tex3] então cada classe de equivalência [tex3]\pmod p[/tex3] aparece [tex3]q[/tex3] vezes; então ficariaIttalo25 escreveu: ↑02 Set 2020, 22:32 Seja n = pq, onde p é primo. Então:
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(-2)}^{n-1}+ {(-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(p-2)}^{n-1}+ {(p-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
Seja x uma raiz primitiva módulo p, então:
[tex3]1 + 1 + x^{n-1} + \dots + x^{(p-3)(n-1)}+ {x}^{(p-2)(n-1)} \equiv 0 \mod(p)[/tex3]
Se [tex3]p-1| n-1 [/tex3] , então pelo pequeno teorema de fermat:
[tex3]1 + 1\cdot (p-1) \equiv p \equiv 0 \mod(p)[/tex3] [...]
[tex3]1 + q( 1+ x^{n-1} +.... + x^{(p-3)(n-1)} + x^{(p-2)(n-1}) \equiv 0 \pmod p[/tex3] e se [tex3]p-1 \mid n-1:[/tex3]
[tex3]1+q(p-1) \equiv 0 \pmod p \iff q-1 \equiv 0 \pmod p[/tex3] ou seja [tex3]p \mid q-1.[/tex3]
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
Deleted User 24633
- Última visita: 31-12-69
Set 2020
03
18:02
Re: (Olimpíada Indiana) Teoria dos Números
Ahh... agora entendi o que você fez; achei que você tinha feito outra coisa; perdão. Mas isso me fez ver outra solução....Ittalo25 escreveu: ↑03 Set 2020, 17:57A raiz primitiva x nada tem a ver com n ou q.pedro1729 escreveu: ↑03 Set 2020, 17:40Ittalo25 acho que você cometeu um erro aqui. Se [tex3]n=pq[/tex3] então cada classe de equivalência [tex3]\pmod p[/tex3] aparece [tex3]q[/tex3] vezes; então ficariaIttalo25 escreveu: ↑02 Set 2020, 22:32 Seja n = pq, onde p é primo. Então:
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(n-2)}^{n-1}+ {(n-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(-2)}^{n-1}+ {(-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
[tex3]1 + 1^{n-1} + 2^{n-1} + \dots + {(p-2)}^{n-1}+ {(p-1)}^{n-1} \equiv 0 \mod(p)[/tex3]
Seja x uma raiz primitiva módulo p, então:
[tex3]1 + 1 + x^{n-1} + \dots + x^{(p-3)(n-1)}+ {x}^{(p-2)(n-1)} \equiv 0 \mod(p)[/tex3]
Se [tex3]p-1| n-1 [/tex3] , então pelo pequeno teorema de fermat:
[tex3]1 + 1\cdot (p-1) \equiv p \equiv 0 \mod(p)[/tex3] [...]
[tex3]1 + q( 1+ x^{n-1} +.... + x^{(p-3)(n-1)} + x^{(p-2)(n-1}) \equiv 0 \pmod p[/tex3] e se [tex3]p-1 \mid n-1:[/tex3]
[tex3]1+q(p-1) \equiv 0 \pmod p \iff q-1 \equiv 0 \pmod p[/tex3] ou seja [tex3]p \mid q-1.[/tex3]
Editado pela última vez por Deleted User 24633 em 03 Set 2020, 18:48, em um total de 3 vezes.
-
Deleted User 24633
- Última visita: 31-12-69
Set 2020
03
18:42
Re: (Olimpíada Indiana) Teoria dos Números
Realmente.... a questão era mais fácil do que eu pensei; sua solução provou algo muito mais forte Ittalo25: [tex3]p \mid q - 1.[/tex3]
Dava para ser menos refinado!
Seja [tex3]p[/tex3] primo tal que [tex3]p \mid n[/tex3] e [tex3]q:= \dfrac{n}{p}.[/tex3]
Note que dentre os números [tex3]1, \ 2, \dots , (n-1)[/tex3] cada classe de equivalência (excluindo o zero) aparece exatamente [tex3]q[/tex3] vezes; assim
[tex3]-1 \equiv 1^{n-1} + 2^{n-1} + \dots +(n-1) ^{n-1} \equiv q[ 1^{n-1} + 2^{n-1} + \dots + {(p-1)}^{p-1}] \pmod p[/tex3]
e logo [tex3]p \not \mid q[/tex3] ou seja [tex3]\operatorname{mdc} (p,q)= 1[/tex3] e a prova está concluída.
Mas não deixo de agradecer o Ittalo25 pela solução que me fez ver essa solução mais simples e provou algo muito mais interessante!
Seja [tex3]p[/tex3] primo tal que [tex3]p \mid n[/tex3] e [tex3]q:= \dfrac{n}{p}.[/tex3]
Note que dentre os números [tex3]1, \ 2, \dots , (n-1)[/tex3] cada classe de equivalência (excluindo o zero) aparece exatamente [tex3]q[/tex3] vezes; assim
[tex3]-1 \equiv 1^{n-1} + 2^{n-1} + \dots +(n-1) ^{n-1} \equiv q[ 1^{n-1} + 2^{n-1} + \dots + {(p-1)}^{p-1}] \pmod p[/tex3]
e logo [tex3]p \not \mid q[/tex3] ou seja [tex3]\operatorname{mdc} (p,q)= 1[/tex3] e a prova está concluída.
Mas não deixo de agradecer o Ittalo25 pela solução que me fez ver essa solução mais simples e provou algo muito mais interessante!
Editado pela última vez por Deleted User 24633 em 03 Set 2020, 20:53, em um total de 7 vezes.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última mensagem
-
-
Nova mensagem (Olimpíada Balcânica Júnior-2009) Teoria dos Números
por Auto Excluído (ID:17906) » » em Olimpíadas - 3 Respostas
- 1103 Exibições
-
Última mensagem por undefinied3
-
-
- 1 Respostas
- 915 Exibições
-
Última mensagem por AugustoITA
-
- 1 Respostas
- 791 Exibições
-
Última mensagem por AugustoITA
-
- 2 Respostas
- 686 Exibições
-
Última mensagem por Ornitologo
