Throughout, we will assume that , the odd positive integer to be factored, is not a perfect square and that
. Also, we are assuming that
, such that is odd. Note that with this definition,
, so that . Also note that we have defined by this that . The recursive formulas are:
Formally, the equation we are assuming is:
Note that this equation serves as a definition of , , , and , so that these equations are true regardless of the conditions on these variables.
(a) From (4), the equation requires that .
(b) It is evident from simplifying the expression on the far right of 4 that . Therefore, we have that .
(c) For , .
For , . By the definition of floor, we then have that . If , then the continued fraction expression formed by the sequence is a rational expression equal to , which is irrational since is not a perfect square, providing a contradiction. Therefore, , so that . Therefore, , so that .
(d-e) I will prove inductively that and .
or , so by definition .
. Also, . Since , we must have , so that .
Induction: Assume and .
From (c), means . Since , we can say . From the left side of this, we have that . Now, either or .
Case 1: If , then , so that .
Case 2: If , then by (b), .
By (a), . Since , , so since also , we have that .
. Since , we must have that . Since , this implies .
(f) The fact that requires that . In order to show that is an integer, I will prove by induction that is an integer and .
and are odd by their definitions, so is even, so that . But , so the statement is true for .
Induction: Assume for some , is an integer and . Then, since , , so that since , is an integer. Also, , so that since is an integer, . Since ,
Since and , we have that and the induction is complete.
(g) Since each and thus the entire sequence that follows it is defined by the two integers and , limited by the bounds and , there is only a finite number of distinct 's. Therefore, for some and some , . QED
Proof: The second part of this equation, that follows from the definition of .
In order to show that
, I will first show that
Proof: By Lemma 1,
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 such that
Proof: Let . Then, by Lemma 2,
However, this is the same as , so the sequence of pseudo-squares will be symmetric about . Therefore, . QED
Combining periodicity with reversibility, we can make a slightly stronger statement about periodicity.
Proof: Essentially, I need to prove that in Theorem 1 (g), there is no lower bound for . Assume the contrary, that there is some lower bound . Let and as in Theorem 1 (g) such that is the smallest such positive integer and is the smallest such integer, assuming it exists. Then . But by Lemma 2 we have that , so that also meets this criteria, violating the assumption that is the smallest such integer. Therefore, . QED
Based on the symmetry about , we are able to show that there is another point of symmetry.
Case 1: If is even, . Then, by Lemmas 3 and 4, .
If , since is the only odd integer such that , so that is a shorter period than , contradicting the fact that is the smallest positive integer such that . Therefore, .
Case 2: If is odd, . Then, by Lemma 3 and 4, . 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.
Proof: I will prove by induction that if is chosen such that , then .
, so .
and is odd, so , but then .
Induction: Given and .
Choose such that . Then . Let . Choose such that . Choose such that . Since , . But since is odd, , so that . Let .
, with odd, so that
and , so .
, so since , , so
Therefore, and the induction is complete. QED
In Theorem 2, note that if and is prime, Gauss's quadratic reciprocity law states that is a quadratic residue of . Alternately, this theorem could be used as a proof of that portion of quadratic reciprocity.
Proof: Let be as in Lemma 5.
Case 1: is even, choose . . Since and , this simplifies to , but since , this provides .
But , so . If , , so that , so that . But this contradicts the fact that is even by Lemma 5 and by Lemma 4.
Therefore, . Let . Then, since and and , . Since also , is a nontrivial factor of .
Case 2: is odd. Choose . . , so that . If , this is a nontrivial factor of , and we are done. Therefore, assume that and are relatively prime, so that exists. Then we have . But then is a square root of modulo , contradicting the fact that is not a quadratic residue of . Therefore, a nontrivial factor of is found at . QED