mateforum.ro

Fie \( A \) un inel finit cu \( |A|=n \), unde \( n \) e liber de patrate.Demonstrati ca \( x^{\phi(n)+1}=x,\ \forall x \in A. \)

Aceasta problema apare in demonstratia algoritmului RSA de criptare pentru cazul cand \( n=pq \), p,q prime.

Cum n este liber de patrate, avem \( n=p_1p_2...p_k \) cu \( p_i \) prime distincte si se arata usor (folosind eventual teorema lui Cauchy) ca exista in grupul \( (A,+) \) elementele \( a_1, a_2, ... , a_k \) de ordin \( p_1, p_2, ... , p_k \) si cum grupul \( (A,+) \) este comutativ obtin ca elementul \( x_1+x_2+...+x_2 \) are ordinul \( p_1p_2...p_k \), adica \( n \), deci inelul este ciclic, deci va fi izomorf cu \( Z_n \) si acum rezultatul se obtine din teorema lui Euler.

S-a mai discutat si aici iar o solutie a fost data chiar de catre initiatorul acestui topic.

Da, prima parte s-a mai postat. A doua parte nu rezulta chiar direct din teorema lui Euller. Mai intai trebuie demonstrat izomorfismul \( Z_n \approx Z_{p_1} \times Z_{p_2} \times \cdot \times Z_{p_k} \), folosind Lema Chineza (sau poate sa fie folosita direct lema). M-am gandit ca e o problema buna ca parte teoretica si mi s-a parut interesant ca e folosita la o chestie practica.