[obm-l] Polinomios e bijecoes em Z_p
Oi, pessoal: Preciso de ajuda com o problema de se determinar quando um polinomio de coeficientes inteiros eh uma bijecao em Z_p (Z_p: corpo dos inteiros mod p) Eu sei que podemos nos restringir a polinomios f(x) monicos de grau = p-1, pois se grau(f(x)) = p, basta tomar o resto da divisao de f(x) por x^p - x e se f(x) nao for monico, basta multiplica-lo pelo inverso do coeficiente lider. Baseado no fato de que nenhum polinomio de grau 2 eh uma bijecao, eu inicialmente pensei que um tal f(x) teria que ser da forma ax + b, onde a eh primo com p. Mas dai, descobri que f(x) = x^3 eh uma bijecao em Z_5 e, mais geralmente, f(x) = x^(p-2) eh uma bijecao em Z_p, pois: f(0) = 0 e se a 0, entao a^(p-1) = 1 == a^(p-2) = a^(-1) e o inverso de um elemento inversivel de qualquer corpo eh unico. Isso implica, mais geralmente, que f(x) = (ax + b)^(p-2) com (a,p) = 1 eh uma bijecao em Z_p. Mais geralmente ainda, se n for primo com p-1, entao f(x) = (ax + b)^n eh uma bijecao pois nesse caso existirao inteiros r, s tais que r*n + s*(p-1) = 1, e dai, em Z_p: x = x^1 = x^(r*n + s*(p-1)) = (x^n)^r * (x^(p-1))^s = (x^n)^r. Logo, a^n = b^n == a = (a^n)^r = (b^n)^r = b == x^n eh injetiva == x^n eh sobrejetiva, pois Z_p eh finito == x^n eh uma bijecao == f(x) = (ax + b)^n eh uma bijecao Minha pergunta: alem de f(x) = (ax + b)^n, com (a,p) = 1 e (n,p-1) = 1, existem outros polinomios que sao bijecoes em Z_p? []s, 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 =
Re: [obm-l] Polinomios e bijecoes em Z_p
On Tue, Mar 16, 2004 at 03:53:38PM -0300, Claudio Buffara wrote: Oi, pessoal: Preciso de ajuda com o problema de se determinar quando um polinomio de coeficientes inteiros eh uma bijecao em Z_p (Z_p: corpo dos inteiros mod p) ... Minha pergunta: alem de f(x) = (ax + b)^n, com (a,p) = 1 e (n,p-1) = 1, existem outros polinomios que sao bijecoes em Z_p? Claro que sim. Por interpolação (que já foi discutida o bastante quando falávamos de seqüências) *qualquer* função de Z/(p) em Z/(p) é dada por um polinômio de grau menor do que p. Ou seja, temos p! polinômios de grau p que dão bijeções de Z/(p) em Z/(p) e a sua expressão dá menos do que p^3 polinômios. Para p = 7 temos que p! é bem maior do que p^3. Mesmo para p = 5 existem polinômios que são bijeções e não são da forma que você descreveu. []s, N. = 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 =
[obm-l] Polinomios e bijecoes em Z_p (II)
Eu sou uma anta... O numero de polinomios distintos em Z_p de grau = p-1 eh p^p (incluindo o polinomio identicamente nulo). Mas o numero de funcoes de Z_p em Z_p eh igual a p^p. Isso implica que toda funcao de Z_p em Z_p eh um polinomio (!!!). *** Existem p! bijecoes de Z_p em Z_p. Logo, existirao apenas p! polinomios bijetivos. Quantos desses sao da forma f(x) = (ax + b)^n com (a,p) = (n,p-1) = 1? Teremos p-1 escolhas para a, p para b e Phi(p-1) para n. Total: p*(p-1)*Phi(p-1). Para p = 5, como Phi(p-1) (p-2)!, certamente vai existir algum polinomio bijetivo que nao eh da forma acima. A pergunta permanece: Quais sao eles? []s, 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 =
Re: [obm-l] Polinomios e bijecoes em Z_p
on 16.03.04 17:09, Nicolau C. Saldanha at [EMAIL PROTECTED] wrote: On Tue, Mar 16, 2004 at 03:53:38PM -0300, Claudio Buffara wrote: Oi, pessoal: Preciso de ajuda com o problema de se determinar quando um polinomio de coeficientes inteiros eh uma bijecao em Z_p (Z_p: corpo dos inteiros mod p) ... Minha pergunta: alem de f(x) = (ax + b)^n, com (a,p) = 1 e (n,p-1) = 1, existem outros polinomios que sao bijecoes em Z_p? Claro que sim. Por interpolação (que já foi discutida o bastante quando falávamos de seqüências) *qualquer* função de Z/(p) em Z/(p) é dada por um polinômio de grau menor do que p. Ou seja, temos p! polinômios de grau p que dão bijeções de Z/(p) em Z/(p) e a sua expressão dá menos do que p^3 polinômios. Para p = 7 temos que p! é bem maior do que p^3. Mesmo para p = 5 existem polinômios que são bijeções e não são da forma que você descreveu. []s, N. Eu me dei conta disso 1 minuto depois de ter mandado a minha msg. Mas ainda assim gostaria de saber se estes polinomios bijetivos tem alguma forma especial. Por exemplo, serah que todos os polinomios bijetivos sao obtidos a partir de composicoes dos polinomios da forma acima e possiveis reducoes mod x^p - x? Ou serah que esse eh um daqueles problemas cuja solucao eh feia e nao oferece nenhum tipo de insight estrutural? []s, 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 =
