# Probability distribution for gcd with a fixed integer / for the order of a random element in a finite field

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.

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$$.