on 16.08.03 05:54, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: > Ol� pessoal! > > Prove que se n > 1 e a > 0 s�o inteiros ent�o n | PHY(a^n - 1). > > PHY � a fun��o de Euler. > > Abra�o, > Duda. >
Oi, Duda: Eh claro que mdc(a,a^n - 1) = 1 Entao, pelo teorema de Euler, teremos: a^Phi(a^n - 1) == 1 (mod a^n - 1) ==> a^n - 1 divide a^Phi(a^n - 1) - 1 ==> n divide Phi(a^n - 1) *** Essa ultima passagem pode ser vista da seguinte forma: Sejam x^n - 1 e x^n - 1 polinomios (portanto m, n inteiros) x^n - 1 divide x^m - 1 mas n nao divide m ==> m = qn + r com 0 < r <= n-1 ==> x^m - 1 = x^(qn + r) - 1 = x^(qn)*x^r - x^r + x^r - 1 = = x^r(x^(qn) - 1) + x^r - 1 ==> x^n - 1 divide x^r - 1 com 0 < r < n ==> contradicao. Um abraco, Claudio. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
