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

Question

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?

Answer 1

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)

Answer 2

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