Página 1 de 1
(Olimpíada Indiana) Teoria dos Números
Enviado: 02 Set 2020, 16:39
por Deleted User 24633
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]
.
Re: (Olimpíada Indiana) Teoria dos Números
Enviado: 02 Set 2020, 22:32
por Ittalo25
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
Re: (Olimpíada Indiana) Teoria dos Números
Enviado: 03 Set 2020, 17:40
por Deleted User 24633
Ittalo25 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]
[...]
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 ficaria
[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]
Re: (Olimpíada Indiana) Teoria dos Números
Enviado: 03 Set 2020, 17:57
por Ittalo25
pedro1729 escreveu: ↑03 Set 2020, 17:40
Ittalo25 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]
[...]
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 ficaria
[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]
A raiz primitiva x nada tem a ver com n ou q.
Re: (Olimpíada Indiana) Teoria dos Números
Enviado: 03 Set 2020, 18:02
por Deleted User 24633
Ittalo25 escreveu: ↑03 Set 2020, 17:57
pedro1729 escreveu: ↑03 Set 2020, 17:40
Ittalo25 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]
[...]
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 ficaria
[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]
A raiz primitiva x nada tem a ver com n ou q.
Ahh... agora entendi o que você fez; achei que você tinha feito outra coisa; perdão. Mas isso me fez ver outra solução....
Re: (Olimpíada Indiana) Teoria dos Números
Enviado: 03 Set 2020, 18:42
por Deleted User 24633
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!