Skip to main content
amended for irrational
Source Link
G Cab
  • 35.4k
  • 3
  • 22
  • 63

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$$$ \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 $$ N = 1 + \gcd (a,b) $$$$ \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 $$ \left\{ \matrix{ 0 \le x,y,n,m,q \in \mathbb Z \hfill \cr n\,x + m\,y = q \hfill \cr} \right. $$$$ \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 EulideanEuclidean algorithm, subject to $$ {\rm lcm}(a,b) = q\quad \Leftrightarrow \quad \gcd \left( {n,m} \right)\backslash q $$$$ \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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$$$ \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 $$ 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. $$$$ \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 $$ \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. $$$$ \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. }$$

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$

Clearly, if $a$ or $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$.

  • $a$ and $b$ integer

In this case the number of points is given by $$ N = 1 + \gcd (a,b) $$ 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 $$ \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 Eulidean algorithm, subject to $$ {\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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ 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. $$ where $$ \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. $$

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. }$$

edited central part
Source Link
G Cab
  • 35.4k
  • 3
  • 22
  • 63

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$

Clearly, if $a$ or $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$.

  • $a$ and $b$ integer

AssumingIn this case the number of points is given by $$ N = 1 + \gcd (a,b) $$ 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 $$ \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 Eulidean algorithm, subject to $$ {\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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ 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. $$ where $$ \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. $$

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$

Clearly, if $a$ or $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$.

Assuming that $a$ and $b$ are rational, with simple passages we can reduce to $$ \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 Eulidean algorithm, subject to $$ {\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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ 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. $$ where $$ \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. $$

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$

Clearly, if $a$ or $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$.

  • $a$ and $b$ integer

In this case the number of points is given by $$ N = 1 + \gcd (a,b) $$ 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 $$ \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 Eulidean algorithm, subject to $$ {\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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ 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. $$ where $$ \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. $$

Source Link
G Cab
  • 35.4k
  • 3
  • 22
  • 63

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 $$ \left\{ \matrix{ 0 \le x,y \in \mathbb Z \hfill \cr {x \over a} + {y \over b} = 1 \hfill \cr} \right. $$

Clearly, if $a$ or $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$.

Assuming that $a$ and $b$ are rational, with simple passages we can reduce to $$ \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 Eulidean algorithm, subject to $$ {\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 $$ {1 \over {\left( {1 - z^n } \right)\left( {1 - z^m } \right)}} $$ and $p_{\{n,m}\}(q)$ can also be expressed, thanks to Popoviciu's theorem, as $$ 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. $$ where $$ \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. $$