Re:[obm-l] Homomorfismo sobrejetor

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

---------- Cabeçalho original -----------

De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia: 
Data: Fri, 23 Mar 2007 19:51:51 -0300 (ART)
Assunto: [obm-l] Homomorfismo sobrejetor

> Olá para todos! Estou com o seguinte problema:
>    
>   Seja d um divisor de n. Prove que o homomorfismo natural de (Z/nZ)* em 
>   (Z/dZ)* é sobrejetor. 
>   Obs.: (Z/mZ)* é o grupo das unidades do anel (Z/nZ).
>    
>   Eu pensei no seguinte: Tome k um elemento de (Z/dZ)*. Então (k,d)=1. Se (k,n)=1 então basta tomar k em (Z/nZ)*. 
Agora, se (k,n) > 1, então dentre os números {1,2,...,n/d-1} deve existir um i tal que (ik+d,n)=1. Porém, não consigo mostrar 
este último fato.
>    
>   Se alguém souber provar este fato, gostaria de ver a prova (ou se não for verdade, um contra-exemplo). Ou ainda, se 
alguém souber resolver o problema de outro modo...
>    
>   Grato,
>    
>   Tertuliano.
>    

Sejam p_1, ..., p_u, q_1, ..., q_v, r_1, ..., r_w os fatores primos de n, tais que: 
p_1, ..., p_u tambem dividem d (e sao, portanto, primos com k);
q_1, ..., q_v sao primos com d mas dividem k;
r_1, ..., r_w sao primos com d e k.

O problema eh encontrar um inteiro x tal que (kx+d,n) = 1, onde (k,d) = 1.
Assim, basta achar x tal que kx+d seja primo com cada fator primo de n.
Isso parece um trabalho para o teorema chines dos restos.

Para os p_i e r_j, que sao primos com k, usamos:
kx + d == 1 (mod p_i) (1<=i<=u)
kx + d == 1 (mod r_j) (1<=j<=w)

Seja x = x_0 a solucao (unica mod p_1*...*p_u*r_1*...*r_w) dessas u+w congruencias.
Eh claro que (kx_0 + d,p_i) = (kx_0 + d,r_j) = 1 (1<=i<=u e 1<=j<=w)

kx_0 + d == d (mod q_i) (1<=i<=v), pois q_i divide k.
Assim, (kx_0 + d,q_i) = (d,q_i) = 1.

Em suma, para cada fator primo p de n, vale (kx_0 + d,p) = 1.
Portanto, (kx_0 + d,n) = 1.

[]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
=========================================================================