Fórum de Matemática
DÚVIDAS? Nós respondemos!

Um Fórum em Português dedicado à Matemática
Data/Hora: 28 mar 2024, 21:48

Os Horários são TMG [ DST ]




Fazer Nova Pergunta Responder a este Tópico  [ 3 mensagens ] 
Autor Mensagem
MensagemEnviado: 01 fev 2017, 03:07 
Offline

Registado: 01 fev 2017, 02:13
Mensagens: 7
Localização: Valinhos,Sao paulo
Agradeceu: 3 vezes
Foi agradecido: 2 vezes
Exercício 15.9 do livro 21 Aulas de Matemática Olímpica:

Os três últimos dígitos de 1978m são iguais aos três últimos dígitos de 1978n (1 ≤ m < n , m e n pertecem aos Naturais). Determine m e n tais que m+n seja mínimo. ( Cuidado! A resposta não 1+ϕ(1000) ).


*Esse exercício esta na seção em que é apresentado o Teorema de Euler-Fermat e o Pequeno Teorema de Fermat, então acredito que seja necessário usa-los na resolução.

*Sou novo no forum e não encontrei uma seção para teoria dos números. Não existe nenhuma ?


Topo
 Perfil  
 
MensagemEnviado: 01 fev 2017, 07:31 
Offline

Registado: 11 jan 2015, 02:31
Mensagens: 539
Localização: Covilhã
Agradeceu: 7 vezes
Foi agradecido: 298 vezes
É curioso que quando li este problema, lembrei-me que já o tinha resolvido algures. Fui vaguear pelos meus cadernos das aulas de Matemática Discreta e encontrei a solução. Vou então copiar a solução que o meu professor me deu.

O que queremos encontrar é que o número \(1978^n-1978^m=1978^m(1978^{n-m}-1)\) seja múltiplo de 1000. Isto é, o resto da divisão por 1000 é 0.
Ora \(1000=8\times 125\)

Assim 8 divide \(1978^m\) e como \(1978\equiv2\: (mod \: 8)\), concluímos que \(m\geq 3\)

E 125 divide \(1978^{n-m}-1\)

Pelo Teorema de Euler-Fermat \(1978^{\Phi (125)}\equiv1\: (mod \: 125)\)
\(\Phi (125)=125-25=100\)

E assim temos que: \(1978^{100}\equiv1\: (mod \: 125)\)

E portanto o valor mínimo de r tal que \(1978^{r}\equiv1\: (mod \: 125)\) tem que ser um divisor de 100. O que fica 9 possibilidades 1, 2, 4, 5, 10, 20, 25, 50, 100.

Ao testar as possibilidades reparamos que o menor valor de s tal que \(1978^{s}\equiv1\: (mod \: 5)\) é 4 e portanto r tem de ser um múltiplo de 4. O que resta 4,20 e 100 para verificar.

\(1978^{1}\equiv103\: (mod \: 125)
1978^{2}\equiv103^2\equiv109\:(mod \: 125)
1978^{4}\equiv109^2\equiv6\:(mod \: 125)
1978^{20}\equiv6^5\equiv26\:(mod \: 125)\)

Como para 4 e 20 o resto é diferente de 1. Então o r mais pequeno é 100.
Como o m mais pequeno possível é 3. Já que 8 divide \(1978^3\). Então temos que:

\(n-m=100\Rightarrow n=100+3=103\)

E temos a solução m=3 e n=103


Topo
 Perfil  
 
MensagemEnviado: 01 fev 2017, 15:08 
Offline

Registado: 01 fev 2017, 02:13
Mensagens: 7
Localização: Valinhos,Sao paulo
Agradeceu: 3 vezes
Foi agradecido: 2 vezes
Obrigado, ajudou bastante!!!


Topo
 Perfil  
 
Mostrar mensagens anteriores:  Ordenar por  
Fazer Nova Pergunta Responder a este Tópico  [ 3 mensagens ] 

Os Horários são TMG [ DST ]


Quem está ligado:

Utilizadores a ver este Fórum: Nenhum utilizador registado e 14 visitantes


Criar perguntas: Proibído
Responder a perguntas: Proibído
Editar Mensagens: Proibído
Apagar Mensagens: Proibído
Enviar anexos: Proibído

Pesquisar por:
Ir para:  
cron