math.wiki
Number theory › Quadratic residues and beyond › Pell's equation and continued fractions
Sign in

Pell's equation and continued fractions

For a positive integer d that is not a perfect square, which points with integer coordinates lie on the hyperbola x squared minus d y squared equals 1, and how can they be found when the smallest one has ten digits?

Where you are 5 in Quadratic residues and beyond

Why this exists

Let d be a positive integer that is not a perfect square. Pell’s equation asks for integers x and y with

x^2 - dy^2 = 1.

The pair (1, 0) always works. For d = 2 a short search finds (3, 2). For d = 61 the smallest solution in positive integers is

x = 1{,}766{,}319{,}049, \qquad y = 226{,}153{,}980.

Fermat set this very case as a challenge in 1657.

A solution says (x/y)^2 = d + 1/y^2, so x/y is a fraction extraordinarily close to \displaystyle \sqrt{d}. The machine that produces such fractions is the continued fraction of \displaystyle \sqrt{d}, and it delivers the solutions directly. The name is a slip: Euler attached Pell’s name to the equation, apparently by mistake. Brahmagupta, in the seventh century, already combined solutions to make new ones, and Lagrange proved in the 1760s that a solution other than (1, 0) always exists.

Definition

A finite continued fraction is an expression

[a_0; a_1, \dots, a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}

with a_0 an integer and a_1, \dots, a_n positive integers, the partial quotients. The bracket [a_0; a_1, \dots, a_{k-1}, t] with a positive real t last means the same nested expression.

The continued fraction expansion of a real number \alpha sets \alpha_0 = \alpha and, for k = 0, 1, 2, \dots,

a_k = \lfloor \alpha_k \rfloor, \qquad \alpha_{k+1} = \frac{1}{\alpha_k - a_k},

stopping when some \alpha_k is an integer. Each \alpha_{k+1} exceeds 1, so a_k \ge 1 for k \ge 1, and since \alpha_k = a_k + 1/\alpha_{k+1}, unwinding gives \alpha = [a_0; a_1, \dots, a_k, \alpha_{k+1}] for every k the process reaches.

The convergents p_k / q_k are built from the partial quotients by

p_{-2} = 0, \quad p_{-1} = 1, \quad p_k = a_k p_{k-1} + p_{k-2},
q_{-2} = 1, \quad q_{-1} = 0, \quad q_k = a_k q_{k-1} + q_{k-2}.

For an infinite sequence, [a_0; a_1, a_2, \dots] means \lim p_k/q_k, which exists by Theorem 3. A bar marks a block that repeats forever, as in [a_0; \overline{a_1, \dots, a_r}].

A positive solution of Pell’s equation has x, y \ge 1. The fundamental solution (x_1, y_1) is the positive solution with the smallest x. Since y^2 = (x^2 - 1)/d grows with x, it also has the smallest y and the smallest \displaystyle x_1 + y_1\sqrt{d}.

Intuition

For a rational number the expansion is the The Euclidean algorithm and coprime numbers in disguise. For an irrational number it never stops, and the convergents close in on \alpha from alternate sides, with error below 1/q_k^2.

The hyperbola x^2 - 3y^2 = 1 in Figure 1 runs ever closer to the line \displaystyle x = \sqrt{3}\,y, so its integer points are fractions x/y almost equal to \displaystyle \sqrt{3}. The convergents of \displaystyle \sqrt{3} = [1; \overline{1, 2}] are \tfrac11, \tfrac21, \tfrac53, \tfrac74, \tfrac{19}{11}, \tfrac{26}{15}, and so on, and every second one, (2, 1), (7, 4), (26, 15), is a solution.

2 4 6 8 1 2 3 4 x y (1, 0) (2, 1) (7, 4)
x^2 - 3y^2 = 1
\displaystyle x = \sqrt{3}\,y
Figure 1The integer points on x^2 - 3y^2 = 1 hug the line \displaystyle x = \sqrt{3}\,y, so their ratios x/y are very close to \displaystyle \sqrt{3}.

Results

Theorem 1 (rational numbers). The expansion of \alpha stops if and only if \alpha is rational. For \alpha = a/b with b \ge 1, the partial quotients are the successive quotients of the Euclidean algorithm on a and b.

Theorem 2 (convergents). Let a_0 be an integer and a_1, a_2, \dots positive integers. For k \ge 0 and every real t > 0,

[a_0; a_1, \dots, a_{k-1}, t] = \frac{t\,p_{k-1} + p_{k-2}}{t\,q_{k-1} + q_{k-2}},

so p_k/q_k = [a_0; a_1, \dots, a_k]. Also p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1} for k \ge -1, so \gcd(p_k, q_k) = 1, and 1 = q_0 \le q_1 < q_2 < \cdots.

Theorem 3 (convergence). If \alpha is irrational, then for every k \ge 0

\alpha - \frac{p_k}{q_k} = \frac{(-1)^k}{q_k(\alpha_{k+1} q_k + q_{k-1})},

so |\alpha - p_k/q_k| < 1/(q_k q_{k+1}) and p_k/q_k \to \alpha, from below for even k and from above for odd k. Every infinite continued fraction converges.

Theorem 4 (the expansion of \displaystyle \sqrt{d}). Let d \ge 2 be a non-square, \displaystyle a_0 = \lfloor \sqrt{d} \rfloor, P_0 = 0, Q_0 = 1, and

P_{k+1} = a_k Q_k - P_k, \qquad Q_{k+1} = \frac{d - P_{k+1}^2}{Q_k}.

Then every P_k and Q_k is an integer, Q_k \ne 0, \displaystyle \alpha_k = (P_k + \sqrt{d})/Q_k, and for every k \ge 0

p_k^2 - d\,q_k^2 = (-1)^{k+1} Q_{k+1}.

Theorem 5 (periodicity; stated without proof). In Theorem 4, every Q_k > 0, and \displaystyle \sqrt{d} = [a_0; \overline{a_1, \dots, a_r}] with a_r = 2a_0. With r the least such period, Q_k = 1 exactly when r \mid k. Since Q_k > 0, a_k = \lfloor (P_k + a_0)/Q_k \rfloor, so the expansion runs in integers. Periodicity is Lagrange’s theorem on quadratic irrationals (Stein, Elementary Number Theory, Section 5.5); the finer facts for \displaystyle \sqrt{d} are proved in the continued fractions chapter of Niven, Zuckerman and Montgomery.

Theorem 6 (Legendre’s criterion; stated without proof, proved in the same chapter). If \alpha is irrational, p, q are integers with q \ge 1, and |\alpha - p/q| < 1/(2q^2), then p/q is a convergent of \alpha.

Theorem 7 (Pell’s equation from the expansion). Let r be the period of \displaystyle \sqrt{d}. The positive solutions of x^2 - dy^2 = \pm 1 are exactly the pairs (p_k, q_k) with r \mid k + 1, and the sign is (-1)^{k+1}: the +1 equation takes those with k + 1 even, the -1 equation those with k + 1 odd. When r is even every multiple of r is even, so the -1 equation is solvable exactly when r is odd. The fundamental solution is (p_{r-1}, q_{r-1}) if r is even and (p_{2r-1}, q_{2r-1}) if r is odd. In particular a solution other than (\pm 1, 0) always exists.

Theorem 8 (all solutions). Let (x_1, y_1) be the fundamental solution and \displaystyle \varepsilon = x_1 + y_1\sqrt{d}. The positive solutions are exactly the pairs (x_n, y_n), n \ge 1, with \displaystyle x_n + y_n\sqrt{d} = \varepsilon^n. They are all different, so there are infinitely many, and

x_{n+1} = x_1 x_n + d\,y_1 y_n, \qquad y_{n+1} = x_1 y_n + y_1 x_n.

Every integer solution is (\pm 1, 0) or (\pm x_n, \pm y_n).

Why it is true

Comparing parts. \displaystyle \sqrt{d} is irrational: if \displaystyle \sqrt{d} = a/b, then a^2 = db^2, so every prime p has v_p(d) = 2v_p(a) - 2v_p(b), which is even, and by Every number has exactly one prime factorization d is a square (Irrational numbers does d = 2). So if \displaystyle a + b\sqrt{d} = c + e\sqrt{d} with integers, then b = e (otherwise \displaystyle \sqrt{d} = (a - c)/(e - b)), and a = c.

Theorem 1. Write a = a_0 b + r_0 with 0 \le r_0 < b (The division algorithm). Then a_0 = \lfloor a/b \rfloor, and if r_0 \ne 0, \alpha_1 = b/r_0: the step replaces (a, b) by (b, r_0), exactly as Euclid does, and the remainders strictly decrease, so the process stops. Conversely, if \alpha_k is rational, so is \alpha_{k-1} = a_{k-1} + 1/\alpha_k, and so on back to \alpha. An irrational \alpha therefore has no integer \alpha_k.

Theorem 2. Induction on k. At k = 0 the left side is t and the right side is (t \cdot 1 + 0)/(t \cdot 0 + 1) = t, for every real t. If the formula holds at k, then [a_0; \dots, a_k, t] = [a_0; \dots, a_{k-1}, a_k + 1/t], which by the formula at k is

\begin{aligned} \frac{(a_k + 1/t)p_{k-1} + p_{k-2}}{(a_k + 1/t)q_{k-1} + q_{k-2}} &= \frac{p_k + p_{k-1}/t}{q_k + q_{k-1}/t} \\ &= \frac{t\,p_k + p_{k-1}}{t\,q_k + q_{k-1}}. \end{aligned}

Putting t = a_k gives p_k/q_k. For the determinant, p_{-1}q_{-2} - p_{-2}q_{-1} = 1, and the recurrences give p_k q_{k-1} - p_{k-1} q_k = -(p_{k-1} q_{k-2} - p_{k-2} q_{k-1}). A common divisor of p_k and q_k divides \pm 1. Finally q_0 = 1, q_1 = a_1, and q_k = a_k q_{k-1} + q_{k-2} > q_{k-1} for k \ge 2.

Theorem 3. Theorem 2 with t = \alpha_{k+1} gives

\alpha = \frac{\alpha_{k+1} p_k + p_{k-1}}{\alpha_{k+1} q_k + q_{k-1}}.

Subtracting p_k/q_k leaves the numerator p_{k-1} q_k - p_k q_{k-1} = (-1)^k. The denominator is positive, which gives the sides, and since the irrational \alpha_{k+1} exceeds a_{k+1}, it exceeds q_k(a_{k+1} q_k + q_{k-1}) = q_k q_{k+1}; and q_k \to \infty. For any infinite sequence of partial quotients, the determinant identity gives p_k/q_k = a_0 + \sum_{j=1}^{k} (-1)^{j-1}/(q_j q_{j-1}), an alternating series whose terms decrease to 0, so it converges.

Theorem 4. Induction, carrying also Q_k \mid d - P_k^2; all holds at k = 0. Given it at k, \displaystyle \alpha_k - a_k = (\sqrt{d} - P_{k+1})/Q_k, so

\alpha_{k+1} = \frac{Q_k(\sqrt{d} + P_{k+1})}{d - P_{k+1}^2} = \frac{P_{k+1} + \sqrt{d}}{Q_{k+1}}.

Since P_{k+1} \equiv -P_k \pmod{Q_k}, d - P_{k+1}^2 \equiv d - P_k^2 \equiv 0 \pmod{Q_k}, so Q_{k+1} is an integer, nonzero because d is not a square, and Q_k Q_{k+1} = d - P_{k+1}^2 carries the divisibility forward. For the identity, write P = P_{k+1}, Q = Q_{k+1}, put t = \alpha_{k+1} in Theorem 2 with \displaystyle \alpha = \sqrt{d}, clear denominators and multiply by Q:

d\,q_k + (P q_k + Q q_{k-1})\sqrt{d} = (P p_k + Q p_{k-1}) + p_k \sqrt{d}.

Comparing parts, d\,q_k = P p_k + Q p_{k-1} and p_k = P q_k + Q q_{k-1}. Multiply the second by p_k, the first by q_k, and subtract: p_k^2 - d q_k^2 = Q(p_k q_{k-1} - p_{k-1} q_k) = (-1)^{k-1} Q_{k+1}.

Theorem 7. Let (x, y) be a positive solution of x^2 - dy^2 = \pm 1. Then x \ge y (for -1, x^2 = dy^2 - 1 \ge 2y^2 - 1 \ge y^2), so \displaystyle x + y\sqrt{d} > 2y and

\left|\sqrt{d} - \frac{x}{y}\right| = \frac{1}{y(x + y\sqrt{d})} < \frac{1}{2y^2}.

By Theorem 6, x/y = p_k/q_k for some k; both are in lowest terms (a common divisor of x and y divides \pm 1), so x = p_k, y = q_k. Theorem 4 now says \pm 1 = (-1)^{k+1} Q_{k+1} with Q_{k+1} > 0, so Q_{k+1} = 1, meaning r \mid k + 1, and the sign is (-1)^{k+1}. Conversely, if r \mid k + 1 then Q_{k+1} = 1 and (p_k, q_k) solves the equation with sign (-1)^{k+1}. A multiple of r can be odd only when r is odd, and then r itself is one. As p_0 < p_1 < \cdots, the smallest admissible k gives the fundamental solution.

Theorem 8. Write \displaystyle N(a + b\sqrt{d}) = a^2 - db^2 = (a + b\sqrt{d})(a - b\sqrt{d}). The conjugate of a product is the product of the conjugates (multiply out), so N(uv) = N(u)N(v): products of solutions are solutions, and \displaystyle \varepsilon^{-1} = x_1 - y_1\sqrt{d} has norm 1.

Lemma. If s^2 - dt^2 = 1 and \displaystyle u = s + t\sqrt{d} > 1, then s, t \ge 1. Indeed \displaystyle s - t\sqrt{d} = 1/u \in (0, 1), so s = (u + 1/u)/2 > 0 and \displaystyle t\sqrt{d} = (u - 1/u)/2 > 0.

Each \varepsilon^n (n \ge 1) is some \displaystyle x_n + y_n\sqrt{d} of norm 1 and exceeds 1, so by the lemma it is a positive solution; the powers strictly increase, so the pairs differ. Conversely, for a positive solution let \displaystyle u = x + y\sqrt{d} \ge \varepsilon, and choose n \ge 1 with \varepsilon^n \le u < \varepsilon^{n+1}. Then v = u\,\varepsilon^{-n} has integer parts, norm 1, and 1 \le v < \varepsilon. If v > 1, the lemma makes it a positive solution smaller than \varepsilon, which is impossible; so u = \varepsilon^n. The recurrence is \varepsilon^{n+1} = \varepsilon^n \varepsilon multiplied out. A solution with y = 0 has x = \pm 1; any other gives the positive solution (|x|, |y|).

Worked examples

Example 1

A rational number and its convergents

Expand 225/157, list its convergents, and find integers x and y with 225x + 157y = 1.

Solution

Run the Euclidean algorithm:

\begin{aligned} 225 &= 1 \cdot 157 + 68 \\ 157 &= 2 \cdot 68 + 21 \\ 68 &= 3 \cdot 21 + 5 \\ 21 &= 4 \cdot 5 + 1 \\ 5 &= 5 \cdot 1 \end{aligned}

By Theorem 1 the quotients are the partial quotients: 225/157 = [1; 2, 3, 4, 5]. The recurrences give

k-2-101234
a_k12345
p_k01131043225
q_k1012730157

The determinant identity at k = 4 reads 225 \cdot 30 - 43 \cdot 157 = 6750 - 6751 = -1, that is, 225 \cdot (-30) + 157 \cdot 43 = 1. So x = -30, y = 43, and every solution is x = -30 + 157t, y = 43 - 225t (Bezout's identity and the extended Euclidean algorithm).

Example 2

The expansion of the square root of 22

Expand \displaystyle \sqrt{22} and find the fundamental solution of x^2 - 22y^2 = 1.

Solution

Here a_0 = 4, since 16 < 22 < 25. Run Theorem 4 with a_k = \lfloor (P_k + 4)/Q_k \rfloor. For instance P_1 = 4 \cdot 1 - 0 = 4, Q_1 = (22 - 16)/1 = 6, a_1 = \lfloor 8/6 \rfloor = 1.

k0123456
P_k0424424
Q_k1632361
a_k4124218
p_k451461136197
q_k113132942

At k = 6, Q_6 = 1 and P_6 = 4, so \displaystyle \alpha_6 = 4 + \sqrt{22} and \displaystyle \alpha_7 = 1/(\sqrt{22} - 4) = \alpha_1: everything repeats, and \displaystyle \sqrt{22} = [4; \overline{1, 2, 4, 2, 1, 8}] with r = 6 and a_6 = 2a_0.

The values p_k^2 - 22q_k^2 for k = 0, \dots, 5 are -6, 3, -2, 3, -6, 1, which is (-1)^{k+1}Q_{k+1} as Theorem 4 says. The period is even, so by Theorem 7 the fundamental solution is (p_5, q_5) = (197, 42): 197^2 = 38{,}809 = 22 \cdot 1764 + 1, and x^2 - 22y^2 = -1 has no solution.

Example 3

An odd period: the square root of 29

Expand \displaystyle \sqrt{29}, solve x^2 - 29y^2 = -1, and find the fundamental solution of x^2 - 29y^2 = 1.

Solution

With a_0 = 5:

k012345
P_k053235
Q_k145541
a_k5211210
p_k511162770727
q_k123513135

So \displaystyle \sqrt{29} = [5; \overline{2, 1, 1, 2, 10}] with r = 5, odd. Theorem 7 gives the -1 solution (p_4, q_4) = (70, 13): 4900 - 29 \cdot 169 = -1.

The fundamental solution of the +1 equation is (p_9, q_9). Continuing with the second period 10, 2, 1, 1, 2, the numerators run 727, 1524, 2251, 3775, 9801 and the denominators 135, 283, 418, 701, 1820. So (x_1, y_1) = (9801, 1820), and indeed 9801^2 - 29 \cdot 1820^2 = 96{,}059{,}601 - 96{,}059{,}600 = 1.

Example 4

A family with period one

Prove that for every positive integer m, \displaystyle \sqrt{m^2 + 1} = [m; \overline{2m}], that (m, 1) solves x^2 - (m^2 + 1)y^2 = -1, and that the fundamental solution of x^2 - (m^2 + 1)y^2 = 1 is (2m^2 + 1, 2m).

Solution

Let \displaystyle \alpha_0 = \sqrt{m^2 + 1}. From m^2 < m^2 + 1 < (m + 1)^2, a_0 = m. Then

\alpha_1 = \frac{1}{\alpha_0 - m} = \frac{\alpha_0 + m}{(m^2 + 1) - m^2} = \alpha_0 + m,

which lies between 2m and 2m + 1, so a_1 = 2m and \alpha_2 = 1/(\alpha_1 - 2m) = 1/(\alpha_0 - m) = \alpha_1. So \displaystyle \sqrt{m^2 + 1} = [m; \overline{2m}] with period r = 1, odd. By Theorem 7, (p_0, q_0) = (m, 1) solves the -1 equation, and the fundamental solution is (p_1, q_1) = (a_1 a_0 + 1, a_1) = (2m^2 + 1, 2m). Check: (2m^2 + 1)^2 - 4m^2(m^2 + 1) = 1.

For m = 6 this is \displaystyle \sqrt{37} = [6; \overline{12}] with (73, 12).

Example 5

Every square triangular number

Triangular numbers shows that T_n = n(n+1)/2 equals s^2 exactly when (2n + 1)^2 - 8s^2 = 1, finds 1, 36, 1225, 41{,}616, and states without proof that the list never ends. Prove that it never ends, and find the next one after 41{,}616.

Solution

For d = 8: a_0 = 2, P_1 = 2, Q_1 = 4, a_1 = 1, P_2 = 2, Q_2 = 1, a_2 = 4, so \displaystyle \sqrt{8} = [2; \overline{1, 4}], r = 2, and the fundamental solution of x^2 - 8y^2 = 1 is (p_1, q_1) = (3, 1). By Theorem 8 the positive solutions are \displaystyle x_j + y_j\sqrt{8} = (3 + \sqrt{8})^j, infinitely many, with x_{j+1} = 3x_j + 8y_j and y_{j+1} = x_j + 3y_j.

Each x_j is odd, because x_j^2 = 1 + 8y_j^2 is odd, so n = (x_j - 1)/2 is a positive integer with T_n = y_j^2. Conversely each square triangular T_n = s^2 with n \ge 1 gives the positive solution (2n + 1, s). So the square triangular numbers are exactly the y_j^2, one for each j \ge 1, and there are infinitely many.

The solutions run (3, 1), (17, 6), (99, 35), (577, 204), then (3363, 1189), since 3 \cdot 577 + 8 \cdot 204 = 3363 and 577 + 3 \cdot 204 = 1189. So n = 1681, and the next square triangular number is T_{1681} = 1189^2 = 1{,}413{,}721. Theorem 8 also shows the list of four was complete.

Example 6

When the period must be even

Prove that if d has a prime factor p \equiv 3 \pmod{4}, then x^2 - dy^2 = -1 has no integer solution, and the period of \displaystyle \sqrt{d} is even.

Solution

Suppose x^2 - dy^2 = -1. Modulo p, x^2 \equiv -1, and p \nmid x (otherwise p \mid 1). Write p = 4j + 3. By Fermat's little theorem, x^{p-1} \equiv 1; but

x^{p-1} = (x^2)^{2j+1} \equiv (-1)^{2j+1} = -1 \pmod{p}.

Then 1 \equiv -1, so p \mid 2, false for an odd prime. So there is no solution, and since an odd period would produce one by Theorem 7, the period is even. For d = 22 = 2 \cdot 11 this predicts the period r = 6 of Example 2. Whether x^2 \equiv -1 \pmod{p} is solvable is the question of whether -1 is one of the Quadratic residues and the Legendre symbol.

Boundaries

d must not be a square. If d = m^2, then (x - my)(x + my) = 1 forces both integer factors to be \pm 1, so y = 0. For d < 0 the curve is an ellipse with finitely many integer points.

The -1 equation. It is solvable exactly when the period is odd. Example 6 is sufficient, not necessary: 34 = 2 \cdot 17 has no prime factor p \equiv 3 \pmod 4, yet \displaystyle \sqrt{34} = [5; \overline{1, 4, 1, 10}] has period 4, so x^2 - 34y^2 = -1 has no solution.

Periodicity is special. An expansion is eventually periodic exactly when \alpha is an irrational root of a quadratic with integer coefficients (Lagrange; Stein, Section 5.5). The expansion of \displaystyle \sqrt[3]{2} is not periodic, and nothing here applies to it.

Where this goes next

Theorem 8 says the numbers \displaystyle x + y\sqrt{d} of norm 1 are, up to sign, the powers \varepsilon^n: the simplest case of Dirichlet’s unit theorem in algebraic number theory. The definite equation x^2 + y^2 = n has only finitely many solutions, and Sums of two squares decides which n have any. Continued fractions also open Diophantine approximation: Hurwitz’s theorem (stated without proof) improves Theorem 3’s 1/q^2 to \displaystyle 1/(\sqrt{5}\,q^2) for infinitely many fractions, and the golden ratio [1; \overline{1}], with Fibonacci convergents, shows \displaystyle \sqrt{5} cannot be raised.

Exercises

Continued fractions of rational numbers

  1. Find the continued fraction of 311/97.
  2. Write [2; 3, 1, 4] as a fraction in lowest terms.
  3. Use the convergents of 311/97 from Exercise 1 to find integers x and y with 311x - 97y = 1.
  4. Find the continued fraction of -17/5.

Infinite continued fractions

  1. Find the exact value of [3; \overline{3}].
  2. Find the exact value of [3; \overline{1, 6}].

Square roots and Pell’s equation

  1. Expand \displaystyle \sqrt{14} and find the fundamental solution of x^2 - 14y^2 = 1.
  2. Expand \displaystyle \sqrt{19} and find the fundamental solution of x^2 - 19y^2 = 1. Then read positive solutions of x^2 - 19y^2 = 5 and x^2 - 19y^2 = -2 off the convergents.
  3. Expand \displaystyle \sqrt{41}. Find a positive solution of x^2 - 41y^2 = -1 and the fundamental solution of x^2 - 41y^2 = 1.
  4. The expansion of \displaystyle \sqrt{61} has a_0 = 7 and the repeating block 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14. Find the solution of x^2 - 61y^2 = -1 that Theorem 7 gives, then square it to get a solution of x^2 - 61y^2 = 1.

Generating solutions

  1. Find every positive solution of x^2 - 7y^2 = 1 with x < 10{,}000.
  2. Mei’s square courtyard is paved with x by x identical square stones, x > 1. The center stone stays under a fountain; Kofi lifts the other x^2 - 1 and relays all of them as 6 identical square patios. Find the two smallest possible values of x and the patio size for each.

Proofs

  1. Prove that for every positive integer m, \displaystyle \sqrt{m^2 + 2} = [m; \overline{m, 2m}], and that the fundamental solution of x^2 - (m^2 + 2)y^2 = 1 is (m^2 + 1, m).
  2. Prove that the solutions of Theorem 8 satisfy x_{n+1} = 2x_1 x_n - x_{n-1} and y_{n+1} = 2x_1 y_n - y_{n-1} for n \ge 1, with (x_0, y_0) = (1, 0).
  3. Prove that y_1 \mid y_n for every n \ge 1.
  4. Prove that if 4 \mid d, then x^2 - dy^2 = -1 has no integer solution.
Answers
  1. [3; 4, 1, 5, 1, 2]. The Euclidean algorithm: 311 = 3 \cdot 97 + 20, 97 = 4 \cdot 20 + 17, 20 = 1 \cdot 17 + 3, 17 = 5 \cdot 3 + 2, 3 = 1 \cdot 2 + 1, 2 = 2 \cdot 1.
  2. 43/19. The numerators are 2, 7, 9, 43 and the denominators 1, 3, 4, 19; Theorem 2 makes the last pair coprime.
  3. x = 34, y = 109 (in general x = 34 + 97t, y = 109 + 311t). The numerators are 3, 13, 16, 93, 109, 311 and the denominators 1, 4, 5, 29, 34, 97. At k = 5 the determinant identity gives 311 \cdot 34 - 109 \cdot 97 = 10{,}574 - 10{,}573 = 1.
  4. [-4; 1, 1, 2]. \lfloor -17/5 \rfloor = -4 and -17/5 = -4 + 3/5; then 5/3 = 1 + 2/3, 3/2 = 1 + 1/2, and 2.
  5. \displaystyle (3 + \sqrt{13})/2. The tail after a_0 is the whole fraction again, so x = 3 + 1/x with x > 3, giving x^2 - 3x - 1 = 0 and the positive root \displaystyle (3 + \sqrt{13})/2 \approx 3.30.
  6. \displaystyle \sqrt{15}. The tail \beta = [1; \overline{6, 1}] repeats after two steps, so \beta = 1 + 1/(6 + 1/\beta) = 1 + \beta/(6\beta + 1), giving 6\beta^2 - 6\beta - 1 = 0 and the positive root \displaystyle \beta = (3 + \sqrt{15})/6. The value is \displaystyle 3 + 6/(3 + \sqrt{15}), which is \displaystyle 3 + (\sqrt{15} - 3) = \sqrt{15}.
  7. \displaystyle \sqrt{14} = [3; \overline{1, 2, 1, 6}] and (15, 4). P_k: 0, 3, 2, 2, 3; Q_k: 1, 5, 2, 5, 1; so r = 4, even. Convergents 3/1, 4/1, 11/3, 15/4, and 15^2 - 14 \cdot 4^2 = 225 - 224 = 1.
  8. \displaystyle \sqrt{19} = [4; \overline{2, 1, 3, 1, 2, 8}] and (170, 39); then (9, 2) and (13, 3). P_k: 0, 4, 2, 3, 3, 2, 4; Q_k: 1, 3, 5, 2, 5, 3, 1; r = 6. Numerators 4, 9, 13, 48, 61, 170, denominators 1, 2, 3, 11, 14, 39; 170^2 = 28{,}900 = 19 \cdot 1521 + 1. By Theorem 4, p_1^2 - 19q_1^2 = Q_2 is 81 - 76 = 5 and p_2^2 - 19q_2^2 = -Q_3 is 169 - 171 = -2.
  9. \displaystyle \sqrt{41} = [6; \overline{2, 2, 12}]; (32, 5) and (2049, 320). P_k: 0, 6, 4, 6; Q_k: 1, 5, 5, 1; r = 3, odd. Convergents 6/1, 13/2, 32/5, and 1024 - 41 \cdot 25 = -1. Continuing with 12, 2, 2 gives numerators 397, 826, 2049 and denominators 62, 129, 320, and 2049^2 - 41 \cdot 320^2 = 4{,}198{,}401 - 4{,}198{,}400 = 1.
  10. (29{,}718, 3805), then (1{,}766{,}319{,}049, 226{,}153{,}980). The period is 11, odd, so the -1 solution is (p_{10}, q_{10}). Numerators: 7, 8, 39, 125, 164, 453, 1070, 1523, 5639, 24{,}079, 29{,}718; denominators: 1, 1, 5, 16, 21, 58, 137, 195, 722, 3083, 3805. Check: 29{,}718^2 = 883{,}159{,}524 and 61 \cdot 3805^2 = 883{,}159{,}525. Squaring gives x = 29{,}718^2 + 61 \cdot 3805^2 and y = 2 \cdot 29{,}718 \cdot 3805, Fermat’s pair from the start of the lesson.
  11. (8, 3), (127, 48) and (2024, 765). \displaystyle \sqrt{7} = [2; \overline{1, 1, 1, 4}] with r = 4 gives (p_3, q_3) = (8, 3). Theorem 8 gives (64 + 63, 48) and then x = 8 \cdot 127 + 7 \cdot 3 \cdot 48 = 2024, y = 8 \cdot 48 + 3 \cdot 127 = 765; the next has x = 16 \cdot 2024 - 127 = 32{,}257 (Exercise 14), and nothing lies between.
  12. x = 5 with 2 by 2 patios, and x = 49 with 20 by 20 patios. Patios of y by y stones need x^2 - 1 = 6y^2, which forces x odd, so a center stone exists. \displaystyle \sqrt{6} = [2; \overline{2, 4}], r = 2, so the fundamental solution is (p_1, q_1) = (5, 2): 24 = 6 \cdot 4. Next, \displaystyle (5 + 2\sqrt{6})^2 = 49 + 20\sqrt{6}: 2400 = 6 \cdot 400. By Theorem 8 no value lies between.
  13. Let \displaystyle \alpha_0 = \sqrt{m^2 + 2}. Since m^2 < m^2 + 2 < (m + 1)^2 for m \ge 1, a_0 = m. Then \alpha_1 = 1/(\alpha_0 - m) = (\alpha_0 + m)/2, which lies between m and m + \tfrac12, so a_1 = m. Next \alpha_2 = 1/(\alpha_1 - m) = 2/(\alpha_0 - m) = \alpha_0 + m, between 2m and 2m + 1, so a_2 = 2m, and \alpha_3 = 1/(\alpha_0 - m) = \alpha_1. So \displaystyle \sqrt{m^2 + 2} = [m; \overline{m, 2m}], with period 2 (not 1, since a_1 \ne 2m). It is even, so by Theorem 7 the fundamental solution is (p_1, q_1) = (a_1 a_0 + 1, a_1) = (m^2 + 1, m); indeed (m^2 + 1)^2 - (m^2 + 2)m^2 = 1.
  14. Since \displaystyle \varepsilon^{-1} = x_1 - y_1\sqrt{d}, \varepsilon + \varepsilon^{-1} = 2x_1. Multiplying by \varepsilon^n gives \varepsilon^{n+1} + \varepsilon^{n-1} = 2x_1 \varepsilon^n for n \ge 1, with \displaystyle \varepsilon^0 = 1 + 0\sqrt{d}. Both sides have integer parts; comparing parts gives x_{n+1} + x_{n-1} = 2x_1 x_n and y_{n+1} + y_{n-1} = 2x_1 y_n.
  15. Strong induction with Exercise 14. y_0 = 0 and y_1 are multiples of y_1, and if y_{n-1} and y_n are, so is y_{n+1} = 2x_1 y_n - y_{n-1}.
  16. If 4 \mid d and x^2 - dy^2 = -1, then x^2 \equiv -1 \equiv 3 \pmod{4}. But every square is 0 or 1 modulo 4, since (2j)^2 = 4j^2 and (2j + 1)^2 = 4(j^2 + j) + 1.
math.wiki · CC-BY-SA-4.0