Why does this continued fraction factorization magic trick work?

Question

I discovered this by accident when I first learned about continued fractions. It's hardly foolproof, but maybe half the time, you can instantly factor semiprimes if you have one in continued fraction form.

Example:

$$\sqrt{47 \cdot 97} = [67; 1, 1, 11, 1, 3, 2, 3, 2, 2, 2, 3, 2, 3, 1, 11, 1, 1, 134].$$

Then you swap the first half of the range with the second half of the range and change the leading term to be half the final term, like so, sort of turning the whole thing inside-out:

$$[1; 2, 3, 2, 3, 1, 11, 1, 1, 134, 1, 1, 11, 1, 3, 2, 3, 2, 2].$$

And then you convert it back to its radical form, and square it.

What does this give you? Well, when it works, as it does here, you get

$$\frac{97}{47},$$

a result which is especially impressive when you're dealing with giant terms. Of course, the number of terms in continued fractions makes this impractical out past $10^{40}$ or something like that.

Anyway, does anyone know why this works$-$and why it doesn't work some of the time? Sometimes the factors split nicely like this, and sometimes they remain together.

Answer 1

You can see a proof of the observed fact in the article: https://www.tandfonline.com/doi/abs/10.1080/00029890.1999.12005008

Here is another idea. For the continued fraction $[a_0,a_1,\dots,a_n]$ let $K[a_0,a_1,\dots,a_n]$ be its numerator and $K[a_1,\dots,a_n]$ its denominator, so that $[a_0,a_1,\dots,a_n]=\dfrac{K[a_0,a_1,\dots,a_n]}{K[a_1,\dots,a_n]}$.

Observe that $K[a_0,a_1,\dots,a_n]=K[a_n,\dots,a_1,a_0]$.

For any natural numbers $a_0,a_1,\dots,a_{k+1}$ it holds:

$\sqrt{[a_0,a_1,\dots,a_k]\cdot [a_0,a_1,\dots,a_k,a_{k+1}]}=[a_0,\overline{a_1,\dots,a_k,2a_{k+1},a_k,\dots,a_1,2a_0}]$

This is proved in https://arxiv.org/pdf/2005.07181.pdf.

Now, notice that:

$[a_0,\overline{a_1,\dots,a_k,2a_{k+1},a_k,\dots,a_1,2a_0}]=\sqrt{[a_0,a_1,\dots,a_k]\cdot [a_0,a_1,\dots,a_k,a_{k+1}]}=\sqrt{\dfrac{K[a_0,a_1,\dots,a_k]}{K[a_1,\dots,a_k]}\cdot\dfrac{K[a_0,a_1,\dots,a_k,a_{k+1}]}{K[a_1,\dots,a_k,a_{k+1}]}}=\sqrt{\dfrac{K[a_0,a_1,\dots,a_k]}{K[a_1,\dots,a_k,a_{k+1}]}\cdot\dfrac{K[a_0,a_1,\dots,a_k,a_{k+1}]}{K[a_1,\dots,a_k]}}.$

And also,

$[a_{k+1},\overline{a_k,\dots,a_1,2a_0,a_1,\dots,a_k,2a_{k+1}}]=\sqrt{[a_{k+1},a_k,\dots,a_1]\cdot [a_{k+1},a_k,\dots,a_1,a_0]}=\sqrt{\dfrac{K[a_{k+1},a_k,\dots,a_1]}{K[a_k,\dots,a_1]}\cdot \dfrac{K[a_{k+1},a_k,\dots,a_1,a_0]}{K[a_k,\dots,a_1,a_0]}}=\sqrt{\dfrac{K[a_1,\dots,a_k,a_{k+1}]}{K[a_0,a_1,\dots,a_k]}\cdot\dfrac{K[a_0,a_1,\dots,a_k,a_{k+1}]}{K[a_1,\dots,a_k]}}$.

This shows that when you turn around the continued fraction of $\sqrt{n}$ you get the continued fraction of $\sqrt{p/q}$ where $pq=n$. This trick will surely work whenever both the period of the continued fraction of $\sqrt{n}$ and its central term are both even.