Proofs

Throughout, we will assume that $N$, the odd positive integer to be factored, is not a perfect square and that $N \equiv 1\pmod 4$. Also, we are assuming that $x_0 = \frac{\sqrt{N}+P_0}{2}$, where $P_0 = \lfloor \sqrt{N} \rfloor$ or $\lfloor \sqrt{N} \rfloor - 1$, such that $P_0$ is odd. Note that with this definition, $0 < x_0 - P_0 < 1$, so that $P_0 = b_0$. Also note that we have defined by this that $Q_0 = 2$. The recursive formulas are:

$$x_{i+1} = \frac{1}{x_i-b_i}\ \ \ b_i = \lfloor x_i \rfloor,\ i \geq 0$$

Formally, the equation we are assuming is:

$$x_{i+1} = \frac{Q_i}{\sqrt{N}-P_i} = \frac{\sqrt{N}+P_i}{Q_{i+1}} = b_{i+1} + \frac{\sqrt{N}-P_{i+1}}{Q_{i+1}} ,\ i \geq 0$$ (4)

Note that this equation serves as a definition of $Q_i$, $P_i$, $Q_{i+1}$, and $P_{i+1}$, so that these equations are true regardless of the conditions on these variables.

Theorem 1   In the continued fraction expansion, each $x_i$ reduces to the form $\frac{\sqrt{N}+P_{i-1}}{Q_i}$, with (a) $N=P_i^2+Q_iQ_{i+1}$, (b) $P_i = b_iQ_i-P_{i-1}$, (c) $b_i > 0$, (d) $0<P_i<\sqrt{N}$, (e) $0<Q_i<2\sqrt{N}$, (f) $Q_i$ is an integer. Furthermore, (g) this sequence is eventually periodic [Rie].

Proof:

(a) From (4), the equation $\frac{Q_i}{\sqrt{N}-P_i} = \frac{\sqrt{N}+P_i}{Q_{i+1}}$ requires that $N=P_i^2+Q_iQ_{i+1}$.

(b) It is evident from simplifying the expression on the far right of 4 that $\frac{\sqrt{N}+P_i}{Q_{i+1}} = \frac{\sqrt{N}+b_{i+1}Q_{i+1}-P_{i+1}}{Q_{i+1}}$. Therefore, we have that $P_i = b_iQ_i-P_{i-1}$.

(c) For $i = 0$, $b_0 = P_0 > 0$.

For $i>0$, $b_{i-1} = \lfloor x_{i-1} \rfloor$. By the definition of floor, we then have that $x_{i-1} - 1 < b_{i-1} \leq x_{i-1}$. If $b_{i-1} = x_{i-1}$, then the continued fraction expression formed by the sequence $(b_i)$ is a rational expression equal to $x_0 = \frac{\sqrt{N}+P_0}{2}$, which is irrational since $N$ is not a perfect square, providing a contradiction. Therefore, $x_{i-1} - 1 < b_{i-1} < x_{i-1}$, so that $0 < x_{i-1} - b_{i-1} < 1$. Therefore, $x_i = \frac{1}{x_{i-1}-b_{i-1}} > 1$, so that $b_i = \lfloor x_i \rfloor \geq 1 > 0$.

(d-e) I will prove inductively that $0<Q_i<2\sqrt{N}$ and $0<P_{i-1}<\sqrt{N}$.

Base case: $i = 1$

$P_0 = \lfloor \sqrt{N} \rfloor$ or $\lfloor \sqrt{N} \rfloor - 1$, so by definition $0 < P_0 < \sqrt{N}$.

$Q_1 = \frac{N-P_0^2}{2} > 0$. Also, $1 = \frac{N-P_0^2}{2Q_1} = \frac{\sqrt{N}-P_0}{2} \frac{\sqrt{N}+P_0}{Q_1}$. Since $\frac{\sqrt{N}-P_0}{2} < 1$, we must have $\frac{\sqrt{N}+P_0}{Q_1} > 1$, so that $Q_1 < \sqrt{N}+P_0 < 2\sqrt{N}$.

Induction: Assume $0<Q_i<2\sqrt{N}$ and $0<P_{i-1}<\sqrt{N}$.

From (c), $0 < x_i - b_i < 1$ means $0 < \frac{\sqrt{N}-P_i}{Q_i} < 1$. Since $Q_i > 0$, we can say $0 < \sqrt{N}-P_i < Q_i$. From the left side of this, we have that $P_i < \sqrt{N}$. Now, either $Q_i \leq \sqrt{N}$ or $Q_i > \sqrt{N}$.

Case 1: If $Q_i \leq \sqrt{N}$, then $\sqrt{N}-P_i < Q_i \leq \sqrt{N}$, so that $P_i > 0$.

Case 2: If $Q_i > \sqrt{N}$, then by (b), $P_i = b_iQ_i - P_{i-1} > b_i\sqrt{N} - \sqrt{N} = (b_i-1)\sqrt{N} > 0$.

Therefore, $0<P_i<\sqrt{N}$.

By (a), $Q_{i+1} = \frac{N-P_i^2}{Q_i}$. Since $0<P_i<\sqrt{N}$, $N-P_i^2 > 0$, so since also $Q_i > 0$, we have that $Q_{i+1} > 0$.

$1 = \frac{N-P_i^2}{Q_iQ_{i+1}} = \frac{\sqrt{N}-P_i}{Q_i} \frac{\sqrt{N}+P_i}{Q_{i+1}}$. Since $\frac{\sqrt{N}-P_i}{Q_i} < 1$, we must have that $\frac{\sqrt{N}+P_i}{Q_{i+1}} > 1$. Since $Q_{i+1} > 0$, this implies $Q_{i+1} < \sqrt{N}+P_i < 2\sqrt{N}$.

(f) The fact that $N=P_i^2+Q_iQ_{i+1}$ requires that $Q_{i+1} = \frac{N-P_i^2}{Q_i}$. In order to show that $\forall i\ Q_i$ is an integer, I will prove by induction that $Q_i$ is an integer and $Q_i \mid N-P_i^2$.

Base case: $i = 0$

$N$ and $P_0$ are odd by their definitions, so $N-P_0^2$ is even, so that $2 \mid N-P_0^2$. But $Q_0 = 2$, so the statement is true for $i = 0$.

Induction: Assume for some $i$, $Q_i$ is an integer and $Q_i \mid N-P_i^2$. Then, since $N=P_i^2+Q_iQ_{i+1}$, $Q_{i+1} = \frac{N-P_i^2}{Q_i}$, so that since $Q_i \mid N-P_i^2$, $Q_{i+1}$ is an integer. Also, $Q_i = \frac{N-P_i^2}{Q_{i+1}}$, so that since $Q_i$ is an integer, $Q_{i+1} \mid N-P_i^2$. Since $P_{i+1} = b_{i+1}Q_{i+1}-P_i$,

$$N-P_{i+1}^2 = N - (b_{i+1}Q_{i+1}-P_i)^2 = N - b_{i+1}^2Q_{i+1}^2 + 2b_{i+1}Q_{i+1}P_i - P_i^2$$

$$= (N-P_i^2)-b_{i+1}^2Q_{i+1}^2+2b_{i+1}Q_{i+1}P_i$$

Since $Q_{i+1} \mid N-P_i^2$ and $Q_{i+1} \mid -b_{i+1}^2Q_{i+1}^2+2b_{i+1}Q_{i+1}P_i$, we have that $Q_{i+1} \mid N - P_{i+1}^2$ and the induction is complete.

(g) Since each $x_i$ and thus the entire sequence that follows it is defined by the two integers $Q_i$ and $P_{i-1}$, limited by the bounds $0<Q_i<2\sqrt{N}$ and $0<P_i<\sqrt{N}$, there is only a finite number of distinct $x_i$'s. Therefore, for some $m$ and some $k$, $\forall i \geq k\ x_i = x_{i+m}$. QED

Lemma 1  

$$\lfloor \frac{\sqrt{N}+P_i}{Q_i} \rfloor = \lfloor \frac{\sqrt{N}+P_{i-1}}{Q_i} \rfloor = b_i$$

Proof: The second part of this equation, that $\lfloor \frac{\sqrt{N}+P_{i-1}}{Q_i} \rfloor = b_i$ follows from the definition of $b_i$.

In order to show that $\lfloor \frac{\sqrt{N}+P_i}{Q_i} \rfloor = \lfloor \frac{\sqrt{N}+P_{i-1}}{Q_i} \rfloor$, I will first show that

$$\frac{\sqrt{N}+P_i}{Q_i}>1.$$

Assume the contrary, that $Q_i \geq \sqrt{N}+P_i$. Then,

$$b_i(\sqrt{N}+P_i) - P_i \leq b_iQ_i-P_i = P_{i-1} < \sqrt{N},$$

$$b_i\sqrt{N}+P_i(b_i-1) < \sqrt{N},$$

$$\sqrt{N}(b_i-1)+P_i(b_i-1)<0,$$

$$(b_i-1)(\sqrt{N}+P_i) <0.$$

But $\sqrt{N}$ and $P_i$ are positive, so this implies $b_i < 1$, contradicting the fact that $b_i > 0$, since $b_i$ must be an integer. Therefore,

$$Q_i < \sqrt{N}+P_i,\ \ \frac{\sqrt{N}+P_i}{Q_i}>1$$

From this, we find that $Q_{i+1} = \frac{\sqrt{N}-P_i^2}{Q_i} = \frac{(\sqrt{N}+P_i)(\sqrt{N}-P_i)}{Q_i} > \sqrt{N}-P_i$. Therefore,

$$\lfloor \frac{\sqrt{N}+P_i}{Q_i} \rfloor = \lfloor \frac{\s... ... b_i+\lfloor \frac{\sqrt{N}-P_{i-1}}{Q_i} \rfloor = b_i.\ QED$$

Lemma 2   If $x_i-b_i = \frac{\sqrt{N}-P_i}{Q_i}$ and $x_{i+1} = \frac{1}{x_i-b_i} = b_{i+1}+\frac{\sqrt{N}-P_{i+1}}{Q_{i+1}}$ and if we assign $y_0 = \frac{\sqrt{N}+P_{i+1}}{Q_{i+1}}$, then $c_0 = \lfloor y_0 \rfloor = b_{i+1}$ and $y_{1} = \frac{1}{y_0-c_0} = \frac{\sqrt{N}+P_i}{Q_i}$

Proof: By Lemma 1, $c_0 = \lfloor y_0 \rfloor = \lfloor \frac{\sqrt{N}+P_{i+1}}{Q_{i+1}} \rfloor = b_{i+1}$

$$y_1 = \frac{1}{y_0-c_0} = \frac{1}{\frac{\sqrt{N}+P_{i+1}}{... ...} = \frac{1}{\frac{\sqrt{N}+P_{i+1}-b_{i+1}Q_{i+1}}{Q_{i+1}}}$$

$$= \frac{1}{\frac{\sqrt{N}-P_i}{Q_{i+1}}} = \frac{\sqrt{N}+P_i}{\frac{N-P_i^2}{Q_{i+1}}} = \frac{\sqrt{N}+P_i}{Q_i}\ QED$$

This demonstrates an important fact about continued fractions, the fact that the direction of the sequences of pseudo-squares and residues can be reversed (i.e the indices decrease) by taking the conjugate and applying the same recursive mechanism. Thus, if the starting condition near some point is the same in both directions, the sequence will be symmetric about that point. This is the point of Lemma 3. Note that this lemma implicitly uses the fact there is only one odd integer $P_0$ such that $0 < \sqrt{N} - P_0 < 2$

Lemma 3   Let negative indices represent pseudo-squares found using the reversal of direction defined in Lemma 2. The sequence of pseudo-squares is symmetric about $Q_0 = 2$, so that, using this notation $\forall i\ Q_i = Q_{-i}$.

Proof: Let $y_{-1} = \frac{\sqrt{N}+P_1}{Q_1}$. Then, by Lemma 2, $y_0 = \frac{\sqrt{N}+P_0}{Q_0} = \frac{\sqrt{N}+P_0}{2}$

However, this is the same as $x_0$, so the sequence of pseudo-squares will be symmetric about $Q_0 = 2$. Therefore, $Q_i = Q_{-i}$. QED

Combining periodicity with reversibility, we can make a slightly stronger statement about periodicity.

Lemma 4   There exists a positive integer $m$ such that $\forall i\ x_i = x_{i+m}$, $i$ not necessarily positive.

Proof: Essentially, I need to prove that in Theorem 1 (g), there is no lower bound for $k$. Assume the contrary, that there is some lower bound $k$. Let $m$ and $k$ as in Theorem 1 (g) such that $m$ is the smallest such positive integer and $k$ is the smallest such integer, assuming it exists. Then $x_k = x_{k+m}$. But by Lemma 2 we have that $x_{k-1} = x_{k+m-1}$, so that $k-1$ also meets this criteria, violating the assumption that $k$ is the smallest such integer. Therefore, $\forall i\ x_i = x_{i+m}$. QED

Based on the symmetry about $Q_0 = 2$, we are able to show that there is another point of symmetry.

Lemma 5   Let $s = \lfloor \frac{m}{2} \rfloor$, where $m$ is the period from Lemma 4. If $m$ is even, $\forall i\ Q_{s+i} = Q_{s-i}$, but $Q_s \neq 2$. If $m$ is odd, $\forall i\ Q_{s+i+1} = Q_{s-i}$.

Proof:

Case 1: If $m$ is even, $m = 2s$. Then, by Lemmas 3 and 4, $Q_{s+i} = Q_{-s-i} = Q_{2s-s-i} = Q_{s-i}$.

If $Q_s = 2$, $x_s = \frac{\sqrt{N}+P_0}{2}$ since $P_0$ is the only odd integer such that $0 < \sqrt{N} - P_0 < 2$, so that $s$ is a shorter period than $m$, contradicting the fact that $m$ is the smallest positive integer such that $\forall i\ Q_i = Q_{i+m}$. Therefore, $Q_s \neq 2$.

Case 2: If $m$ is odd, $m = 2s+1$. Then, by Lemma 3 and 4, $Q_{s+i+1} = Q_{-s-i-1} = Q_{2s+1-s-i-1} = Q_{s-i}$. QED

The symmetry about this other point provides the mechanism for being able to find this point. Theorem 2 provides the importance of being able to find this point.

Lemma 6   $\forall i\ Q_i$ is even.

Proof: I will prove by induction that if $\alpha$ is chosen such that $2^{\alpha} \parallel Q_i$, then $2^{\alpha+1} \mid N-P_i^2$.

Base case: $i = 0$

$2^1 \parallel Q_0$, so $\alpha = 1$.

$N \equiv 1\pmod 4$ and $P_0$ is odd, so $4 \mid N-P_0^2$, but then $4 = 2^2 = 2^{\alpha+1}$.

Induction: Given $2^{\alpha} \parallel Q_i$ and $2^{\alpha+1} \mid N-P_i^2$.

Choose $r$ such that $2^{r} \parallel N-P_i^2$. Then $r > \alpha$. Let $\beta = r - \alpha$. Choose $L$ such that $N - P_i^2 = 2^{r}L$. Choose $M$ such that $Q_i = 2^{\alpha}M$. Since $Q_i \mid N-P_i^2$, $M \mid N-P_i^2$. But since $M$ is odd, $\gcd(M,2^a) = 1$, so that $M \mid L$. Let $W = \frac{L}{M}$.

Therefore, $Q_{i+1} = \frac{N-P_i^2}{Q_i} = \frac{2^rL}{2^{\alpha}M} = 2^{r-\alpha}\frac{L}{M} = 2^{\beta}W$, with $W$ odd, so that $2^\beta \parallel Q_{i+1}$.

$$N-P_{i+1}^2 = N - (b_{i+1}Q_{i+1}-P_i)^2 = N - b_{i+1}^2Q_{i+1}^2 + 2b_{i+1}Q_{i+1}P_i - P_i^2$$

$$= (N-P_i^2)-b_{i+1}^2Q_{i+1}^2+2b_{i+1}Q_{i+1}P_i$$

$2^r \mid N-P_i^2$ and $r = \alpha + \beta > \beta$, so $2^{\beta+1} \mid N - P_i^2$.

$2^{2\beta} \mid Q_i^2$, so since $\beta > 0$, $2\beta > \beta$, so $2^{\beta+1} \mid b_{i+1}^2Q_{i+1}^2$

$2^{\beta} \mid Q_i$, so $2^{\beta+1} \mid 2b_{i+1}Q_{i+1}$

Therefore, $2^{\beta+1} \mid N - P_{i+1}^2$ and the induction is complete. QED

In Theorem 2, note that if $N \equiv 1$ and $N$ is prime, Gauss's quadratic reciprocity law states that $-1$ is a quadratic residue of $N$. Alternately, this theorem could be used as a proof of that portion of quadratic reciprocity.

Theorem 2   If $N \equiv 1\pmod 4$ and $-1$ is not a quadratic residue of $N$, if $s$ is as in Lemma 5, $\gcd(Q_s,N)$ is a nontrivial factor of $N$.

Proof: Let $s$ be as in Lemma 5.

Case 1: $m$ is even, choose $i = 1$. $Q_{s+1} = Q_{s-1}$. Since $Q_{s+1} = \frac{N-P_s^2}{Q_s}$ and $Q_{s-1} = \frac{N-P_{s-1}^2}{Q_s}$, this simplifies to $P_s^2 = P_{s-1}^2$, but since $\forall i\ P_i > 0$, this provides $P_s = P_{s-1}$.

But $P_s = b_sQ_s-P_{s-1} = b_sQ_s-P_s$, so $2P_s = b_sQ_s$. If $\gcd (P_s,Q_s) = 1$, $P_s \mid b_s$, so that $b_s \geq P_s$, so that $Q_s = \frac{2P_s}{b_s} \leq 2$. But this contradicts the fact that $Q_s$ is even by Lemma 5 and $Q_s \neq 2$ by Lemma 4.

Therefore, $\gcd (P_s,Q_s) > 1$. Let $d = \gcd (P_s,Q_s)$. Then, since $N = P_i^2 + Q_iQ_{i-1}$ and $d \mid P_i$ and $d \mid Q_i$, $d \mid N$. Since also $d>1$, $d$ is a nontrivial factor of $N$.

Case 2: $m$ is odd. Choose $i = 0$. $Q_{s+1} = Q_s$. $N = P_{s+1}^2 + Q_sQ_{s+1} = P_{s+1}^2 + Q_s^2$, so that $P_{s+1}^2 \equiv -Q_s^2\pmod N$. If $\gcd (Q_s,N) > 1$, this is a nontrivial factor of $N$, and we are done. Therefore, assume that $Q_s$ and $N$ are relatively prime, so that $Q_s^{-1}\pmod N$ exists. Then we have $(Q_s^{-1})^2P_{s+1}^2 \equiv -1\pmod N$. But then $Q_s^{-1}P_{s+1}$ is a square root of $-1$ modulo $N$, contradicting the fact that $-1$ is not a quadratic residue of $N$. Therefore, a nontrivial factor of $N$ is found at $s$. QED