2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – lhf
    Jul 15 '18 at 5:28
  • $\begingroup$ 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. $\endgroup$
    – komPLEX
    Jul 15 '18 at 9:45
  • $\begingroup$ Anyhow, thank you very much for the counter examples. That closes this case somehow... $\endgroup$
    – komPLEX
    Jul 15 '18 at 9:49
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.