Divisibilidade
2 participantes
PiR2 :: Questões Especiais :: Olimpíadas :: Matemática
Página 1 de 1
Divisibilidade
Mostre que n^13 - n eh divisivel por 105. (Dica: 105=3*5*7 )
Obs :. Estou tentando por inducao mas nao consigo
Obs :. Estou tentando por inducao mas nao consigo
pedrodemargomes- Iniciante
- Mensagens : 7
Data de inscrição : 10/08/2015
Idade : 27
Localização : brasil,pr,londrina
Re: Divisibilidade
Primeiro vamos trabalhar um pouco a expressão:
n¹³ - n
= n(n¹² - 1)
= n(n⁶ - 1)(n⁶ + 1) ---> a expressão é múltipla de (n⁶ - 1)
= n(n³ - 1)(n³ + 1)(n² + 1)(n⁴ - n² + 1)
= n(n - 1)(n² +n + 1)(n + 1)(n² - n + 1)(n² + 1)(n⁴ - n² + 1) ---> a expressão é múltipla de (n² - 1)
= n(n² + n + 1)(n² - n + 1)(n⁴ - n² + 1)(n² - 1)(n² + 1) ---> a expressão é múltipla de (n⁴ - 1)
Queremos provar que a expressão é divisível por 105. Como 105 = 3*5*7, se provarmos que a expressão é divisível por 3, por 5 e por 7, a demonstração estará concluída.
Já que 3, 5 e 7 são primos, façamos uma análise para um primo genérico p.
Se n for divisível pelo primo p, então a expressão, por ser múltipla de n, obviamente também o será.
Suponha, então, que n não é divisível por p, isto é, mdc(n, p) = 1. Do Pequeno Teorema de Fermat, temos:
np-1 ≡ 1 (mod p)
Aplicando para p = 3, p = 5 e p = 7:
n2 ≡ 1 (mod 3) ---> n² - 1 ≡ 0 (mod 3) ---> n² - 1 é divisível por 3
n⁴ ≡ 1 (mod 5) ---> n⁴ - 1 ≡ 0 (mod 5) ---> n³ - 1 é divisível por 5
n⁶ ≡ 1 (mod 7) ---> n⁶ - 1 ≡ 0 (mod 7) ---> n⁶ - 1 é divisível por 7
Como foi visto no início da postagem, n¹³ - n é múltiplo de n² - 1, de n³ - 1 e de n⁶ - 1. Mas como esses fatores são divisíveis por 3, 5 e 7 respectivamente, concluímos que n¹³ - n é divisível por 3*5*7 = 105.
Isso conclui a demonstração para n não divisível por 3 nem por 5 nem por 7.
No caso de n ser divisível por alguns elementos (mas não todos) de {3, 5, 7}, o raciocínio anterior demonstra que a expressão será divisível pelos elementos fora do subconjunto em questão. Portanto, qualquer que seja o caso, a expressão será divisível por 3*5*7 = 105.
Logo, n¹³ - n é sempre divisível por 105.
n¹³ - n
= n(n¹² - 1)
= n(n⁶ - 1)(n⁶ + 1) ---> a expressão é múltipla de (n⁶ - 1)
= n(n³ - 1)(n³ + 1)(n² + 1)(n⁴ - n² + 1)
= n(n - 1)(n² +n + 1)(n + 1)(n² - n + 1)(n² + 1)(n⁴ - n² + 1) ---> a expressão é múltipla de (n² - 1)
= n(n² + n + 1)(n² - n + 1)(n⁴ - n² + 1)(n² - 1)(n² + 1) ---> a expressão é múltipla de (n⁴ - 1)
Queremos provar que a expressão é divisível por 105. Como 105 = 3*5*7, se provarmos que a expressão é divisível por 3, por 5 e por 7, a demonstração estará concluída.
Já que 3, 5 e 7 são primos, façamos uma análise para um primo genérico p.
Se n for divisível pelo primo p, então a expressão, por ser múltipla de n, obviamente também o será.
Suponha, então, que n não é divisível por p, isto é, mdc(n, p) = 1. Do Pequeno Teorema de Fermat, temos:
np-1 ≡ 1 (mod p)
Aplicando para p = 3, p = 5 e p = 7:
n2 ≡ 1 (mod 3) ---> n² - 1 ≡ 0 (mod 3) ---> n² - 1 é divisível por 3
n⁴ ≡ 1 (mod 5) ---> n⁴ - 1 ≡ 0 (mod 5) ---> n³ - 1 é divisível por 5
n⁶ ≡ 1 (mod 7) ---> n⁶ - 1 ≡ 0 (mod 7) ---> n⁶ - 1 é divisível por 7
Como foi visto no início da postagem, n¹³ - n é múltiplo de n² - 1, de n³ - 1 e de n⁶ - 1. Mas como esses fatores são divisíveis por 3, 5 e 7 respectivamente, concluímos que n¹³ - n é divisível por 3*5*7 = 105.
Isso conclui a demonstração para n não divisível por 3 nem por 5 nem por 7.
No caso de n ser divisível por alguns elementos (mas não todos) de {3, 5, 7}, o raciocínio anterior demonstra que a expressão será divisível pelos elementos fora do subconjunto em questão. Portanto, qualquer que seja o caso, a expressão será divisível por 3*5*7 = 105.
Logo, n¹³ - n é sempre divisível por 105.
Robson Jr.- Fera
- Mensagens : 1263
Data de inscrição : 24/06/2012
Idade : 30
Localização : Rio de Janeiro, RJ
Re: Divisibilidade
Obrigado pela resposta, vou estudar um pouco o Pequeno Teorema de Fermat pois nunca tinha ouvido falar dele. Valeu !
pedrodemargomes- Iniciante
- Mensagens : 7
Data de inscrição : 10/08/2015
Idade : 27
Localização : brasil,pr,londrina
PiR2 :: Questões Especiais :: Olimpíadas :: Matemática
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
|
|