Determine the number of integral points on hypotenuse of a right triangle

Question

If I have a right triangle with right angle at the origin and perpendicular sides along the X and Y axes, how can we determine the number of integral points on its hypotenuse?

Answer 1

Contrary to first appearance, that's not a simple problem at all, either if the intercepts on the axes (the sides of the triangle) are integral or not.

The problem is to find the solutions to $$ \bbox[lightyellow] { \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. }$$

Clearly, if only $a$ or only $b$ are irrational there are no solutions. But also when when they are rational there might be no solutions, e.g. for $a=b=7/2$.

Let's examine the various cases in detail.

• $a$ and $b$ irrational

As already said if only one them is irrational there cannot be any solution.
If both are irrational, also in general there is no solution, unless in the special case in which we can write $$ \bbox[lightyellow] { \eqalign{ & {{x - a} \over {x_{\,0} - a}} = {x \over {x_{\,0} - a}} - {a \over {x_{\,0} - a}} = {y \over {y_{\,0} }}\quad \Rightarrow \cr & \Rightarrow \quad {x \over a} - {y \over {y_{\,0} {a \over {x_{\,0} - a}}}} = 1\quad \Rightarrow \quad b = y_{\,0} {a \over {x_{\,0} - a}} \quad \left| {\;0 \le x_{\,0} ,y_{\,0} \in \mathbb Z} \right. \cr} } \tag{1}$$ when there is the only solution $(x_0,y_0)$ in fact.

• $a$ and $b$ integer

In this case the number of points is given by $$ \bbox[lightyellow] { N = 1 + \gcd (a,b) } \tag{2}$$ because the step $(\Delta x, \Delta y)$ between two solutions shall be such that $| \Delta y/ \Delta x |=b/a$ and the number of steps $k$ be such that $k|\Delta x|=a$ and $k|\Delta y|=b$.

• $a$ and $b$ rational

When $a$ and $b$ are rational, with simple passages we can reduce to $$ \bbox[lightyellow] { \left\{ \matrix{ 0 \le x,y,n,m,q \in \mathbb Z \hfill \cr n\,x + m\,y = q \hfill \cr} \right. }$$

If $x$ and $y$ could be also negative, then the above linear diophantine equation can be solved by the extended Euclidean algorithm, subject to $$ \bbox[lightyellow] { {\rm lcm}(a,b) = q\quad \Leftrightarrow \quad \gcd \left( {n,m} \right)\backslash q }$$

In the set of the solutions $\{(x_k,y_k)\}$ arising from the above, then you shall determine which, if any, are the couples with non-negative values.

The number of such non-negative solutions comes under the denomination of Restricted Partition Function $p_{\{n,m}\}(q)$, that is the number of partitions of $q$ containing only parts belonging to a given set $S$, in this case $S=\{n,m\}$.
This function is a building block in the Representability Problem or Frobenius Coin Problem.

The ogf of $p_{\{n,m}\}(q)$ is $$ \bbox[lightyellow] { {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} } \tag{3}$$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ \bbox[lightyellow] { p_{\{ n,m\} } (q) = {q \over {nm}} - \left\{ {{{n^{( - 1)} q} \over m}} \right\} - \left\{ {{{m^{( - 1)} q} \over n}} \right\} + 1\quad \left| {\;\gcd (n,m) = 1} \right. }\tag{4}$$ where $$ \bbox[lightyellow] { \left\{ \matrix{ \left\{ x \right\} = x - \left\lfloor x \right\rfloor \hfill \cr n^{( - 1)} n \equiv 1\quad \left( {\bmod m} \right) \hfill \cr m^{( - 1)} m \equiv 1\quad \left( {\bmod n} \right) \hfill \cr} \right. }$$

Answer 2

Develop the equation of the line which connects the two oblique vertices $\;\{(0, a) \text{and} (b, 0)\}.\qquad\qquad$ It is assumed that these two points are lattice points, of course.

Then solve as a linear Diophantine equation, yielding $\;\{x = c + dt;\quad y = e + ft\}.$

Then solve the two inequations $\;\{c + dt \ge 0 \; \text{and} \; e + ft \ge 0\}.$

This should yield a range $\;[g, h]\quad$ of valid values for $\;t.\quad$ Each of these values, substituted into the two expressions for $\;x\quad$ and $\;y,\quad$ will give you a lattice point of the hypotenuse.

The number of these (the question you asked) will be
max(g, h) - min(g, h) + 1.