combinatoria o simile
Moderatore: tutor
un\'espressione che genera tutte le infinite (di solito) soluzioni di diofantee piuttosto standard di grado basso (o per lo meno ben determinato); non è il nostro caso, direi (sono pronto a ricredermi quando vedrò qualcosa del genere)
[img:2sazto6b]http://digilander.iol.it/daniel349/boy_math_md_wht.gif[/img:2sazto6b]
Credo che quello che fra intende con la parola \"generatore\" sia qualcosa di diverso da ciò che ha inteso di DD.
<BR>
<BR>In un certo modulo m, g è un generatore se ord_m(g)=phi(m), ovvero il minimo esponente n > 0 tale che g^n == 1 (m) è phi(n). Da ciò segue che le potenze di g, ovvero g, g²,..., g^(phi(m)-1) percorrono tutto il sistema di residui primi con m.
<BR>In altre parole, fissato un numero k tale che (k,m)=1 si ha che k == g^h (m), per qualche h.
<BR>E\' inoltre evidente che se esiste un generatore modulo m allora ne esistono esattamente phi(phi(m)): cioè tutte le potenze di g con esponente primo con phi(m).
<BR>Quando esiste un generatore? Esiste se (non ricordo se valga il solo se) m=2, 4, p^n, 2p^n, con p primo dispari.
<BR>
<BR>Ah, a proposito fra: in chat ho provato ad usare i generatori su questo problema, ma senza successo, e non credo che vi sia qualche modo di applicarli. Bisogna armarsi di pazienza e utilizzare l\'approccio \"evidente\".<BR><BR>[ Questo Messaggio è stato Modificato da: lordgauss il 14-09-2003 16:26 ]
<BR>
<BR>In un certo modulo m, g è un generatore se ord_m(g)=phi(m), ovvero il minimo esponente n > 0 tale che g^n == 1 (m) è phi(n). Da ciò segue che le potenze di g, ovvero g, g²,..., g^(phi(m)-1) percorrono tutto il sistema di residui primi con m.
<BR>In altre parole, fissato un numero k tale che (k,m)=1 si ha che k == g^h (m), per qualche h.
<BR>E\' inoltre evidente che se esiste un generatore modulo m allora ne esistono esattamente phi(phi(m)): cioè tutte le potenze di g con esponente primo con phi(m).
<BR>Quando esiste un generatore? Esiste se (non ricordo se valga il solo se) m=2, 4, p^n, 2p^n, con p primo dispari.
<BR>
<BR>Ah, a proposito fra: in chat ho provato ad usare i generatori su questo problema, ma senza successo, e non credo che vi sia qualche modo di applicarli. Bisogna armarsi di pazienza e utilizzare l\'approccio \"evidente\".<BR><BR>[ Questo Messaggio è stato Modificato da: lordgauss il 14-09-2003 16:26 ]
-
Ospite
La cosa più importante da sapere sui generatori è che in inglese si chiamano \"primitive root\"(s); da questa nozione si risale facilmente a tutto il resto <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>Il se e solo se vale ed è una facile conseguenza dell\'ordine moltiplicativo massimo (che a sua volta è conseguenza del teorema cinese sugli esponenti più un induzione per il caso p = 2)
<BR>
<BR>
<BR>Il se e solo se vale ed è una facile conseguenza dell\'ordine moltiplicativo massimo (che a sua volta è conseguenza del teorema cinese sugli esponenti più un induzione per il caso p = 2)
<BR>