[proofplan] We exploit that $m$ is a multiple of $\phi(N)$: [Euler's theorem](/theorems/???) gives $x^m \equiv 1 \pmod N$ for $x \in (\mathbb{Z}/N\mathbb{Z})^\times$, so setting $y = x^b$ yields $y^{2^a} \equiv 1 \pmod N$ and the orders of $y$ modulo $p$ and modulo $q$ are powers of $2$ at most $2^a$. If these two orders differ (the defining condition of $X$), at the smaller one $y^{2^t}$ is $1$ modulo the smaller-order prime but not the other, so the gcd $\gcd(y^{2^t} - 1, N)$ is exactly that prime. This proves (i). For (ii) we pass to the CRT decomposition $(\mathbb{Z}/N\mathbb{Z})^\times \cong (\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$, express the order of $x^b$ in each factor using a primitive root, and count: exactly half of $(\mathbb{Z}/p\mathbb{Z})^\times$ yields the maximal $2$-power order, giving a product count of at least $\tfrac{1}{2}\phi(N)$ elements in $X$. [/proofplan] [step:Apply Euler's theorem to reduce orders to $2$-powers] For part (i), let $x \in X \subseteq (\mathbb{Z}/N\mathbb{Z})^\times$. Euler's theorem states that for every $a \in (\mathbb{Z}/N\mathbb{Z})^\times$, $a^{\phi(N)} \equiv 1 \pmod N$. Since $\phi(N) \mid m$, we have $x^m \equiv 1 \pmod N$. Writing $m = 2^a b$ and $y := x^b$, \begin{align*} y^{2^a} = x^{b \cdot 2^a} = x^m \equiv 1 \pmod{N}. \end{align*} Reducing modulo $p$ and modulo $q$ separately: $y^{2^a} \equiv 1 \pmod p$ and $y^{2^a} \equiv 1 \pmod q$. Therefore $\mathrm{ord}_p(y)$ and $\mathrm{ord}_q(y)$ each divide $2^a$, which is a power of $2$. Since every divisor of $2^a$ is itself a power of $2$, both orders are powers of $2$. [guided] Why does $y^{2^a} \equiv 1 \pmod N$ give that the orders modulo $p$ and modulo $q$ are powers of $2$? The [multiplicative order](/page/Order%20of%20an%20Element) of an element $y$ in a group $G$ is the smallest positive integer $d$ with $y^d = e$. If $y^k = e$, then $d \mid k$; this is a general fact for cyclic subgroups. Applying this in $(\mathbb{Z}/p\mathbb{Z})^\times$: $y^{2^a} \equiv 1 \pmod p$ forces $\mathrm{ord}_p(y) \mid 2^a$. The divisors of $2^a$ are exactly $\{1, 2, 4, \ldots, 2^a\}$, so $\mathrm{ord}_p(y)$ is a power of $2$, say $2^{t_p}$ with $0 \le t_p \le a$. Likewise $\mathrm{ord}_q(y) = 2^{t_q}$ with $0 \le t_q \le a$. The hypothesis $x \in X$ is exactly $t_p \ne t_q$. Without loss of generality we will take $t_p < t_q$ (swapping $p, q$ if needed). [/guided] [/step] [step:Locate the exponent $t$ that splits divisibility] Write $\mathrm{ord}_p(y) = 2^{t_p}$ and $\mathrm{ord}_q(y) = 2^{t_q}$ with $0 \le t_p, t_q \le a$. By the definition of $X$, $t_p \ne t_q$; without loss of generality (renaming $p, q$ if necessary) assume $t_p < t_q$. Set $t := t_p$, so $0 \le t < t_q \le a$, and in particular $0 \le t < a$. Then $y^{2^t} = y^{2^{t_p}} \equiv 1 \pmod p$, so $p \mid y^{2^t} - 1$. On the other hand, $2^t < 2^{t_q} = \mathrm{ord}_q(y)$, so $y^{2^t} \not\equiv 1 \pmod q$, i.e. $q \nmid y^{2^t} - 1$. Consequently \begin{align*} \gcd(y^{2^t} - 1, N) = \gcd(y^{2^t} - 1, pq) = p, \end{align*} because $p$ divides the gcd but $q$ does not, and $N = pq$ has no other prime factors. Since $y^{2^t} = (x^b)^{2^t} = x^{2^t b}$, we conclude \begin{align*} \gcd(x^{2^t b} - 1, N) = p, \end{align*} which is a non-trivial factor of $N$. This proves part (i). [guided] The crucial inequality is $t_p < t_q \le a$, which gives $t = t_p < a$ as required. At the exponent $2^t$ we are exactly at the order modulo $p$ but strictly below the order modulo $q$, so $y^{2^t} - 1$ vanishes modulo $p$ but not modulo $q$. The gcd with $N = pq$ therefore picks out $p$ and only $p$. If $t_p = t_q$ the argument fails: $y^{2^t} - 1$ would vanish modulo both primes for $t \ge t_p = t_q$ and modulo neither for $t < t_p = t_q$, so $\gcd(y^{2^t} - 1, N)$ would always equal $1$ or $N$ — never a proper factor. This is why $X$ is exactly the set where the orders differ; outside $X$ the factoring attempt fails. [/guided] [/step] [step:Decompose the counting via CRT and a primitive root modulo $p$] For part (ii), the Chinese Remainder Theorem gives the group isomorphism \begin{align*} \Phi: (\mathbb{Z}/N\mathbb{Z})^\times &\longrightarrow (\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times \\ x \bmod N &\longmapsto (x \bmod p, \, x \bmod q). \end{align*} Since $\gcd(p, q) = 1$, the CRT hypothesis is met. Under $\Phi$, $\mathrm{ord}_p(x^b)$ depends only on $x \bmod p$, and $\mathrm{ord}_q(x^b)$ depends only on $x \bmod q$. Let $g$ be a [primitive root modulo $p$](/page/Primitive%20Root), i.e. a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p - 1$. Every element of $(\mathbb{Z}/p\mathbb{Z})^\times$ has the form $g^k$ for a unique $k \in \{0, 1, \ldots, p - 2\}$. Write $p - 1 = 2^{\alpha_p} \beta_p$ with $\beta_p$ odd and $\alpha_p \ge 1$ (since $p$ is odd, $p - 1$ is even). The order of $g^b$ is $\mathrm{ord}_p(g^b) = (p - 1)/\gcd(p - 1, b)$; since $b$ is odd, $\gcd(p - 1, b) = \gcd(\beta_p, b)$, an odd divisor of $\beta_p$. Thus the $2$-part of $\mathrm{ord}_p(g^b)$ is the full $2$-part of $p - 1$, namely $2^{\alpha_p}$. [guided] Existence of a primitive root modulo a prime is [classical](/theorems/???): $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $p - 1$, so it has a generator $g$. We use $g$ to parametrise every element as $g^k$ for $k \in \mathbb{Z}/(p-1)\mathbb{Z}$. We wish to count the residues $x \bmod p$ with a specified value of $\mathrm{ord}_p(x^b)$. Since $x = g^k$ for unique $k$, we have $x^b = g^{kb}$, and the order of $g^{kb}$ in the cyclic group of order $p - 1$ is \begin{align*} \mathrm{ord}_p(g^{kb}) = \frac{p - 1}{\gcd(p - 1, kb)}. \end{align*} This is a standard formula for the order of a power in a cyclic group. The factorisation $p - 1 = 2^{\alpha_p} \beta_p$ isolates the $2$-part of $p - 1$. Since $b$ is odd, $\gcd(2^{\alpha_p}, b) = 1$, so the $2$-part of $\gcd(p-1, kb)$ equals the $2$-part of $\gcd(2^{\alpha_p}, k)$, i.e. the $2$-adic valuation of $k$ truncated at $\alpha_p$. Consequently the $2$-part of $\mathrm{ord}_p(g^{kb})$ is $2^{\alpha_p - \min(\alpha_p, v_2(k))}$, where $v_2(k)$ is the $2$-adic valuation of $k$. In particular, the $2$-part of the order is exactly $2^{\alpha_p}$ (the maximum possible) iff $v_2(k) = 0$, i.e. iff $k$ is odd. [/guided] [/step] [step:Count residues with maximal $2$-part of order modulo $p$] Let $e_p(x) := v_2(\mathrm{ord}_p(x^b))$ denote the $2$-adic valuation of the order of $x^b$ modulo $p$, so $\mathrm{ord}_p(x^b) = 2^{e_p(x)} \cdot (\text{odd})$. Using $x = g^k$, from the previous step \begin{align*} \mathrm{ord}_p(x^b) = \mathrm{ord}_p(g^{kb}) = \frac{p - 1}{\gcd(p - 1, kb)}, \end{align*} and writing $k = 2^{v} \ell$ with $\ell$ odd and $0 \le v$, \begin{align*} \gcd(p - 1, kb) = \gcd(2^{\alpha_p} \beta_p, 2^v \ell b) = 2^{\min(\alpha_p, v)} \cdot \gcd(\beta_p, \ell b). \end{align*} Hence the $2$-part of the order is $\mathrm{ord}_p(x^b)_{2\text{-part}} = 2^{\alpha_p - \min(\alpha_p, v)}$. In particular, $e_p(x) = \alpha_p$ iff $v = 0$ iff $k$ is odd. The number of odd $k$ in $\{0, 1, \ldots, p - 2\}$ is $(p-1)/2$, so exactly $(p - 1)/2$ elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ satisfy $e_p(x) = \alpha_p$, and the remaining $(p - 1)/2$ satisfy $e_p(x) < \alpha_p$. By symmetric argument, exactly $(q - 1)/2$ elements of $(\mathbb{Z}/q\mathbb{Z})^\times$ have $e_q(x) = \alpha_q$ (where $q - 1 = 2^{\alpha_q} \beta_q$ with $\beta_q$ odd, $\alpha_q \ge 1$), and the remaining $(q - 1)/2$ have $e_q(x) < \alpha_q$. [guided] We have reduced the problem to counting $k \in \mathbb{Z}/(p-1)\mathbb{Z}$ according to the $2$-adic valuation $v_2(k)$. The set of odd $k$ in $\{0, 1, \ldots, p - 2\}$ has cardinality exactly $(p - 1)/2$, since the residues alternate odd/even. The condition $e_p(x) = \alpha_p$ — the $2$-part of $\mathrm{ord}_p(x^b)$ is the maximum $2^{\alpha_p}$ — is thus satisfied by exactly half of $(\mathbb{Z}/p\mathbb{Z})^\times$. The remaining half has $e_p(x) \le \alpha_p - 1$, a strictly smaller power. The same analysis modulo $q$ yields the parallel count: $(q - 1)/2$ elements satisfy $e_q = \alpha_q$, and $(q - 1)/2$ satisfy $e_q < \alpha_q$. [/guided] [/step] [step:Combine via CRT to bound $|X|$ below by $\tfrac{1}{2}\phi(N)$] Let \begin{align*} A_p := \{u \in (\mathbb{Z}/p\mathbb{Z})^\times : e_p(u) = \alpha_p\}, \qquad B_p := \{u \in (\mathbb{Z}/p\mathbb{Z})^\times : e_p(u) < \alpha_p\}, \end{align*} and analogously $A_q, B_q$ in $(\mathbb{Z}/q\mathbb{Z})^\times$. By the previous step, $|A_p| = |B_p| = (p - 1)/2$ and $|A_q| = |B_q| = (q - 1)/2$. Under the CRT isomorphism $\Phi$, an element $x \in (\mathbb{Z}/N\mathbb{Z})^\times$ lies in $X$ iff the $2$-valuations of the orders modulo $p$ and modulo $q$ differ, i.e. iff $e_p(x) \ne e_q(x)$. The product set $A_p \times B_q \subseteq (\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$ has every element satisfying $e_p = \alpha_p$ and $e_q < \alpha_q \le a$, so $e_p \ne e_q$ except possibly when $\alpha_p = e_q$. If $\alpha_p = e_q$ then $e_q(x) = \alpha_p < \alpha_q$, consistent with $x \in B_q$, and $e_p(x) = \alpha_p = e_q(x)$ — these elements would be excluded from $X$. To avoid this case we use the more robust pair $A_p \times B_q^{(<\alpha_p)}$ where $B_q^{(<\alpha_p)} := \{u \in (\mathbb{Z}/q\mathbb{Z})^\times : e_q(u) < \alpha_p\}$. However, rather than refining the count, we proceed as follows. Observe that under $\Phi$, the set $X^c$ (the complement of $X$ in $(\mathbb{Z}/N\mathbb{Z})^\times$) consists of $x$ with $e_p(x) = e_q(x)$. Partitioning by the common value $t \in \{0, 1, \ldots, \min(\alpha_p, \alpha_q)\}$, \begin{align*} |X^c| = \sum_{t = 0}^{\min(\alpha_p, \alpha_q)} \#\{u \in (\mathbb{Z}/p\mathbb{Z})^\times : e_p(u) = t\} \cdot \#\{v \in (\mathbb{Z}/q\mathbb{Z})^\times : e_q(v) = t\}. \end{align*} For each $t$, the count $\#\{u : e_p(u) = t\}$ equals $(p - 1)/2^{\alpha_p - t + 1}$ if $0 \le t < \alpha_p$ and $(p - 1)/2$ if $t = \alpha_p$ (combining the parameterisation of the previous step: $e_p(u) = t$ iff $v_2(k) = \alpha_p - t$ for $t < \alpha_p$, giving $(p-1)/2^{\alpha_p - t + 1}$ values of $k$; and $e_p(u) = \alpha_p$ iff $v_2(k) = 0$, giving $(p - 1)/2$ values). Summing over $t$ and using $\min(\alpha_p, \alpha_q) \le \min(\alpha_p, \alpha_q)$, a direct calculation gives $|X^c| \le \tfrac{1}{2}\phi(N)$, hence $|X| \ge \tfrac{1}{2}\phi(N)$. Alternatively and more transparently: consider the involution $\tau: (\mathbb{Z}/p\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times$ given by $\tau(g^k) = g^{k + (p-1)/2}$, which flips the parity of $k$ and hence flips membership between $A_p$ and $B_p$. Extending $\tau$ to $(\mathbb{Z}/N\mathbb{Z})^\times$ via the first CRT coordinate (and identity on the second), this involution swaps $A_p \times (\mathbb{Z}/q\mathbb{Z})^\times$ and $B_p \times (\mathbb{Z}/q\mathbb{Z})^\times$, each of cardinality $\tfrac{1}{2}\phi(N)$. Inside $A_p \times (\mathbb{Z}/q\mathbb{Z})^\times$, every element has $e_p = \alpha_p$; and $e_q(x) \le \alpha_q$ with equality on $A_q$. Whenever $\alpha_p \ne \alpha_q$, every element of $A_p \times (\mathbb{Z}/q\mathbb{Z})^\times$ has $e_p = \alpha_p \ne e_q$, i.e. lies in $X$, yielding $|X| \ge (p-1)(q-1)/2 = \phi(N)/2$. When $\alpha_p = \alpha_q$, the same set contributes elements of $X$ precisely from $A_p \times B_q$ (where $e_q < \alpha_q = \alpha_p = e_p$), of size $(p-1)/2 \cdot (q-1)/2 = \phi(N)/4$, together with $B_p \times A_q$ of size $\phi(N)/4$, for a total of $\phi(N)/2$. In either case $|X| \ge \tfrac{1}{2}\phi(N)$, completing part (ii). [guided] The cleanest way to see $|X| \ge \phi(N)/2$ is by casework on whether $\alpha_p = \alpha_q$ or not. **Case 1: $\alpha_p \ne \alpha_q$.** Say $\alpha_p < \alpha_q$ (otherwise swap). The set $A_q = \{v : e_q(v) = \alpha_q\}$ has $e_q = \alpha_q > \alpha_p \ge e_p$, so every element of $(\mathbb{Z}/p\mathbb{Z})^\times \times A_q$ has $e_p \ne e_q$. This set has cardinality $(p - 1) \cdot (q - 1)/2 = \phi(N)/2$. So $|X| \ge \phi(N)/2$. **Case 2: $\alpha_p = \alpha_q$, call this common value $\alpha$.** The $2$-part of the order modulo either prime ranges in $\{0, 1, \ldots, \alpha\}$. The set $A_p \times B_q$ has $e_p = \alpha$ and $e_q < \alpha$, so $e_p \ne e_q$; its size is $(p-1)/2 \cdot (q-1)/2 = \phi(N)/4$. Symmetrically, $B_p \times A_q$ has $e_p < \alpha = e_q$, contributing another $\phi(N)/4$. These two product sets are disjoint (the first requires $e_p = \alpha$, the second $e_p < \alpha$). Their union is contained in $X$, so $|X| \ge \phi(N)/4 + \phi(N)/4 = \phi(N)/2$. In both cases $|X| \ge \phi(N)/2$. This is the bound we needed. Why is this bound important? In the Miller-Rabin primality test and in the Rabin factoring-with-oracle reduction, we need a positive-density set of "good" witnesses for the randomised algorithm to succeed with constant probability per trial. The density $|X|/|(\mathbb{Z}/N\mathbb{Z})^\times| \ge 1/2$ ensures that a uniformly random sample falls in $X$ with probability at least $1/2$, so amplification by repetition drives failure probability exponentially to $0$. [/guided] [/step] [step:Conclude both statements] Part (i) shows that every $x \in X$ produces a non-trivial factor of $N$ via the computation $\gcd(x^{2^t b} - 1, N) = p$ at the splitting exponent $t < a$. Part (ii) shows $|X| \ge \phi(N)/2$, so a uniformly random sample from $(\mathbb{Z}/N\mathbb{Z})^\times$ lands in $X$ with probability at least $1/2$. Together these give an expected-polynomial-time Las Vegas factoring algorithm given any multiple $m$ of $\phi(N)$. [/step]