TEN 2007

Ho appena finito il 4° del foglio numero 2 (ditemi cosa ne pensate):

a)Zn*={x: mcd(x,n)=1)
H={x: x^2=1 mod n} = {x=+-1 mod n}

=> n|x^2-1 => n|(x+1)*(x-1)

di conseguenza n dividerà uno dei due fattori ma non x, per cui, in ogni caso, varrà che mcd(x,n)=1.
Quindi tutti gli elementi che sono in H hanno mcd(x,n)=1 e di conseguenza H è un sottogruppo di Zn*.

Nota: forse si dovrebbe controllare che presi due elementi h1 e h2 di H il loro prodotto sia ancora in H....(?)

b) se supponiamo che n=p*q (2 divisori)
=>p*q|(x+1)*(x-1) le possibili soluzioni sono 4: p|x+1, p|x-1, q|x+1, q|x-1... e così via se ci sono 3 divisori di n
=> 2^(divisori di n)

c)H={1,4,11,14} per n=91

Siete daccordo?(La notazione è più che minimale per ovvi motivi di tempo...)

Sui primi due punti sono d'accordo (forse sul primo dovresti dimostrare anche che per ogni elemento di H, anche l'inverso si trova in H).
Il punto "c" non l'ho capito... 4^2=16 è non è 1 mod91!!!
Non ho interpretato bene l'esercizio??

Scusa ho fatto confusione con un esempio fatto per autoconvincermi (n=15)...

Comunque per n=91, H={1, 27, 64, 90}

lionel ha scritto:

Sui primi due punti sono d'accordo (forse sul primo dovresti dimostrare anche che per ogni elemento di H, anche l'inverso si trova in H).

Dato che l'inverso è definito come x*x^-1=1 e ogni elemento di H elevato al quadrato da 1...per definizione l'inverso di x in H è.... x!!! quindi ogni elemento di H possiede un inverso (che in questo caso è se stesso)

Scusa un attimo.. tu hai detto che, dato che n non divide x, allora mcd(x,n)=1. Ma nè x nè n sono necessariamente primi, quindi potrebbero avere un fattore in comune.. o mi sfugge qualcosa?

Salve a tutti,
qualcuno sa spiegarmi come funziona il calcolo del logaritmo discreto quando si vuole spezzare il problema in due sottogruppi?
Grazie.