Back to the on-screen lesson ·
A quadratic equation with infinitely many integer solutions, all generated from one, and the continued fraction that finds it.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to verify a solution of Pell's equation, find the fundamental solution for a small coefficient by search, generate every further solution by composing it with itself, say why the coefficient must not be a perfect square and why the negative equation is a different question, and describe how the continued fraction of the square root produces the fundamental solution when search cannot.
Lesson 22 built the convergents of a rational number and showed they are the best approximations at their size, with error below $1/q^{2}$.
That bound is the whole connection to this lesson. If $p/q$ approximates $\sqrt d$ to within $1/q^{2}$, then $|p^{2} - dq^{2}| = |p - q\sqrt d| \cdot |p + q\sqrt d|$ is bounded by a constant — it cannot grow, however large $p$ and $q$ get. So among infinitely many convergents, some value of $p^{2} - dq^{2}$ must repeat, and from a repeat a solution can be manufactured. Good approximation is what forces a solution to exist.
Pell's equation is $x^{2} - dy^{2} = 1$ with $d$ a positive integer that is not a perfect square. $(1, 0)$ is the trivial solution.
The fundamental solution is the smallest solution in positive integers, ordered by $x$ (equivalently by $y$, since $x$ increases with $y$).
Composition combines two solutions into a third: $(x_1, y_1) \ast (x_2, y_2) = (x_1x_2 + dy_1y_2,\; x_1y_2 + x_2y_1)$. It is the multiplication of the numbers $x + y\sqrt d$, written in coordinates.
The negative Pell equation is $x^{2} - dy^{2} = -1$. It has solutions for some $d$ and not others, which is a harder and still not fully settled question.
Existence (Lagrange). For every positive non-square $d$, $x^{2} - dy^{2} = 1$ has a solution in positive integers.
The proof runs through the convergents of $\sqrt d$: they approximate it well enough that $p^{2} - dq^{2}$ stays bounded, so some value $k$ is taken infinitely often, and two solutions of $p^{2} - dq^{2} = k$ that agree modulo $k$ can be divided into each other to produce a solution with right-hand side $1$.
Why $d$ must not be a square. If $d = e^{2}$ then $x^{2} - e^{2}y^{2} = (x - ey)(x + ey) = 1$, forcing both factors to be $1$ and so $y = 0$. Only the trivial solution survives.
Composition, and why all solutions are powers. Identify $(x, y)$ with $x + y\sqrt d$. Then $$\left(x_1 + y_1\sqrt d\right)\left(x_2 + y_2\sqrt d\right) = (x_1x_2 + dy_1y_2) + (x_1y_2 + x_2y_1)\sqrt d,$$ and the quantity $x^{2} - dy^{2}$ is exactly the norm $\left(x + y\sqrt d\right)\left(x - y\sqrt d\right)$, which multiplies. So a product of two solutions is a solution.
Every solution is a power of the fundamental one. If some solution were not, it would lie strictly between two consecutive powers; dividing by the lower power gives a solution smaller than the fundamental one and bigger than $1$, which is impossible. So the solutions are $\left(x_1 + y_1\sqrt d\right)^{n}$ for $n = 1, 2, 3, \ldots$, and there are infinitely many.
Finding the fundamental solution. The continued fraction of $\sqrt d$ is eventually periodic, and the convergent one step before the end of the period gives $p^{2} - dq^{2} = \pm 1$: $+1$ if the period is even, $-1$ if it is odd. In the odd case composing that pair with itself gives $+1$.
Why searching fails. The fundamental solution is wildly irregular in $d$. For $d = 3$ it is $(2, 1)$; for $d = 13$ it is $(649, 180)$; for $d = 61$ it is $(1\,766\,319\,049,\; 226\,153\,980)$ — which Bhāskara found in the twelfth century by a method of this kind, and which no search would ever reach.
Another way: steps
Another way: example
$d = 7$: $y = 1$ gives $8$, not a square; $y = 2$ gives $29$, no; $y = 3$ gives $64 = 8^{2}$, yes. So $(8, 3)$ is fundamental, and $64 - 63 = 1$. The next solution is $(8^{2} + 7 \cdot 3^{2},\; 2 \cdot 8 \cdot 3) = (127, 48)$, and $16129 - 16128 = 1$.
Composition looks like a rule to memorise and is not: it is ordinary multiplication, seen in the right place.
Work in the set of numbers $x + y\sqrt d$ with $x, y$ integers, written $\mathbb{Z}[\sqrt d]$. It is closed under addition and multiplication, so it is a ring. Define the norm $$N\left(x + y\sqrt d\right) = \left(x + y\sqrt d\right)\left(x - y\sqrt d\right) = x^{2} - dy^{2}.$$
The norm is multiplicative: $N(\alpha\beta) = N(\alpha)N(\beta)$, because conjugation respects products. Three things follow at once.
Pell's equation asks for the elements of norm one. Two such multiply to another, so the solutions are closed under multiplication — which is composition, and the formula is just what multiplying out gives.
The solutions form a group. The inverse of $x + y\sqrt d$ with norm $1$ is $x - y\sqrt d$, since their product is $1$. So the solutions are a group under multiplication, and the theorem every solution is a power of the fundamental one says that group is infinite cyclic.
The whole thing is a unit group. An element of norm $\pm 1$ is exactly an invertible element of $\mathbb{Z}[\sqrt d]$. So Pell's equation is asking for the units of a ring of algebraic integers, and Lagrange's theorem — there is always a non-trivial solution — is the statement that this ring has infinitely many units. Dirichlet's unit theorem generalises it to any ring of algebraic integers, and it is one of the foundations of algebraic number theory.
So an equation that looks like a curiosity is the first case of a structural theorem, and the change of viewpoint from pairs of integers to numbers with a square root in them is what makes it visible. That is a move worth remembering: a Diophantine equation is often a statement about factorisation in a larger ring, and looks accidental until it is put there.
Forgetting $d$ must not be a square. When it is, the left side factors and only $(\pm 1, 0)$ survives. The theorem is about non-squares and says nothing otherwise.
Treating $(1, 0)$ as a solution worth having. It always works and generates nothing. Fundamental means the smallest solution in positive integers.
Assuming the negative equation behaves the same way. $x^{2} - dy^{2} = -1$ has no solution for $d = 3$: modulo $4$, $x^{2} - 3y^{2}$ is $0$, $1$ or $2$ and never $3$. Solvability there depends on the period of the expansion being odd.
Expecting the fundamental solution to grow with $d$. It does not. $d = 61$ has a nine-digit solution while $d = 60$ has $(31, 4)$. Neighbouring coefficients say nothing about each other.
Composing with the wrong signs. The rule is $(x_1x_2 + dy_1y_2,\; x_1y_2 + x_2y_1)$; the $d$ belongs in the first coordinate. Multiplying the two numbers out is safer than remembering the formula.
$d = 2$: trying $y = 1$ gives $2 + 1 = 3$, not a square; $y = 2$ gives $9 = 3^{2}$. So the fundamental solution is $(3, 2)$.
A short search, at this size.
Compose with itself: $(3^{2} + 2 \cdot 2^{2},\; 2 \cdot 3 \cdot 2) = (17, 12)$, and $289 - 288 = 1$.
Or square $3 + 2\sqrt2 = 17 + 12\sqrt2$.
Again: $(3 \cdot 17 + 2 \cdot 2 \cdot 12,\; 3 \cdot 12 + 17 \cdot 2) = (99, 70)$, and $9801 - 9800 = 1$. The ratios $3/2$, $17/12$, $99/70$ are the convergents of $\sqrt2$.
The solutions are the convergents, which is the connection made precise.
Does $x^{2} - 3y^{2} = -1$ have a solution? Try a congruence before searching.
A congruence is the cheapest thing to try.
Modulo $4$: squares are $0$ or $1$, so $x^{2} - 3y^{2} \equiv x^{2} + y^{2}$ is $0$, $1$ or $2$.
$-3 \equiv 1$ modulo $4$, which turns the difference into a sum.
But $-1 \equiv 3 \pmod 4$, which is not among them. So there is no solution — while $x^{2} - 3y^{2} = 1$ has infinitely many, starting at $(2, 1)$.
The sign on the right changes the problem completely.
$y = 1$ gives $5 + 1 = 6$, not a square; $y = 2$ gives $21$, no; $y = 3$ gives $46$, no; $y = 4$ gives $81 = 9^{2}$.
Increase the second unknown one step at a time.
So the fundamental solution is $(9, 4)$, and $81 - 80 = 1$.
Check before going on.
Composing with itself: $(9^{2} + 5 \cdot 4^{2},\; 2 \cdot 9 \cdot 4) = (161, 72)$, and $25921 - 25920 = 1$.
The smallest positive solution of $x^{2} - 7y^{2} = 1$ has $x = 8$ and $y = 3$. Fill in the table that checks it.
| Value | |
|---|---|
| The first unknown | |
| The second unknown | |
| The square of the first | |
| The coefficient times the square of the second |
What is the value of $x$ in the smallest positive solution of $x^{2} - 5y^{2} = 1$?
Answer:
Is this true: the fundamental solution grows steadily with the coefficient?
The smallest positive solution of $x^{2} - 15y^{2} = 1$ is $(4, 1)$. Give the next solution.
first unknown a, second unknown c
Match each equation to the first unknown of its smallest positive solution.
| $3$ | $4$ | $33$ | |
|---|---|---|---|
| $x^{2} - 8y^{2} = 1$ | |||
| $x^{2} - 15y^{2} = 1$ | |||
| $x^{2} - 17y^{2} = 1$ |
Searching for the smallest solution of $x^{2} - 17y^{2} = 1$ stops working for larger coefficients. Put the steps of the method that does not into the order they are carried out.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The smallest positive solution of $x^{2} - 15y^{2} = 1$ has $x = 4$ and $y = 1$. Fill in the table that checks it.
| Value | |
|---|---|
| The first unknown | |
| The second unknown | |
| The square of the first | |
| The coefficient times the square of the second |
You can find and check solutions of Pell's equation and generate the infinite family from the smallest one. Say in your own words why composing two solutions gives another. Next: how the primes are spread out among the integers.
9. Your turn: find the fundamental solution for $d = 5$ and the next one after it, step 3