Motivation
The equation can look like a search problem with no stopping rule. Testing larger values of sometimes finds a small solution, but for the first positive one is already . A useful theory must explain why a solution exists, why a search will reach it, and how one solution generates every other solution.
The expression connects these questions. Multiplication preserves its norm , while conjugation changes the sign of the square-root term. Continued fractions supply infinitely many approximations whose norms stay in a bounded set of nonzero integers. A repetition argument then produces norm one. Finally, discreteness gives a smallest positive unit and turns multiplication into a classification.
Throughout, is an integer that is not a square. It need not be squarefree. We use the convergence, error bound and Legendre criterion proved in the preceding unit. No theorem asserting periodicity for every quadratic irrational is assumed.
Definitions
Definition 7.4.1
(Quadratic integers here, conjugation and norm)
Here , with its usual real multiplication. The representation is unique because is irrational. Define and . Conjugation preserves sums and products, so .
A unit of is an element with an inverse in . This happens exactly when its norm is or : one direction follows by multiplying integer norms, and the other from . A positive unit is positive as a real number. We do not assert that this ring is the full ring of integers of its quadratic field.
The positive Pell equation has norm one; the negative Pell equation has norm minus one. A positive solution means . Units also include and conjugates, so the statement about all units will carry more information than a list of positive solutions.
Theorems
Theorem 7.4.2
(Existence and a least generator)
For every nonsquare integer , has a solution with . There is a least unit among units of norm either sign. Every positive unit is for a unique integer , and every unit is .
If , there are no norm-minus-one units, and the positive solutions of norm one are the coefficients of for . If , norm-one positive solutions are the coefficients of for , and norm-minus-one positive solutions are the coefficients of for .
Concept lensGeometric
Units as one orbit on a hyperbola
Let be the least norm-one unit above one. Multiplication by acts on coefficient pairs by
an integer matrix of determinant whose inverse, multiplication by , is also integral. It preserves and every curve . The theorem says that the integer points on the branch of form exactly one orbit of this matrix, the orbit of .
Theorem 7.4.3
(Every positive Pell solution is a convergent)
If and , then is a reduced convergent of . Testing convergents for norm one therefore terminates and finds the least positive norm-one unit first. Testing for either sign finds first. These are termination and classification statements; no polynomial running-time bound is claimed.
Proof sketch or proof idea
Bounded norms produce a genuine unit
Proof
(A repeated norm and residue pair gives a unit)
Let be the convergents of . Their denominators tend to infinity and their errors are less than . For all sufficiently large , and . Thus the nonzero integers
satisfy
Nonzero follows from irrationality. Finitely many integer values are possible, so infinitely many of these pairs have the same norm . Passing to a further infinite subsequence, their pairs also agree modulo . The positive real numbers are unbounded. Choose two in that subsequence with .
Rationalizing their quotient gives
Both numerators are divisible by : modulo the first is , and the second is zero. Consequently the quotient belongs to , has norm one, and is greater than one. Write it as . Since its conjugate is ,
These are integers because the quotient is in . This proves existence. The repeated norm alone would not have made the quotient integral; the repeated residue pair is the additional step that makes the argument work.
Discreteness, followed by division into powers
Proof
(A least unit, then division into powers)
For a unit , its conjugate has absolute value . Therefore its integer coefficients satisfy and . There are only finitely many such pairs. Existence supplies at least one unit above one; among those no larger than that unit there is a least one, denoted .
For any positive unit , choose the unique integer with . Such an integer exists because powers of the real number are unbounded above and tend to zero in the other direction. Then is a positive unit in . Minimality forces , proving . Distinct powers have distinct positive real values. Every negative unit is the negative of a positive one.
The norm is multiplicative, so the asserted parity distinction follows from . A unit of either norm has , since in the coefficient formulas. Units between zero and one have a negative coefficient: negative if the norm is one and negative if the norm is minus one, as shows. Thus restricting powers as in the theorem gives exactly the positive solutions.
Proof X-ray
Two different finiteness arguments
The existence proof uses a finite set of possible norms and residues to create an integral quotient. The classification proof uses finiteness of integer coefficient pairs in a bounded real interval to obtain a smallest generator. Neither argument follows merely from observing several solutions. Once the generator exists, division by its powers eliminates every possible gap between consecutive powers.
Why the continued-fraction search finds the smallest solution
Proof
(Legendre’s criterion and the order of solutions)
For a positive solution, a common divisor of would have its square divide one, so is reduced. Rationalizing gives
For norm one, . For norm minus one, because , so and the denominator factor is again greater than two. Legendre's criterion proves the convergent claim.
Among positive solutions of either sign, increasing strictly increases . Indeed, if , then , so even the smallest possible exceeds the largest possible . For a fixed positive , the two norms cannot both occur: two nonnegative integer squares cannot differ by two. Denominators of convergents increase strictly after the possible initial pair with denominator one, and those two cannot both be Pell solutions by the same observation. Hence the first tested solution is the smallest unit of the specified norm class. Existence ensures that a norm-one test eventually succeeds.
An exact finite-state calculation for the square-root tails
One can generate the tails with integers rather than rounded square roots. Put . If , define
The reciprocal of gives the next tail after rationalization. Inductively are integers, , , and . Divisibility persists because . The upper bound on follows from the positive fractional part; its lower bound follows from and . Thus and is at most . The floor formula is exact: replacing by changes its numerator by a number strictly between zero and one, which cannot cross the next integer after division by the positive integer .
There are finitely many allowed integer states , and the next state is deterministic. A state must repeat, after which all later states repeat. This proves eventual periodicity for these square-root expansions. We have not proved the broader characterization of all eventually periodic real continued fractions, nor used a period-length parity rule to decide the negative equation.
Worked examples
Worked example 7.4.4
(The square root of two and a generator of negative norm)
The continued fraction begins with , whose norm is . It is the first positive solution of either sign, so . Its square is , the least norm-one unit above one. Every positive solution of is obtained from , . The first three are . Negative-norm solutions use odd powers of , beginning . The exponent parity comes from the norm homomorphism.
Worked example 7.4.5
(A negative equation with a local obstruction)
For , the first convergents are . Their norms are , so has norm one. Independently, is impossible modulo three because the only square residues are zero and one, whereas it would require . All positive norm-one solutions are powers of , beginning . Local impossibility and the global unit classification give compatible explanations.
Worked example 7.4.6
(Why thirteen has a large first norm-one solution)
The exact tail calculation gives . Before the entry six, its convergents are , with norms . Thus is the smallest unit above one of either norm. The least norm-one unit is its square,
The check is . A direct search that stops at a smaller bound would miss it. Here the approximation criterion and ordering proof certify minimality; merely displaying this identity would certify only one solution.
Counterexample mode
A convergent need not solve either Pell equation
For , the convergent has norm . Every positive Pell solution is a convergent, but the converse fails. The error threshold identifies where a solution must occur; the integer norm test still has to select it. Likewise, the theorem for nonsquare cannot be applied to a square parameter: if , then forces for the norm-one equation.
Common mistakes
Common mistake
(The ring is , and units below one have a negative coefficient)
The ring used here is specifically ; changing to the full ring of algebraic integers can change its unit generator. For , the larger ring contains , of norm , and is the generator found in this unit. A positive real unit can also have a negative coefficient if it lies below one, as shows.
Common mistake
(The least unit need not have norm one)
A least generator of units of both norms need not itself solve the positive Pell equation. Its square is needed when its norm is minus one: for , has norm , and the least norm-one unit is .
Common mistake
(Equal norms alone do not give an integral quotient)
Repeated bounded norms do not by themselves give an integral quotient; congruence matching is required. For , the convergents and both have norm , since . Their residue pairs modulo are and , and indeed
Similarly, a finite list of partial quotients does not prove repetition without an exact repeated state, and the proved termination of a convergent search supplies no unstated claim of fast computation for large input .
Summary
Small approximation errors bound the integer norms of convergents. Matching both norm and residues creates a positive norm-one unit. Discreteness then yields a least generator and classifies all units by powers. Legendre's criterion places every positive Pell solution among the convergents, making the exact search both terminating and complete.
Exercises
Quick check
(Find the least units above one of either norm and of norm one for , and write all positive solutions of both Pell equations.)
Compute the first tail exactly.
Solution · Answer
The first tail is , with integer part four and the same fractional part as the original input. Hence . Its first convergent has norm , so and . Positive norm-one solutions are the coefficients of , ; positive norm-minus-one solutions are the coefficients of , . No others occur by the unit theorem.
Quick check
(If is the least norm-one unit above one, derive an integer recurrence generating all positive norm-one solutions. Apply one step for starting with .)
Multiply by and compare coefficients.
Solution · Answer
Multiply by . This gives and , starting with . The powers classification proves completeness. For , the next pair is .
Quick check
(Prove that the complete integer solution set of is represented by the units , . Explain the signs of for negative and for the extra minus sign.)
Start from the classification and the parity of the norm.
Solution · Answer
If , take ; otherwise take . In either case the norm-one subgroup of all units is exactly by the parity calculation. For its coefficients are positive; for , conjugation gives , with positive . Multiplication by minus one reverses both coefficient signs. At this yields . Thus all integer sign choices are accounted for without adding nonexistent positive solutions.
Quick check
(Show directly that is impossible, and use to identify the least positive norm-one unit. Justify the displayed repeating expansion by exact tails.)
Work modulo for the negative equation.
Solution · Answer
Modulo three a solution of the negative equation would give , impossible. The first tail of is , with integer part two; its successor is , with integer part four; the next is the first tail again. The first convergents are of norm and of norm one. Thus the least unit above one is and all positive norm-one solutions are its positive powers. The local obstruction also independently excludes negative-norm units.