Tag Archives: niven-zuckerman-montgomery

Generalization of Pythagoras equation


About 3 years ago I discussed following two Diophantine equations of degree 2:

In this post, we will see a slight generalization of the result involving Pythagorean triplets. Unlike Pythagoras equation, x^2+y^2-z^2=0, we will work with a little bit more general equation, namely: ax^2+by^2+cz^2=0, where a,b,c\in \mathbb{Z}. For proofs, one can refer to section 5.5 of Niven-Zuckerman-Montgomery’s An introduction to the theory of numbers.

Theorem: Let a,b,c\in \mathbb{Z} be non-zero integers such that the product is square free. Then ax^2+by^2+cz^2=0 have a non-trivial solution in integers if and only if a,b,c do not have same sign, and that -bc, -ac, -ab are quadratic residues modulo a,b,c respectively.

In fact, this result helps us determine the existence of a non-trivial solution of any degree 2 homogeneous equation in three variables, f(X,Y,Z)=\alpha_1 X^2 +\alpha_2Y^2+\alpha_3Z^2+\alpha_4XY+\alpha_5YZ+\alpha_6ZX due to the following lemma:

Lemma: There exists a sequence of changes of variables (linear transformations) so that f(X,Y,Z) can be written as an equation of the form g(x,y,z)=ax^2+by^2+cz^2 with \gcd(a,b,c)=1.

Now let’s consider the example. Let f(x,y,z)=3x^2+5y^2+7z^2+9xy+11yz+13zx, and we want to determine whether this f(x,y,z)=0 has a non-trivial solution. Firstly, we will do change of variables:

\displaystyle{f(x,y,z)=3\left(x+\frac{3}{2}y +\frac{13}{6}z\right)^2 - \frac{7}{4}y^2 - \frac{85}{12}z^2 - \frac{17}{2}yz = g(x',y',z')}

where x' = x+\frac{3}{2}y +\frac{13}{6}z, y'=y and z'=z. Thus

\displaystyle{12g(x',y',z')=36x'^2 - 21 y'^2 - 85z'^2 - 102y'z' = 36x'^2 - 21\left(y'+\frac{17}{7}z'\right)^2+\frac{272}{7}z'^2=h(x'',y'',z'')}

where x'' = x',y'' = y'+\frac{17}{7}z' and z''=z'. Thus

\displaystyle{7h(x''',y'',z'') = 252x''^2 - 147y''^2+272z''^2=7(6x'')^2-3(7y'')^2 + 17(4z'')^2 = F(X,Y,Z)}

where X=6x'', Y=7y'' and Z=4z''. Now we apply the theorem to 7X^2-3Y^2+17Z^2=0. Since all the coefficients are prime numbers, we can use quadratic reciprocity to conclude that the given equation has non-trivial solution (only non trivial thing to note that -7\times 17 is quadratic residue mod -3, is same as -7\times 17 is quadratic residue mod 3).

Farey Dissection


The Farey sequence \mathcal{F}_n of order n is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed n. This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.

Thus \frac{h}{k} belongs to \mathcal{F}_n if 0\leq h\leq k\leq n and \text{gcd}(h,k)=1, the numbers 0 and 1 are included in the forms \frac{0}{1} and \frac{1}{1}. For example,
\displaystyle{\mathcal{F}_5 = \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}}

Following are the  characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers):

  1. If \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} are two successive terms of \mathcal{F}_n, then kh'-hk'=1.
  2. If \displaystyle{\frac{h}{k}}\displaystyle{\frac{h''}{k''}} and \displaystyle{\frac{h'}{k'}} are three successive terms of \mathcal{F}_n, then \displaystyle{\frac{h''}{k''}=\frac{h+h'}{k+k'}}.
  3. If \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} are two successive terms of \mathcal{F}_n, then the mediant \displaystyle{\frac{h+h'}{k+k'}} of \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} falls in the interval \displaystyle{\left(\frac{h}{k},\frac{h'}{k'}\right)}.
  4. If n>1, then no two successive terms of \mathcal{F}_n have the same denominator.

The Stern-Brocot tree, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.

Now, consider a circle \mathcal{C} of unit circumference, and an arbitrary point O of the circumference as the representative of 0 (zero), and represent a real number x by the point P_x whose distance from O, measured round the circumference in the anti-clockwise direction, is x.


Plainly all integers are represented by the same point O, and numbers which differ by an integer have the same representative point.

Now we will divide the circumference of the circle \mathcal{C} in the following manner:

  1. We take the Farey sequence \mathcal{F}_n, and form all the mediants \displaystyle{\theta = \frac{h+h'}{k+k'}} of the successive pairs \displaystyle{\frac{h}{k}}\displaystyle{\frac{h'}{k'}}. The first and last mediants are \displaystyle{\frac{1}{n+1}} and \displaystyle{\frac{n}{n+1}}. The mediants naturally do not belong themselves to \mathcal{F}_n.
  2. We now represent each mediant \theta by the point P_\theta. The circle is thus divided up into arcs which we call Farey arcs, each bounded by two points P_\theta and containing  one Farey point, the representative of a term of \mathcal{F}_n. Thus \displaystyle{\left(\frac{n}{n+1},\frac{1}{n+1}\right)} is a Farey arc containing the one Farey point O.

The aggregate of Farey arcs is called Farey dissection of the circle. For example, the sequence of mediants for n=5, say \mathcal{M}_5 is
\displaystyle{\mathcal{M}_5 = \frac{1}{6},\frac{2}{9},\frac{2}{7},\frac{3}{8},\frac{3}{7},\frac{4}{7},\frac{5}{8},\frac{5}{7},\frac{7}{9},\frac{5}{6}}

And hence the Farey disscetion looks like:


Let n>1. If P_{h/k} is a Farey point, and\frac{h_1}{k_1}, \frac{h_2}{k_2} are the terms of \mathcal{F}_n which precede and follow \frac{h}{k}, then the Farey arc around P_{h/k} is composed of two parts, whose lengths are
\displaystyle{\frac{h}{k}-\frac{h+h_1}{k+k_1}=\frac{1}{k+k_1}, \qquad \frac{h+h_2}{k+k_2}-\frac{h}{k}=\frac{1}{k(k+k_2)}}
respectively. Now k+k_1<2n, since k_1 and k_2 are unequal (using the point (4.) stated above)and neither exceeds n; and k+k_1>n (using the point (3.) stated above). We thus obtain:

Theorem: In the Farey dissection of order n, there n>1, each part of the arc which contains the representative \displaystyle{\frac{h}{k}} has a length between \displaystyle{\frac{1}{k(2n-1)}} and \displaystyle{\frac{1}{k(n+1)}}.

For example, for \mathcal{F}_5 we have:


Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of  Niven-Zuckerman-Montgomery’s An Introduction to the Theory of Numbers):

Theorem: If x is a real number, and n a positive integer, then there is an irriducible fraction \displaystyle{\frac{h}{k}} such that 0<k\leq n and \displaystyle{\left| x-\frac{h}{k}\right| \leq \frac{1}{k(n+1)}}

One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers  for details.