初等数论 Chapter 7
Definition Continued Fraction
An approximation for irrational numbers or an representation of rational numbers
\[ \langle x_0,x_1,x_2,x_3,....x_n \rangle = \frac{1}{x_0+\frac{1}{x_1+...}}\]
Propertys
Define \[\frac{P_n}{Q_n} = \langle x_0,x_1,x_2,....x_n \rangle\]
Then
1.1
\[P_nQ_{n-1} - P_{n-1}Q_n = (-1)^{n+1}\]
1.2
\[P_nQ_{n-2} - P_{n-2}Q_n = (-1)^n x_n\]
1.3
\[\langle x_0,x_1,x_2,....x_n \rangle-\langle x_0,x_1,x_2,....x_{n-1} \rangle = \frac{(-1)^{n+1}}{Q_n Q_{n-1}}\]
1.4
\[\langle x_0,x_1,x_2,....x_n \rangle-\langle x_0,x_1,x_2,....x_{n-2} \rangle = \frac{(-1)^{n}x_n}{Q_n Q_{n-2}}\]
1.5
\[P_n = x_n P_{n-1} + P_{n-2}\]
1.6
\[Q_n = x_n Q_{n-1} + Q_{n-2}\]
Pell's Function
Try use the knowledge from continued fraction to prove this! （Which seams utterly impossible)
\[ x^2 - Dy^2 = \plusmn 1\]
General Solution \[x_n+y_n\sqrt D = (x_0+y_0\sqrt D)^n\]
Matrix Form \[\begin{pmatrix}x_n \\ y_n \end{pmatrix} = \begin{pmatrix}x_0 & Dy_0 \\ y_0 & x_0 \end{pmatrix}\begin{pmatrix}x_0 \\ y_0 \end{pmatrix}\]
Why? Assume $ x_1^2 - Dy_1^2 = 1$ and $ x_2^2 - Dy_2^2 = $, then $(x_1^2 - Dy_12)(x_22 - Dy_2^2) = (x_1x_2+Dy_1y_2)^2 - D(x_1y_2 -y_1x_2)^2 =1 $. So another solution can be formed by multiplying them together! Rearrange to obtain the above form.