Ecuatia x^2=1 in Z_n

[bae]

Fie \( n\in\mathbb{N} \), \( n\geq 2 \). Sa se determine numarul solutiilor ecuatiei \( x^2=1 \) in \( \mathbb{Z}_n \) si produsul acestora.

[Filip Chindea]

Rezolvare elementara:

Punem \( n = \prod_{k=1}^r p_k^{a_k} \) (conventiile cunoscute). Astfel, \( x^2 \equiv 1 \pmod{n} \) daca si numai daca \( p^a | x^2 - 1 \), pentru orice \( p^a \in \{ p_k^{a_k} \ : \ k \in \overline{1, r} \} \).
Pentru \( p \) impar, aceasta se intampla iff \( x \equiv \pm 1 \pmod{p^a} \).
In caz ca \( p = 2 \), observam unicele solutii \( x \equiv \pm 1, \pm (2^{a-1} + 1) \pmod{2^a} \).
Conform lemei chineze a resturilor, numarul de solutii este \( 2^{\omega(n) + s} \), cu
\( s = \left\{ \begin{array}{lc} 0 & v_2(n) \in \{0, 2\} \\ -1 & v_2(n) = 1 \\ 1 & v_2(n) \ge 3 \end{array} \right. \)

Produsul (în \( \mathbb{Z}_n \), banuiesc) rezulta straightforward (exercitiu!) din demonstratia lemei chineze a resturilor. Concret:

O solutie a sistemului \( x \equiv a_i \pmod{n_i} \), cu \( i < j \Rightarrow \gcd(n_i, n_j) = 1 \), este data de \( x = \sum a_i\ell_im_i \), unde \( M := \prod n_i \), \( m_i := M/n_i \), \( \ell_im_i \equiv 1 \pmod{n_i} \). Din coprimalitatea \( n_i \)-urilor obtinem si ca \( x \) este unica solutie modulo \( M \).

Indicatie. Orice \( \ell_i \) cu proprietatea zisa poate fi substituit prin \( \ell_i + kn_i \).

[bae]

Produsul (în \( \mathbb{Z}_n \), banuiesc) rezulta straightforward (exercitiu!) din demonstratia lemei chineze a resturilor.

Pai si cam cat este?

[lasamasatelas]

Este \( -1 \) daca \( n=4 \) sau \( n=p^k \) sau \( 2p^k \) cu \( p \) prim mai mare strict ca \( 2 \). In restul cazurilor e \( 1 \).