Re: [obm-l] Teoria dos Números

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 16.08.03 05:54, Eduardo Casagrande Stabel at dudasta@terra.com.br 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
=========================================================================