OliForum Matematico

ragioniamo $ mod n $

allora se ho capito bene, un sistema completo di residui è:

$ 0,1,2,3,...,n-1 $

perchè sono presenti tutte le classi di resto modulo $ n $

giusto?

non ho ben capito come mai il ragazzo(di cui non nricordo il nome) che parla nei video del sito di Massimo Gobbino alla prima lezione sulla teoria dei numeri, dice che anche

$ 0,k,2k,3k,...,(n-1)k $è un sistema completo


per i generatori:

un generatore(ma ce ne possono essere anche di più) $ mod(p) $(con$ p $ primo) è un numero $ m $

tale che $ ord_p(m)=p-1 $

quindi che le potenze di m vanno a generare tutte le classi di resto modulo $ p $(tranne lo 0 che è a se)

mettiamo $ mod5 $

i due generatori sono 2 e 3

quindi significa che un qualunque numero < 5 è congruo a una potenza di 2 o di 3 $ mod5 $

giusto?


allora se g è un generatore mod p
si ha che

$ 0, g^0, g^1, g^2,..., g^p-1 $ è ancora un sistema completo di residui

e credo che fino a qui ci sono

quando però dice:

$ 0,1^m,2^m,3^m,4^m,5^m,6^m $
$ mod7 $(mi sembra)
sono(tranne lo zero) un sistema completo di generatori

ma non riesco a capire perchè sistema completo di generatori e non di residui
mi potreste spiegare?
grazie in anticipo per le risposte

matteo16 ha scritto: $ 0,k,2k,3k,...,(n-1)k $è un sistema completo

Provo a spiegartelo con una dimostrazione.

Sia dato il sistema completo di residui $ {\bmod{n}} $: $ S_1{ \{0,1,2,\dots , n-1\}} $.

Prendo un $ k\in \mathbb{N}\vert (k,n)=1 $.

Voglio dimostrare che $ S_2=\{0,k, 2k,\dots ,k(n-1)\} $ è un sistema completo di residui $ \bmod n $.

Si vede innanzitutto che i due insiemi, hanno la stessa cardinalità. Questo è un fatto necessario, ma non sufficiente.
Occorre dimostrare anche che dato un elemento $ i_1\in S_2 \Rightarrow \nexists i_2\in S_2 \vert i_1\equiv i_2 \pmod n $.

Supponiamo per assurdo che $ i_1, i_2 $ esistano.

Posso scrivere $ i_1=kj_1, i_2=kj_2 $ con $ j_1,j_2 \in S_1 $.

Allora, se $ i_1\equiv i_2 \pmod n \rightarrow kj_1\equiv kj_2 \pmod n $.
Essendo $ (k,n)=1 $ posso dividere e ottengo:
$ j_1\equiv j_2 \pmod n $ cioè che due elementi di $ S_1 $ abbiano la stessa congruenza $ \bmod n $ il che è assurdo.
Allora $ S_2 $ ha $ n $ elementi diversi tra loro, dunque è un sistema completo di residui $ \bmod n $.

Ti torna ora?

EUCLA ha scritto:

matteo16 ha scritto: $ 0,k,2k,3k,...,(n-1)k $è un sistema completo

Provo a spiegartelo con una dimostrazione.

Sia dato il sistema completo di residui $ {\bmod{n}} $: $ S_1{ \{0,1,2,\dots , n-1\}} $.

Prendo un $ k\in \mathbb{N}\vert (k,n)=1 $.

Voglio dimostrare che $ S_2=\{0,k, 2k,\dots ,k(n-1)\} $ è un sistema completo di residui $ \bmod n $.

Si vede innanzitutto che i due insiemi, hanno la stessa cardinalità. Questo è un fatto necessario, ma non sufficiente.
Occorre dimostrare anche che dato un elemento $ i_1\in S_2 \Rightarrow \nexists i_2\in S_2 \vert i_1\equiv i_2 \pmod n $.

Supponiamo per assurdo che $ i_1, i_2 $ esistano.

Posso scrivere $ i_1=kj_1, i_2=kj_2 $ con $ j_1,j_2 \in S_1 $.

Allora, se $ i_1\equiv i_2 \pmod n \rightarrow kj_1\equiv kj_2 \pmod n $.
Essendo $ (k,n)=1 $ posso dividere e ottengo:
$ j_1\equiv j_2 \pmod n $ cioè che due elementi di $ S_1 $ abbiano la stessa congruenza $ \bmod n $ il che è assurdo.
Allora $ S_2 $ ha $ n $ elementi diversi tra loro, dunque è un sistema completo di residui \bmod n.

Ti torna ora?

mmm sì ci devo un attimo ragionare cmq l'idea di base l'ho capita grazie

per gli altri dubbi?

Per il secondo:
Se $ g $ è il generatore $ \bmod n $ per qualsiasi intero $ b\vert (b,n)=1 $ vale $ b\equiv g^{k} \pmod n $.

Per il terzo:
Non riesco bene a capire il contesto in cui viene detto e onestamente mi fa un pò fatica andare a prendere il video però, per $ m=1 $ è un sistema completo di residui

matteo16 ha scritto: quando però dice:

$ 0,1^m,2^m,3^m,4^m,5^m,6^m $
$ mod7 $(mi sembra)
sono(tranne lo zero) un sistema completo di generatori

ma non riesco a capire perchè sistema completo di generatori e non di residui
mi potreste spiegare?
grazie in anticipo per le risposte

Sicuramente voleva dire "sistema completo di residui".

Vale in generale questo. Sia p un numero primo. Allora (trascurando lo 0 che è per le sue) l'insieme $ ~ 1^k,2^k,\ldots,(p-1)^k $ forma un sistema completo di residui se e soltanto se $ ~ (k,p-1)=1 $.

Per dimostrare questo, basta combinare:
- la dimostrazione di eucla
- l'esistenza di un generatore
Infatti la dimostrazione di eucla parla di sistemi completi di residui (in Z_n) che restano completi applicando un'operazione distributiva sulla somma. La tesi di adesso parla di sistemi completi di residui (in Z_n) che restano completi applicando un'operazione distributiva sul prodotto.
Ma il fatto che esista un generatore va interpretato come "le operazioni di prodotto in $ ~ \mathbbZ _p \setminus \{0\} $ e somma in $ ~ \mathbb{Z}_{p-1} $ si comportano allo stesso modo", quindi tramite un
generatore riconduci una dimostrazione all'altra.
Provare per credere...

edriv ha scritto:

matteo16 ha scritto: quando però dice:

$ 0,1^m,2^m,3^m,4^m,5^m,6^m $
$ mod7 $(mi sembra)
sono(tranne lo zero) un sistema completo di generatori

ma non riesco a capire perchè sistema completo di generatori e non di residui
mi potreste spiegare?
grazie in anticipo per le risposte

Sicuramente voleva dire "sistema completo di residui".

Vale in generale questo. Sia p un numero primo. Allora (trascurando lo 0 che è per le sue) l'insieme $ ~ 1^k,2^k,\ldots,(p-1)^k $ forma un sistema completo di residui se e soltanto se $ ~ (k,p-1)=1 $.

Per dimostrare questo, basta combinare:
- la dimostrazione di eucla
- l'esistenza di un generatore
Infatti la dimostrazione di eucla parla di sistemi completi di residui (in Z_n) che restano completi applicando un'operazione distributiva sulla somma. La tesi di adesso parla di sistemi completi di residui (in Z_n) che restano completi applicando un'operazione distributiva sul prodotto.
Ma il fatto che esista un generatore va interpretato come "le operazioni di prodotto in $ ~ \mathbbZ _p \setminus \{0\} $ e somma in $ ~ \mathbb{Z}_{p-1} $ si comportano allo stesso modo", quindi tramite un
generatore riconduci una dimostrazione all'altra.
Provare per credere...

ah ok quindi intendeva residui e non generatori, perchè l'ha anche ripetuto un sacco di volte. per fortuna, mi era già venuta l'ansia di non aver capito.

per la dimostrazione, la dimostrerò, almeno cercherò di dimostrarla XD.

grazie ancora a tutti e due

credo che 'sistema completo di residui' e 'sistema completo di generatori' vengano usati in maniera equivalente se stiamo ragionando modulo p primo, in quanto un sistema completo di residui (eccetto lo zero che , come detto da edriv, da noia) è anche un sistema contenente tutte le potenze del generatore