Resto da divisão
3 participantes
PiR2 :: Matemática :: Álgebra
Página 1 de 1
Resto da divisão
por Cristina Lins Dom 10 Dez 2017, 21:56
Determine o resto da divisão por 7 do número 1^7 + 2^7 + 3^7 + ...+ 100^7
Cristina Lins- Jedi
- Mensagens : 470
Data de inscrição : 01/03/2012
Idade : 66
Localização : Itapetininga - SP
Re: Resto da divisão
por superaks Dom 10 Dez 2017, 22:50
Pelo teorema de Fermat, sabemos que:
Se p é primo e a um inteiro, então:
p | a^p - a
Logo, existe um inteiro k tal que:
a^p - a = pk
a^p = pk + a
Ou seja, a^p deixa resto a na divisão por p.
Então, para saber o resto da divisão daquela soma por 7, basta somarmos os restos de cada termo por 7.
1^7 + 2^7 + ... + 100^7
Somando os restos de cada termo por 7, temos:
1 + 2 + 3 ... + 100 = (1 + 100)100/2 = 5050
Descobrindo o resto da divisão de 5050 por 7:
5050 |_7_
- 49 721
15
- 14
10
- 7
3
Portanto o resto será 3.
Se p é primo e a um inteiro, então:
p | a^p - a
Logo, existe um inteiro k tal que:
a^p - a = pk
a^p = pk + a
Ou seja, a^p deixa resto a na divisão por p.
Então, para saber o resto da divisão daquela soma por 7, basta somarmos os restos de cada termo por 7.
1^7 + 2^7 + ... + 100^7
Somando os restos de cada termo por 7, temos:
1 + 2 + 3 ... + 100 = (1 + 100)100/2 = 5050
Descobrindo o resto da divisão de 5050 por 7:
5050 |_7_
- 49 721
15
- 14
10
- 7
3
Portanto o resto será 3.
superaks- Mestre Jedi
- Mensagens : 525
Data de inscrição : 27/06/2016
Idade : 23
Localização : São Paulo, Guarulhos, Brasil
Re: Resto da divisão
por OBMarcos Seg 11 Dez 2017, 01:53
Esse foi meu raciocínio para resolver esse problema:
Para isso, demonstrarei esta seguinte proposição, por indução.
Se a soma de k com 101-k deixa resto 3 por 7 (é fato ) , e k7 + (101-k)7 também deixa resto 3 por 7, então o "próximo termo", (k+1)7 + (101-(k+1))7 também deixa resto 3 por 7.
Para k=1 é verdade, pois 1007 = 27 (mod7) = 2 (mod7) , no qual implica que o resto de 17 + 1007 é 1+2=3.
Por binômio de Newton, podemos desenvolver
(k+1)7 + (100-k)7 = S7p=0 ( 7p)kp + S7p=0 (7p)1007-p kp
= S7p=0 (7p )kp [1 + 1007-p ] Tirando do somatório quando p=0;
= 1 + 1007 + S7p=1 (7p )kp [1 + 1007-p ]
Esse último somatório é multiplo de 7, pois o (7p ) é múltiplo de 7, por p ser diferente de 0.
e como visto antes, 1 + 1007 deixa resto 3, assim (k+1)7 + (100-k)7 deixa resto 3, o que nos demonstra a proposição. Como k+1 + 100-k deixa resto 3, pela proposição já demonstrada, o próximo termo (k+2)7 + (99-k)7 também deixa resto 3 por 7, e como k+2 + 99-k deixa resto 3 por 7, o próximo termo também deixará resto 3, e assim por diante. Agora, vamos ao problema:
Podemos reordenar a soma
17 + 27 + ... + 1007
Aos pares, desse jeito
(17 + 1007 ) + (27 + 997 ) + ( 37 + 987 ) + ... + ( 507 + 517 )
e como demonstrado, sabemos que cada par de soma deixa resto 3 por 7, e como temos 50 pares, teremos um resto total de 150, no qual podemos reescrevê-lo como 7x21 + 3. Logo, o resto de toda essa soma é 3.
Para isso, demonstrarei esta seguinte proposição, por indução.
Se a soma de k com 101-k deixa resto 3 por 7 (é fato ) , e k7 + (101-k)7 também deixa resto 3 por 7, então o "próximo termo", (k+1)7 + (101-(k+1))7 também deixa resto 3 por 7.
Para k=1 é verdade, pois 1007 = 27 (mod7) = 2 (mod7) , no qual implica que o resto de 17 + 1007 é 1+2=3.
Por binômio de Newton, podemos desenvolver
(k+1)7 + (100-k)7 = S7p=0 ( 7p)kp + S7p=0 (7p)1007-p kp
= S7p=0 (7p )kp [1 + 1007-p ] Tirando do somatório quando p=0;
= 1 + 1007 + S7p=1 (7p )kp [1 + 1007-p ]
Esse último somatório é multiplo de 7, pois o (7p ) é múltiplo de 7, por p ser diferente de 0.
e como visto antes, 1 + 1007 deixa resto 3, assim (k+1)7 + (100-k)7 deixa resto 3, o que nos demonstra a proposição. Como k+1 + 100-k deixa resto 3, pela proposição já demonstrada, o próximo termo (k+2)7 + (99-k)7 também deixa resto 3 por 7, e como k+2 + 99-k deixa resto 3 por 7, o próximo termo também deixará resto 3, e assim por diante. Agora, vamos ao problema:
Podemos reordenar a soma
17 + 27 + ... + 1007
Aos pares, desse jeito
(17 + 1007 ) + (27 + 997 ) + ( 37 + 987 ) + ... + ( 507 + 517 )
e como demonstrado, sabemos que cada par de soma deixa resto 3 por 7, e como temos 50 pares, teremos um resto total de 150, no qual podemos reescrevê-lo como 7x21 + 3. Logo, o resto de toda essa soma é 3.
OBMarcos- Iniciante
- Mensagens : 20
Data de inscrição : 05/12/2017
Idade : 21
Localização : Belém, Pará, Brasil
Re: Resto da divisão
por Cristina Lins Seg 11 Dez 2017, 11:35
Bom dia
Tenho que entender melhor o teorema de Fermat.
O seu modo, Marcos , Tb vou estudar com carinho.
Muito obrigada aos dois. Estão me ajudando bastante.
Tenho que entender melhor o teorema de Fermat.
O seu modo, Marcos , Tb vou estudar com carinho.
Muito obrigada aos dois. Estão me ajudando bastante.
Cristina Lins- Jedi
- Mensagens : 470
Data de inscrição : 01/03/2012
Idade : 66
Localização : Itapetininga - SP
Tópicos semelhantesPiR2 :: Matemática :: Álgebra
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
