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.
