Next: Bibliography Up: PROPOSED METHOD OF INVESTIGATION Previous: Glossary   Contents

# Proofs

Throughout, we will assume that , the odd positive integer to be factored, is not a perfect square and that . Also, we are assuming that , where or , 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:

 (4)

Note that this equation serves as a definition of , , , and , so that these equations are true regardless of the conditions on these variables.

Theorem 1   In the continued fraction expansion, each reduces to the form , with (a) , (b) , (c) , (d) , (e) , (f) is an integer. Furthermore, (g) this sequence is eventually periodic [Rie].

Proof:

(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 .

Base case:

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), .

Therefore, .

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 .

Base case:

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

Lemma 1

Proof: The second part of this equation, that follows from the definition of .

In order to show that , I will first show that

Assume the contrary, that . Then,

But and are positive, so this implies , contradicting the fact that , since must be an integer. Therefore,

From this, we find that . Therefore,

Lemma 2   If and and if we assign , then and

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

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 , so that, using this notation .

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.

Lemma 4   There exists a positive integer such that , not necessarily positive.

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.

Lemma 5   Let , where is the period from Lemma 4. If is even, , but . If is odd, .

Proof:

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.

Lemma 6   is even.

Proof: I will prove by induction that if is chosen such that , then .

Base case:

, 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 .

Therefore, , with odd, so that .

and , so .

, so since , , so

, 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.

Theorem 2   If and is not a quadratic residue of , if is as in Lemma 5, is a nontrivial factor of .

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

Next: Bibliography Up: PROPOSED METHOD OF INVESTIGATION Previous: Glossary   Contents
David Joyner 2004-02-23