Sembrerà stupido, ma una domanda mi assilla:
Se n|p-1, con p primo, esiste per forza un elemento che ha ordine n modulo p?
Se n|p-1
Beh ...
1) quante sono le soluzioni di $ x^q-1\equiv 0 \bmod p $ con q primo divisore di p-1?
2) quante sono le soluzioni di $ x^{q^k}-1\equiv 0\bmod p $ che non siano già soluzioni di $ x^{q^h}-1\equiv 0\bmod p $ per h<k?
3) quante sono le soluzioni di $ x^n-1\equiv 0\bmod p $ con n divisore di p-1 che non siano già soluzioni di $ x^m-1\equiv 0\bmod p $ con m divisore proprio di n?
1) quante sono le soluzioni di $ x^q-1\equiv 0 \bmod p $ con q primo divisore di p-1?
2) quante sono le soluzioni di $ x^{q^k}-1\equiv 0\bmod p $ che non siano già soluzioni di $ x^{q^h}-1\equiv 0\bmod p $ per h<k?
3) quante sono le soluzioni di $ x^n-1\equiv 0\bmod p $ con n divisore di p-1 che non siano già soluzioni di $ x^m-1\equiv 0\bmod p $ con m divisore proprio di n?
Visto che ci sono, scrivo la dimostrazione del risultato generale che implica l'esistenza di un generatore:
Lemma 1
$ ~ \sum_{d \mid n} \phi(d) = n $
Proof: quanti sono i numeri $ ~ 1 \le k \le n $ tali che $ ~ (k,n) = d $? ... ecco. Sommiamo sui vari d e abbiamo la formula.
Lemma 2
Un polinomio di grado n ha al max n radici modulo p.
Proof: per induzione. Un polinomio di grado 0 non ha radici.
Poi, sia r una radice di questo polinomio:
$ ~ P(x) = a_nx^n + \ldots + a_1x + a_0 = (x-r)Q(x) $
Ora, tutte e sole le radici di P sono r unita alle radici di Q, perchè:
$ ~ p \mid P(x) \Leftrightarrow p \mid (x-r)Q(x) \Leftrightarrow p \mid (x-r) \lor p \mid Q(x) $
Qui abbiamo usato appunto il fatto che p è primo. Altrimenti non funziona.
Lemma 3 Anzi, che lemma, chiamiamolo pure teorema:
$ ~ \mathrm{ord}_p x =d $ ha esattamente $ ~ \phi(d) $ soluzioni, se $ ~ d \mid \phi(p) $.
Supponiamo che questa legge valga su tutti i divisori propri di d. Dimostriamo che vale anche per d.
$ ~ x^d-1 \equiv 0 \pmod p $
Poichè $ ~ x^{p-1}-1 = (x^d-1)Q(x) $ ha p-1 soluzioni (per il teorema di Eulero) e per il lemma 2 Q(x) ha al più p-d-1 soluzioni, $ ~ x^d-1 $ ha almeno d soluzioni, sempre per il lemma 2 ne ha al più d, quindi ha esattamente d soluzioni.
I numeri che hanno per ordine un divisore di d sono quindi d. Ma per ipotesi induttiva, i numeri che hanno per ordine un divisore proprio di d sono:
$ ~ \sum_{k \mid d, k \neq d} \phi(k) $
Se applichiamo il lemma 1, vediamo che i numeri con ordine d devono essere proprio $ ~ \phi(d) $.
Il passo base di questa induzione (chiamiamola pure induzione ben fondata, poichè lavoriamo sul buon ordine dei divisori) sono i numeri con ordine 1... che è solo 1.
Piccola aggiunta: una volta saputo che esiste un generatore, si poteva anche dimostrare questo semplice risultato di teoria dei gruppi:
In un gruppo ciclico con n elementi, gli elementi di ordine d (con d|n) sono esattamente $ ~ \phi(d) $.
Lemma 1
$ ~ \sum_{d \mid n} \phi(d) = n $
Proof: quanti sono i numeri $ ~ 1 \le k \le n $ tali che $ ~ (k,n) = d $? ... ecco. Sommiamo sui vari d e abbiamo la formula.
Lemma 2
Un polinomio di grado n ha al max n radici modulo p.
Proof: per induzione. Un polinomio di grado 0 non ha radici.
Poi, sia r una radice di questo polinomio:
$ ~ P(x) = a_nx^n + \ldots + a_1x + a_0 = (x-r)Q(x) $
Ora, tutte e sole le radici di P sono r unita alle radici di Q, perchè:
$ ~ p \mid P(x) \Leftrightarrow p \mid (x-r)Q(x) \Leftrightarrow p \mid (x-r) \lor p \mid Q(x) $
Qui abbiamo usato appunto il fatto che p è primo. Altrimenti non funziona.
Lemma 3 Anzi, che lemma, chiamiamolo pure teorema:
$ ~ \mathrm{ord}_p x =d $ ha esattamente $ ~ \phi(d) $ soluzioni, se $ ~ d \mid \phi(p) $.
Supponiamo che questa legge valga su tutti i divisori propri di d. Dimostriamo che vale anche per d.
$ ~ x^d-1 \equiv 0 \pmod p $
Poichè $ ~ x^{p-1}-1 = (x^d-1)Q(x) $ ha p-1 soluzioni (per il teorema di Eulero) e per il lemma 2 Q(x) ha al più p-d-1 soluzioni, $ ~ x^d-1 $ ha almeno d soluzioni, sempre per il lemma 2 ne ha al più d, quindi ha esattamente d soluzioni.
I numeri che hanno per ordine un divisore di d sono quindi d. Ma per ipotesi induttiva, i numeri che hanno per ordine un divisore proprio di d sono:
$ ~ \sum_{k \mid d, k \neq d} \phi(k) $
Se applichiamo il lemma 1, vediamo che i numeri con ordine d devono essere proprio $ ~ \phi(d) $.
Il passo base di questa induzione (chiamiamola pure induzione ben fondata, poichè lavoriamo sul buon ordine dei divisori) sono i numeri con ordine 1... che è solo 1.
Piccola aggiunta: una volta saputo che esiste un generatore, si poteva anche dimostrare questo semplice risultato di teoria dei gruppi:
In un gruppo ciclico con n elementi, gli elementi di ordine d (con d|n) sono esattamente $ ~ \phi(d) $.