# Confusion regarding probability of period resulting in factoring

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

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%?

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