Pythagorean triples and Pell's equations
source link: https://codeforces.com/blog/entry/116313
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Pythagorean triples and Pell's equations
Hi everyone!
Recently I started solving projecteuler, and while doing so I encountered two concepts about which I heard before, but I didn't really bother to learn them. I made a few notes to myself about how they work, and thought it could be useful for somebody else too. This blog focuses on Pythagorean triples and Pell's equations, which are recurrent concepts on projecteuler.
Great thanks to nor, Endagorion, Golovanov399 and Neodym for useful discussions about these topics.
Pythagorean triples
Pythagorean triple is a triple such that
It is possible to parameterize them in a way that allows to find all triples such that in .
Rational points on a unit circle
To do that, let's divide the equation by to get
This reduces the task of finding Pythagorean triples to finding rational points on a unit circle.
And there is a nice and simple way to find all such points. To do this, we should notice that a ray going from into a rational point will intersect the line in a rational point . So, we can find all rational points by projecting the point back onto unit circle for each .
We consider a ray from into to find rational points on the unit circleNote: The correct value for the numerator of in the image is
The direction vector of a ray from to is , so the equation of the ray is . Let's solve the system
After expressing as a function of like
we put it back into the first equation and get the result:
As it turns out, the projection point on a unit circle is also always rational, so we found a bijection between rational points in and rational points on the unit circle.
As a geometric inversion
It was also pointed to me that the bijection between the Pythagorean triples and the rational numbers can be perceived as an inversion transform on a complex plane. General formula for the inversion in the point with the radius is
where is complex conjugate. Therefore,
In our particular case we use and . Then the image of a real number is
which rewrites as
Then it follows from geometric inversion properties that all such points lie on the unit circle. And for it is
Back to integers
This translates back into integer triples as
Note that for integers such parameterization is incomplete, as the fraction could as well correspond to for some integer . Therefore, all possible triplets are obtained by multiplying vectors of the form defined above with all possible integer constants .
Pell's equations
Another somewhat recurring theme is Pell's equations. These are the equations that look like
We're looking for positive integer solutions to it. To understand the solutions better, we can relax it to inequalities
The two inequalities above are equivalent to the equation when are restricted to integers. Now, by dividing with we turn it into
The only possible lattice points satisfying the inequalities above are actual solutions to . It means that the set of lattice points in the quater-plane , for which , is a subset of the area surrounded by the curve . As this area is strictly convex (see the picture below), the subset can only intersect the boundary of the area in the convex hull of the subset. In other words, all solutions must lie on the convex hull of lattice points on .
Note that being on the convex hull of lattice points is a necessary, but generally not sufficient, condition for a solution.
Convergents (red) correspond to corners of the convex hull of lattice pointsFrom the theory of continued fractions it is known that such points are exactly the convergents of . Knowing this, and trying all convergents in order we will eventually find at least one non-trivial solution, from which it will be possible to find all the others (see below).
Solutions as a subgroup of matrices with determinant
The text above shows that if solution exists, it must be a convergent of . But still, we would like to know which particular convergents are the solutions and what is their general structure. To better understand it, let's rewrite the equation as
That's a very nice representation because of the following facts:
- If an integer matrix has determinant , its inverse is also an integer matrix with determinant .
- If two matrices have determinant , so does their product.
So, let's consider the inverse of the matrix under the determinant. It is
corresponding to the fact that if is an integer solution to the Pell's equation, so is . Now to the product:
In other words, if and are solutions, so is . This means that the full set of integer solutions to the Pell's equations in fact form a group with the group operation defined as above. Note that the point corresponds to the identity element of such group. Note that for the result is .
Solutions as a subgroup of
Another, perhaps simpler way to look on it is to consider numbers of kind . For such numbers, it's natural to define multiplication
and the multiplicative norm . Then it's also quite easy to see that the numbers satisfying form a group, as the norm is multiplicative, that is .
Periodicity of the continued fraction
Consider the continued fraction and its complete quotients . We can represent them as
where and are rational numbers. In fact, we can even prove that and are integers, and that
for any convergent . The proof is a bit technically involved, thus I will place it under the spoiler.
The identity above means that if and only if , that is . As it turns out, this is tightly related to the periodicity of the continued fraction of , and only ever happens at or after we just completed another period. To better understand this, we should prove the following fact:
That is, has a periodic fraction if and only if it's larger than and .
The result above allows us to prove that is periodic starting with , because from the very beginning. It, in turn, means that when we get to it must hold that , otherwise won't be in the interval . But this immediately tells us that .
Finding all solutions
In other words, the first non-trivial solution to is given by the convergent , where
and all the non-negative solutions are the convergents with indices for integer . This observation also allows to find the explicit correspondence between a convergent and its matrix representation. It generally holds for convergents that
If , we can additionally derive that
It makes a lot of sense, as applying the transform defined by such matrix to any convergent will simply add another period in front of it, thus moving it into . This gives explicit isomorphism between addition in convergent's indices and group operation in the solution group in terms of matrices. This also highlights that the solution group is cyclic, that is all solutions are obtained as powers of the smallest solution , which can be found with continued fractions.
Summary
In other words, to find all solutions to the Pell's equation , one may find the smallest solution as the first convergent of such that . Then all the other solutions are obtained as
for all integer .
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK