Olimpíadas ⇒ (POTI) - Divisibilidade Tópico resolvido

[goncalves3718]

Seja [tex3]n > 1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n > 1[/tex3]

e [tex3]k [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k [/tex3]

um inteiro positivo qualquer. Prove que [tex3](n−1)^2|(n^k −1)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](n−1)^2|(n^k −1)[/tex3]

se, e somente se , [tex3](n−1)|k [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](n−1)|k [/tex3]

.

Acho que tem a ver com a fatoração da aula 1

[goncalves3718]

Temos:

[tex3]\frac{n^k-1^k}{(n-1)^2}=\frac{(n-1)}{n-1}\cdot\frac{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}{(n-1)}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^k-1^k}{(n-1)^2}=\frac{(n-1)}{n-1}\cdot\frac{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}{(n-1)}[/tex3]

, a primeira parte da expressão é divísivel, então resta:

[tex3]\frac{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}{(n-1)}=\frac {n^{k-1}}{(n-1)}+\frac{n^{k-2}}{(n-1)}+ ... \frac{(n-1)}{(n-1)}+\frac{1^{k-1}}{(n-1)}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}{(n-1)}=\frac {n^{k-1}}{(n-1)}+\frac{n^{k-2}}{(n-1)}+ ... \frac{(n-1)}{(n-1)}+\frac{1^{k-1}}{(n-1)}[/tex3]

Números da forma: [tex3]\frac{n^x-1}{(n-1)} [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^x-1}{(n-1)} [/tex3]

são inteiros, mas não consegui provar o que exercício pediu!

[deOliveira]

O que você quer é provar que [tex3](n-1)^2|(n^k-1)\iff (n-1)|k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](n-1)^2|(n^k-1)\iff (n-1)|k[/tex3]

Temos a fatoração [tex3]x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+...+xy^{n-2}+y^{n-1})[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+...+xy^{n-2}+y^{n-1})[/tex3]

(creio que você tenha se enganado na hora de fatorar, não tem esse n-1)

[tex3]n^k-1=(n^{k-1}+n^{k-2}+...+1)(n^k-1)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^k-1=(n^{k-1}+n^{k-2}+...+1)(n^k-1)[/tex3]

[tex3]\implies \frac{n^k-1}{(n-1)^2}=\frac{n^{k-1}+n^{k-2}+...+1}{n-1}=\\\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac n{n-1}+\frac1{n-1}=\\\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac n{n-1}+\frac1{n-1}+\frac k{n-1}-\frac{k}{n-1}=\\
\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}+\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\implies \frac{n^k-1}{(n-1)^2}=\frac{n^{k-1}+n^{k-2}+...+1}{n-1}=\\\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac n{n-1}+\frac1{n-1}=\\\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac n{n-1}+\frac1{n-1}+\frac k{n-1}-\frac{k}{n-1}=\\
\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}+\frac k{n-1}[/tex3]

Cada um dos [tex3]\frac{n^x-1}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^x-1}{n-1}[/tex3]

inteiro
[tex3](\Longleftarrow)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](\Longleftarrow)[/tex3]

[tex3]\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac k{n-1}[/tex3]

também é inteiro pois [tex3](n-1)|k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](n-1)|k[/tex3]

[tex3](\Longrightarrow)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](\Longrightarrow)[/tex3]

[tex3]\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac k{n-1}[/tex3]

é inteiro somente se [tex3](n-1)|k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](n-1)|k[/tex3]

Creio que seja isso. A sacada era somar e subtrair [tex3]\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac k{n-1}[/tex3]

.

Espero ter ajudado .

[goncalves3718]

[tex3]x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+...+xy^{n-2}+y^{n-1})[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+...+xy^{n-2}+y^{n-1})[/tex3]

, se [tex3]x=n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x=n[/tex3]

e [tex3]y=1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]y=1[/tex3]

, temos sim:

[tex3]{n^k-1^k}={(n-1)}\cdot{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]{n^k-1^k}={(n-1)}\cdot{(n^{k-1}+n^{k-2} ... n-1+ 1^{k-1})}[/tex3]

, certo?

[deOliveira]

Não
[tex3]n^k-1=(n-1)(n^{k-1}+n^{k-2}\cdot1+n^{k-3}\cdot1^2+...+n\cdot1^{k-2}+1^{k-1})=\\
(n-1)(n^{k-1}+n^{k-2}+...+n+1)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^k-1=(n-1)(n^{k-1}+n^{k-2}\cdot1+n^{k-3}\cdot1^2+...+n\cdot1^{k-2}+1^{k-1})=\\
(n-1)(n^{k-1}+n^{k-2}+...+n+1)[/tex3]

Repara que na aparece nenhum menos.
Repara também que [tex3]-1+1^{k-1}=-1+1=0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]-1+1^{k-1}=-1+1=0[/tex3]

[goncalves3718]

Ahh, entendi!! Vou acabar de ver sua resposta...

[goncalves3718]

Como chegou na conclusão, em que subtrai 1 de cada termo?

[tex3]\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}-\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}-\frac k{n-1}[/tex3]

[deOliveira]

[tex3]\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac{n}{n-1}+\frac{1}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+...+\frac{n}{n-1}+\frac{1}{n-1}[/tex3]

Vamos contar quantas frações temos aí, eu vou fazer da esquerda para a direita, mas tanto faz.
[tex3]\underbrace{\frac{n^{k-1}}{n-1}}_k+\underbrace{\frac{n^{k-2}}{n-1}}_{k-1}+...+\underbrace{\frac{n}{n-1}}_2+\underbrace{\frac{1}{n-1}}_1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\underbrace{\frac{n^{k-1}}{n-1}}_k+\underbrace{\frac{n^{k-2}}{n-1}}_{k-1}+...+\underbrace{\frac{n}{n-1}}_2+\underbrace{\frac{1}{n-1}}_1[/tex3]

Então eu posso "distribuir" o [tex3]-\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]-\frac k{n-1}[/tex3]

como tirando [tex3]1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1[/tex3]

de cada um dos denominadores.

[goncalves3718]

Não entendi.........

[deOliveira]

A gente tem isso:

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1}{n-1}[/tex3]

Eu vou somar e subtrair k do numerador.

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1+k-k}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1+k-k}{n-1}[/tex3]

Vou escrever [tex3]-k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]-k[/tex3]

como a soma de [tex3]k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k[/tex3]

menos uns

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1+k+(\underbrace{-1-1-...-1}_{k\ menos\ uns})}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}+n^{k-2}+...+n+1+k+(\underbrace{-1-1-...-1}_{k\ menos\ uns})}{n-1}[/tex3]

Agora como a adição é comutativa eu vou mudar a ordem dessas parcelas, eu vou colocar um -1 depois de cada [tex3]n^x[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^x[/tex3]

[tex3]\frac{(n^{k-1}-1)+(n^{k-2}-1)+...+(n-1)+(1-1)+k}{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{(n^{k-1}-1)+(n^{k-2}-1)+...+(n-1)+(1-1)+k}{n-1}[/tex3]

E aí a gente pode separar em várias frações

[tex3]\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}+\frac k{n-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+...+\frac {n-1}{n-1}+\frac{1-1}{n-1}+\frac k{n-1}[/tex3]

Obs: Tem de reparar que em [tex3]n^{k-1}+n^{k-2}+...+n+1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^{k-1}+n^{k-2}+...+n+1[/tex3]

existem k parcelas.
[tex3]n^{k-1}+n^{k-2}+...+n+1=\\n^{k-1}+n^{k-2}+...+n^{k-(k-1)}+n^{k-k}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^{k-1}+n^{k-2}+...+n+1=\\n^{k-1}+n^{k-2}+...+n^{k-(k-1)}+n^{k-k}[/tex3]

Contando as parcelas:
[tex3]\underbrace{n^{k-1}}_1+\underbrace{n^{k-2}}_2+...+\underbrace{n^{k-(k-1)}}_{k-1}+\underbrace{n^{k-k}}_k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\underbrace{n^{k-1}}_1+\underbrace{n^{k-2}}_2+...+\underbrace{n^{k-(k-1)}}_{k-1}+\underbrace{n^{k-k}}_k[/tex3]

(Dessa vez eu contei da direita para a esquerda, nessa contagem o número de cada parcela [tex3]n^{k-a}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n^{k-a}[/tex3]

é [tex3]a[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a[/tex3]

)