# Probability of success proof for Shor's algorithm

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

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

## Setup

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