| trouvailles mathématiques 
alphabet phonétique (étendu) | 
autres | 
unicode
| |
quels nombres tester pour trouver une racine primitive ?
12 décembre 2023je reprends enfin du temps pour écrire ici ! bon, vous le savez peut-être, les seules valeurs de n pour lesquelles ℤ/nℤ× est cyclique sont n = 2, 4, pk and 2pk pour p premier impair et k ∈ ℕ. le problème est que trouver un générateur (appelé racine primitive) qui permette de faire des calculs concrets avec ce fait, ça peut s'avérer assez compliqué. le problème, c'est qu'on n'a pratiquement rien sur le sujet qui soit vraiment prouvé, surtout quelques conjectures comme celle d'artin.
pour de petites valeurs de n, c'est assez simple de trouver des racines primitives : $$\left\{\begin{array}l\mathbb Z/1\mathbb Z^\times=\left<0,\cdot\right>\\\mathbb Z/2\mathbb Z^\times=\left<1,\cdot\right>\\\mathbb Z/3\mathbb Z^\times=\left<-1,\cdot\right>\\\mathbb Z/4\mathbb Z^\times=\left<-1,\cdot\right>\end{array}\right.$$ mais au-delà, ça devient assez chaotique, et aucune des valeurs précédentes ne fonctionnent en tant que racines primitives. du coup, pour palier ce problème, j'ai décidé de coder un truc qui calcule la plus petite racine primitive ce qui, pour être clair, signifie le représentant le plus proche de 0 parmi toutes les classes de racines primitives, donc ça peut être 2, 3, &c comme ça peut être -2, -3, &c. je dois avouer que je n'ai pas testé sur les modules paires, car ça cassait un peu mon code et j'ai eu la flemme de le retravailler.
la suite résultante, par ordre de fréquence, a l'air de ressembler à ±2, ±3, ±5, ±7, ±6, ±11, ±10, ±13, ±17, ±14, ±19, ±15, ±23... au début, quand j'ai essayé avec environ 200 000 entiers, j'ai cru que ça ressemblait beaucoup à la suite des nombres premiers, avec quelques entiers sans facteurs carrés mis entre deux – plus précisément, je me suis dit que quand un premier exécedait un entier sans facteur carré, ce dernier serait son successeur dans la suite, mais juste un tel nombre à la fois (donc si on a deux entiers sans facteurs premiers entre deux nombres premiers, le deuxième attendra le prochain nombre premier pour le succéder). après, c'est un bon moyen mnémotechnique, et je ne cherchais pas à faire vraiment mieux de toute manière.
d'ailleurs, empiriquement, on dirait que, si on note les termes de cette suite \(\sigma_n\), alors \(\mathbb P[\mathbb Z/p^k\mathbb Z^\times=\left<\sigma_n,\cdot\right>:\forall\,m\lt n,\mathbb Z/p^k\mathbb Z^\times\ne\left<\sigma_m,\cdot\right>]\approx\displaystyle\frac6{\pi^2n^2}.\)
|
|