0
$\begingroup$

Are there some known results for the following related questions:

  1. Fix an integer $N$. What is the probability distribution of the random variable $G = \gcd(k, N)$, where $k$ is uniform in $\{0,…,N-1\}$?

  2. Fix a prime power $q$. What is the probability distribution of the order of a uniform nonzero element $x\in𝔽_q$?

The relationship between the two is easily seen once you consider a generator $ω$ of $𝔽_q^×$. Sampling a uniform element $x\in𝔽_q^×$ is equivalent as sampling a random integer $k\in\{0,…,q-1\}$ and taking $x = ω^k$. Then the order of $x$ is $(q-1)/\gcd(k,q-1)$ so both probability distributions are closely related.

Of course, describing exactly the distribution(s) is hard, and depends (a lot) on the prime factorization of $N$, resp. $q-1$. I am looking for results giving lower and/or upper bounds on

  • the expected value of $\gcd(k,N)$, resp. the order of $x$,
  • the probability that $\gcd(k,N) ≥ εN$ for some $ε$, resp. the order of $x$ is $≤εN$,
  • the probability that $\gcd(k,N) ≤ εN$ for some $ε$, resp. the order of $x$ is $≥εN$,

or any other result giving some insight on these distributions. I am interested in some of worst-case results, that is that apply to every value $N$, resp. $q$, rather than, say, probabilistic results when $N$ is random.

$\endgroup$

1 Answer 1

1
$\begingroup$

A partial answer is given in the following paper:

Joachim von zur Gathen; Arnold Knopfmacher; Florian Luca; Lutz G. Lucht; Igor E. Shparlinski. Average order in cyclic groups. Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 107-123. doi : 10.5802/jtnb.436. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/

They prove in particular that the expected (additive) order of a uniform element $a\in ℤ/Nℤ$ is between $φ(N)$ and $A⋅φ(N)$ where $φ(⋅)$ is Euler's totient function and $A = ζ(2)ζ(3)/ζ(6) \simeq 1.9435964368$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .