| mathematical findings 
(extended) phonetic alphabet | 
miscellaneous | 
unicode
| |
which numbers to test to find a primitive root ?
december 12th, 2023finally taking time to write on there again ! so, as you may know, the only values of n for which ℤ/nℤ× may be cyclic are n = 2, 4, pk and 2pk for odd primes p and k ∈ ℕ (to be clear, yes, k can equal 0). the problem is, to find an actual generator (called a primitive root) to carry on calculations out of this, ends up being quite a tricky thing. the issue is that, we have practically nothing really solid about all that, mostly conjectures like that of artin's.
for tiny values of n, it's pretty simple to find primitive roots : $$\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.$$ but above that, it gets a bit more chaotic, and none of the latter primitive roots work anymore. so, to deal with that, i decided to code something that computes what the smallest primitive root is. just to be clear, by "smallest", i mean the member of its modulo class that is closest to 0, so it could be 2, 3, &c just like it could be -2, -3, &c. gotta admit, i only tested for odd modulos, because my code would get janky and i was a bit lazy to rework it.
the resulting sequence, sorted by frequency, seems to overall be something like ±2, ±3, ±5, ±7, ±6, ±11, ±10, ±13, ±17, ±14, ±19, ±15, ±23... at first, when i tried it with about 20k integers, i thought that looked an awful lot like the sequence of prime numbers, with some squarefree integers added in-between – namely, i thought that once a prime number would exceed a squarefree integer, the latter would show up next, but only maybe once at a time, so even though from 13 to 17 we've exceeded both 14 and 15, it'd only be followed up by 14 before jumping to the next prime, and only then would 15 appear. unfortunately, with 1 million integers, we can tell the next one is actually gonna be 22, and not 21. still, that's a nice mnemonic up to the first thirteen possibilities, and i didn't really search to strive for much better than this anyway.
also, empirically, it seems as though, if we notate that sequence as \(\sigma_n\), then \(\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}.\)
|
|