Sistema ridotto di residui

[ladepie]

In alcuni libri ho notato che un sistema ridotto di residui è un sottoinsieme di un sistema completo di residui tale che gli elementi sono primi con n. Tale sottoinsieme, modulo n, viene indicato con $S^{*}= \{ k_{1}, \cdots , k_{\varphi(n)} \}$ Però se indico con $S=\{k_1, \cdots, k_{n} \}$ il sistema completo dei residui, il $\varphi(n)$ nell'indice di $S^{*}$ cosa indica?

Se seguo la mia interpretazione ottengo:

Modulo 10: $S={1,2,3,4,5,6,7,8,9,10}$ $S^{*}= \{1,2,3,4 \}$ essendo $\varphi(10)=4$. Però in realtà secondo la definizione di sistema ridotto in modulo 10 $S^{*}=\{1,3,7,9 \}$

Quindi cosa si intende quando si dice che $S^{*}= \{ k_{1}, \cdots , k_{\varphi(n)} \}$ è un sistema ridotto di residui ovvero un insieme di numeri che non mai congruenti fra loro e che sono primi con n?

[mistake89]

Io non l'avevo mai sentito nominare. Credo tutta via che si debba ragionare così.
E' l'insieme delle classi $mod n$ i cui rappresentanti canonici sono coprimi con $n$, che sono ovviamente in numero $phi(n)$
Questo ovviamente ti permette di contarli, non ti dice quali sono.
Nel tuo esempio infatti essi sono in numero $phi(10)=4$ e sono quelli che hai individuato in un secondo tempo.

[ladepie]

beh si cosi' forse si...ma magari nominarli non con k!!

[Injo]

Sì, è sbagliato indicare entrambi con [tex]k[/tex]. Si dovrebbe dire che il sistema ridotto è [tex]\{r_1, ... r_{\phi(n)}\}[/tex] con [tex]\forall i \exists j : r_i\equiv k_j \bmod{n}[/tex].

[ladepie]

Infatti l'Apostol mi sa che usa un'altra lettera...

Comunque mi chiedevo anche questa cosa

Sia $S^*$ un sistema ridotto di residui e sia $U^*$ lo stesso sistema di prima soltanto che ogni elemento di $S^*$ eì stato moltiplicato per a primo con il modulo n.
Non riesco a provare che $a\cdot k_i \equiv t_i (modn)$ dove t_i è un generico elemento di S.
Pensavo di utilizzare il lemma di Euclide pero' boh...

[antonello palermo]

"ladepie":Infatti l'Apostol mi sa che usa un'altra lettera...

Comunque mi chiedevo anche questa cosa

Sia $S^*$ un sistema ridotto di residui e sia $U^*$ lo stesso sistema di prima soltanto che ogni elemento di $S^*$ eì stato moltiplicato per a primo con il modulo n.
Non riesco a provare che $a\cdot k_i \equiv t_i (modn)$ dove t_i è un generico elemento di S.
Pensavo di utilizzare il lemma di Euclide pero' boh...

si esatto si puo' far ricorso al lemma di Euclide: osservare che gli elementi di T sono in numero $\phi(n) $ ,dunque basta provare che
(1) sono a due a due incongrui modulo n
(2) ($a\cdot k_i ,n)=1$ che indica la coprimalità di ciascuno degli elementi prodotto ottenuti rispetto a n.
La dimostrazione di incongruità si ottiene facilmente per assurdo (è un semplice esercizio di dimostrazione con questa tecnica).
Provare la coprimalità richiede invece alcune semplici osservazioni di aritmetica,procedendo ancora per assurdo: poiché $(a,n)=1$ si ha che se fosse $(a\cdot k_i ,n)=d>1$ allora $d|n$ e $d|a\cdot k_i.$
Sia allora p un fattore primo del divisore comune d,segue che $p|n$ e $p|a\cdot k_i$. ma ora essendo p primo ne segue che p divide almeno uno dei due fattori $a$ o $k_i$, per ciascuno dei quali casi si arriva a contraddizione con le ipotesi di coprimalità.