In the book "Quantum Computation and Information" by Nielsen and Chuang, Shor's algorithm is presented with a related probability of success theorem and proof found on page 634, Theorem A4.13. In the last paragraph of this proof, the authors write that:

It is easy to see that $r_j | r$ for each j, and therefore $r_j$ is odd, so $d_j = 0$ for all $i = 1,...,k$.

I understand why the last portion of the statement is true, but I do not understand how we see that $r_j | r$.


1 Answer 1


TL;DR This is a consequence of the Chinese Remainder theorem and the fact that in any group if $g^k$ is the identity then the order of $g$ divides $k$.


We are factoring an odd composite positive integer $N=p_1^{\alpha_1}\dots p_m^{\alpha_m}$ where $p_i$ are distinct primes and $\alpha_i$ are positive integers. We choose $x\in\mathbb{Z}_N^*$ uniformly at random. By the Chinese Remainder theorem this choice corresponds to the choice of $m$ numbers $x_j\in\mathbb{Z}_{p_m^{\alpha_m}}^*$ such that $x=x_j\pmod{p_j^{\alpha_j}}$ for every $j=1,\dots,m$. Let $r$ be the order of $x$ and $r_j$ the order of $x_j$.

Proof that $r_j|r$

By the Chinese Remainder theorem, the map from $\mathbb{Z}_N$ to $\mathbb{Z}_{p_1^{\alpha_1}}\times\dots\times\mathbb{Z}_{p_m^{\alpha_m}}$ defined by

$$ x \mapsto(x_1,\dots,x_m) $$

is a ring isomorphism. Therefore, $x^r=1\pmod N$ implies $x_j^r=1\pmod{p_j^{\alpha_j}}$ for every $j$. Now, by group theory, for any $y\in\mathbb{Z}_{p_j^{\alpha_j}}^*$ if $y^k= 1 \pmod{p_j^{\alpha_j}}$ then the order of $y$ divides $k$. Setting $y:=x_j$, we see that the order of $x_j$ divides $r$.$\square$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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