I care about a rough estimation for the number of elements of a certain order in $(\mathbb{Z}/\mathbb{Z}_n)^*$. Let us take one of the rather simple cases, where $n=p_1 p_2$ with two different odd primes $p_1$, $p_2$.
What can you tell now about the number of elements in $(\mathbb{Z}/\mathbb{Z}_n)^*$ with order $k$ divisible by $(p_1-1)$ (the order of one of the corresponding group of units: $(\mathbb{Z}/\mathbb{Z}_{p_1})^*$)?
I know, in general there is no simple solution to this but I'd be fine if I could say that it is larger than $\frac 12 |(\mathbb{Z}/\mathbb{Z}_n)^*|$ (that is $\frac 12 \varphi(n)=(p_1-1)(p_2-1)/2$). I've calculated some examples that indicate that this is true, but I cannot tell for sure. So far the things you can say are (with $\text{ord}(a)\mod n$ the order of $a$ in $(\mathbb{Z}/\mathbb{Z}_n)^*$)
- $\quad\text{ord}(a)\mod n =\text{lcm}(\text{ord}(a) \mod p_1,\ \text{ord}(a) \mod p_2)$
- $\quad$largest occuring order of an element in $(\mathbb{Z}/\mathbb{Z}_n)^*$ is $(p_1-1)(p_2-1)/2$
- $\quad$there are elements in $(\mathbb{Z}/\mathbb{Z}_n)^*$ of order $(p_1-1)$
- $\quad$in $(\mathbb{Z}/\mathbb{Z}_{p_1})^*$, for all divisors $d$ of $\varphi(p_1)=(p_1-1)$, there are $\varphi(d)$ many elements of order $d$
Apart from that the occurence of elements of order $k=\lambda(p_1-1)$ (some multiple of $(p_1-1)$ different from the mentioned) is not mandatory.
So far I am stuck on this and would be glad for any help.
(of course you could interchange the roles of $p_1$ and $p_2$)
edit
There appeared an answer that is gone now, I guess it was deleted by the writer(?). It suggested the desired number is exactly $(p_2-1)$. I want to give a little (counter) example, that fits my assumption above. Take $(\mathbb{Z}/\mathbb{Z}_{35})^*(=(\mathbb{Z}/\mathbb{Z}_{5})^*\times (\mathbb{Z}/\mathbb{Z}_{7})^*)$. The elements of order divisible by 4 are
${2, 3, 8, 12, 13, 17, 18, 22, 23, 27, 32, 33 }\in (\mathbb{Z}/\mathbb{Z}_{35})^*$
That are 12 elements, exactly half of $|(\mathbb{Z}/\mathbb{Z}_{35})^*|$. (the other way around there would be 14 elements with order divisible by 6)
A word about my motivation. In QUANTUM ALGORITHMS VIA LINEAR ALGEBRA
– A Primer (Lipton, Regan) there is a chapter about Shors famous factoring algorithm, with a slightly different analysis part. Anyway, the authors seem to state the assumption from above as given in the factoring chapter with no explanation (any element with order divisible by $(p_1-1)$ can lead to a factor, and because there are at least half as many as the group order you have success probability of at least $\frac 12$ by picking random elements). I want to use the same assumption in a different context but want to have "kind of a proof"…
Best Answer
For $n=13\cdot 19$, the number you're interested in is less than half the total when $p_1=13$.
For $n=29\cdot 31$, the number you're interested in is less than half the total no matter which prime you choose for $p_1$.