Confusion regarding probability of period resulting in factoring

Question

^{This is a sequel to How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from "if all these powers of $2$ agree"?}

---

From Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) (arXiv), p. 16:

The multiplicative group (mod $p^\alpha$) for any odd prime power $p^\alpha$ is cyclic [Knuth 1981], so for any odd prime power $p_i^{a_i}$, the probability is at most 1/2 of choosing an $x_i$ having any particular power of two as the largest divisor of its order $r_i$. Thus each of these powers of 2 has at most a 50% probability of agreeing with the previous ones, so all k of them agree with probability at most $1/2^{k−1}$, and there is at least a $1 - 1/2^{k-1}$ chance that the $x$ we choose is good. This scheme will thus work as long as $n$ is odd and not a prime power; finding factors of prime powers can be done efficiently with classical methods.

1. Why is the probability of choosing an $x_i$ having any particular power of two as the largest divisor of its order $r_i$ at most $\frac{1}{2}$?

2. Why is the probability of each of these powers of 2 agreeing with the previous at most 50%?

---

Related: Expected repetitions of the quantum part of Shor's algorithm

Answer 1

1. Let $m = p_{i}^{a_i-1}(p_i-1)$ – the order of our multiplicative group. Cyclic group means there is a primitive element $a$ with the order equals to the size of the group, that is $m$. Moreover, the cyclic group consists of the elements $a^1, a^2, ... , a^m=1$. The order of the element $a^k$ is exactly $m/\text{gcd}(m, k)$. If $m/\text{gcd}(m, k)$ has a particular power of $2$ as its largest divisor, then $k$ has corresponding particular power of $2$. All numbers $k$, i.e. numbers from $1$ to $m$, are split into sets by this power value. And the largest set can't have more than $m/2$ elements, because there is a set with all odd numbers $k$, with a size of $m/2$.

2. Because the probability of observing two same results in two experiments is $$P_1 \cdot P_1 + P_2\cdot P_2 + ... + P_j\cdot P_j,$$ where $(P_1,...,P_j)$ – is the probability distribution for events. Since every $P_i \leq 1/2$ and $P_1+..+P_j = 1$, that total expression is also $ \leq 1/2 $ (observe that $P_i\cdot P_i \leq P_i/2$).