# Method to find $r$ in the case when $r'$ returned by the continued fractions procedure is a factor of $r$

In the Quantum Computation and Quantum Information (10th ed.) textbook by Nielsen and Chuang, section 5.3.1 (titled "Application: order-finding") describes how phase estimation can be used to find the order $$r$$ of a positive integer.

After performing the inverse Fourier transform on the first register and then performing a measurement, we'll get an estimation of the phase $$\varphi\approx\frac{s}{r}$$ accurate to $$2L+1$$ bits. We hope to find $$s$$ and $$r$$ by performing the continued fractions procedure, which in certain cases returned $$s'$$ and $$r'$$ instead which happens when $$s$$ and $$r$$ share common factors.

The book describes three methods to fix this problem, two of which repeats the order-finding algorithm $$O(L)$$ times and the third requires a constant number of trials.

The third method:

The idea is to repeat the phase estimation - continued fractions procedure twice, obtaining $$r'_1$$, $$s'_1$$ the first time, and $$r'_2$$, $$s'_2$$ the second time. Provided $$s'_1$$, $$s'_2$$ have no common factors, $$r$$ may be extracted by taking the least common multiple of $$r'_1$$, $$r'_2$$

Question:

I don't understand why $$r$$ may be extracted by taking the least common multiple of $$r'_1$$, $$r'_2$$ and what is the rationale of repeating the phase estimation — continued fractions procedure twice?

## 1 Answer

Numerators and denominators of convergents of continued fractions are always co-prime. If $$s$$ and $$r$$ have a common factor, the $$r'$$ returned by the continued fractions algorithm would be a factor of $$r$$.
For example, $$r=60$$, provided the phase estimation step gives a good approximate to $$40/60$$ (i.e. $$s=40$$), you'll get $$2/3$$ as a convergent. Performing the phase estimation again might give you a good approximate to $$21/60$$ (i.e. $$s=21$$), and you'll get $$7/20$$ as a convergent. $$lcm(3,20)=60$$ will give you the correct $$r$$.
Although doing phase estimation-CF twice doesn't guarantee the correctness of resultant $$r$$ (e.g. if we got $$40/60=2/3$$ and $$28/60=7/15$$ in our two attempts, $$lcm(3,15)=15$$ does not give us the correct $$r$$), some number theoretic theorem guarantees that we succeed with probability at least $$1/4$$ (see the last remark on the last page of Prof Jozsa's Part II QI&C Notes).
(P.S. I'll update my answer with the aforementioned theorem of number theory when I find it)