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

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)

You need that $$\gcd(s_1,s_2)=1$$. It's nos enough that $$\gcd(s_1',s_2')=1$$. Nan uses this in his example.

Lemma : $$\gcd(a,mn)=1$$ if and only if $$\gcd(a,m)=1$$ and $$\gcd(a,n)=1$$

Suppose that $$\gcd(s_1,s_2)=1$$,

$$\frac{s_1'}{r_1'}=\frac{s_1'a}{r_1'a}=\frac{s_1}{r}\quad\&\quad\frac{s_2'}{r_2'}=\frac{s_2'b}{r_2'b}=\frac{s_2}{r}$$ with $$\gcd(r_1',s_1')=\gcd(s_2',r_2')=1$$.

$$\gcd(s_1,s_2)=1\implies \gcd(s_1'a,s_2'b)=1$$

Lemma implies, $$\gcd(a,b)=1$$

$$r=r_1'a=r_2'b\implies a|r_2'b,b|r_1'a\;\&\; \gcd(a,b)=1\implies a,b\text{ have no common factors}\\ \implies a|r_2'\quad\&\quad b|r_1'$$

So $$r_1'=bc$$ and $$r_2'=ad$$ for some integers c,d.

Then $$abc = r = abd$$ and thus, $$c = d$$.

Hence $$\gcd(r_1',r_2')=c$$.

Finally, $$r = abc=\frac{abcc}{c}=\frac{r_1'r_2'}{\gcd(r_1',r_2')}=lcm(r_1',r_2').$$