Pelo algoritmo das divisões sucessivas, disso concluímos também que, conforme sugerido pelo Pedro, de fato mdc(a^m - 1, a^n - 1) = a^mdc(m, n) - 1
Artur Costa Steiner > Em 10/07/2014, às 16:05, Artur Costa Steiner <[email protected]> > escreveu: > > Isto é uma consequência da demonstração que eu dei para aquele outro problema: > > Veja que r é o resto da divisão de m por n. E do último parágrafo conclui-se > a^r - 1 é o resto da divisão de a^m - 1 por a^n - 1. > > OK? > > Artur > >> Observemos que a^m - 1 = (a - 1)(1 + a...+ a^(m - 1)). >> >> Suponhamos que n divida m. Então, m = kn para algum inteiro positivo k. >> Logo, >> >> a^m- 1 = a^(kn) - 1 = ((a^n))^k - 1 = (a^n - 1) (1 + a^n ... + ...(a^n)^(k - >> 1)). >> >> Como no parênteses da direita do segundo membro as parcelas são todas >> inteiras, fica demonstrado que a^n - 1 divide a^m - 1. >> >> Suponhamos agora que n não divida m Existem então um inteiro positivo k e um >> inteiro 0 < r < n tais que m = kn + r. Assim, >> >> a^m - 1 = a^(kn + r) - 1 = a^r a^(kn) - 1 = a^r a^(kn) - a^r + a^r - 1= >> a^r[a^(kn) - 1] + a^r - 1. >> >> Como n divide kn, segue-se da conclusão anterior que a^n - 1 divide a^(kn) - >> 1, havendo assim um inteiro positivo c tal que a^(kn) - 1 = c(a^n - 1). >> Temos portanto que >> >> a^m - 1 = c a^r (a^n - 1) + a^r - 1. >> >> ca^r é inteiro. E como a > 1 e r < m, a^r - 1 < a^m - 1. Da igualdade acima >> concluímos então que a^n - 1 não divide a^m - 1. A recíproca fica assim >> demonstrada por contraposição. > > > > Artur Costa Steiner > >> Em 10/07/2014, às 15:26, Ennius Lima <[email protected]> escreveu: >> >> Desculpem-me o equÃvoco. Faço a correção. >> >> Teorema: >> O resto da divisão euclidiana de a^m - 1 por a^n - 1 é a^r - 1, sendo r o >> resto da divisão euclidiana de m por n. >> (a, m e n são inteiros positivos; a>1, m>=n ) >> >> Abraços do Ennius! >> ________________ >> >> >>  >>  >> >> >> >> >> >> De: [email protected] >> Enviada: Quarta-feira, 9 de Julho de 2014 21:10 >> Para: [email protected] >> Assunto: [obm-l] O mesmo resto >> >> Olá, pessoal! >> >> Aproveitando as recentes questões, proponho a demonstração do seguinte >> teorema: >> >> "O resto da divisão euclidiana de a^m - 1 por a^n - 1 é o mesmo resto da >> divisão euclidiana de m por n." >> (a, m e n são inteiros positivos; a>1 e m>=n) >> >> Agradeço a atenção de vocês. >> Abraços do Ennius! >> _______________________________________ >>  >> -- >> Esta mensagem foi verificada pelo sistema de antiv�rus e >> acredita-se estar livre de perigo. >> >> >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. >> -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
