# Number of elements with order divisible by certain cyclic subgroups order in $(\mathbb{Z}/\mathbb{Z}_n)^*$

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

• 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$.
– lhf
Jul 15 '18 at 5:28
• Oops. Well that is a little surprise. I have tested quite some example (bigger ones with n ~ 20 bits). The little one from above was the first small example to show what i mean. What a trap. Jul 15 '18 at 9:45
• Anyhow, thank you very much for the counter examples. That closes this case somehow... Jul 15 '18 at 9:49

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