0
$\begingroup$

Find all values of $m$, s.t. $7x + 31y = m$ has exactly two positive solutions.

=> Finding a set of value for the particular solution (P.S.), using EEA (Extended Euclidean Algorithm): $$ \begin{align} 31 = 7.4 + 3 <--> & \ 3 = 31.1 + 7.(-4) \\ 7 = 3.2 + 1 <--> & \ 1 = 7 - 3.2 \implies & \ 1 = 7.9 - 31.2 \\ \end{align} $$

A new (though, unrelated) issue, that has cropped up, is which to actually take as $x_0$ (i.e., $a$), as I conventionally take the larger ( and hence, with negative coefficient in the PS ) value to be $a$ in the linear Diophantine equation(LDE) (formed by self) $ax+by =c$. But, here it is given that $31$ is $b$ (as $31$ has $y$ variable attached to it), and $31 \gt 7$.

Attempting solution :

Given, $d=1, x_0 = 9m, y_0 = -2m$.

Positive solutions are given by the number of integers $k$ satisfying : $d\frac{-x_0}{b} \lt k \lt \frac{y_0}{a}d => \frac{-9m}{31}d \lt k \lt \frac{-2m}{7}d => 0.290m \lt k \lt 0.285m$.

This is clearly not possible, unless either :-

(i) take $a=31, b=7$; or

(ii) $m$ is negative.

Pursuing the second approach (i.e.,, (ii)), $\frac{-9m}{31} \lt k \lt \frac{-2m} {7}$ => $-0.29m \lt k \lt -0.285m$.

But this also is not possible for any natural $m$. So, it means my conventional logic of taking the larger number as $a$ is correct.

By following that (i.e, (i)), the value range of $k$ is given by: $\frac{2m}{7} \lt k \lt \frac{9m}{31}$ => $0.285m \lt k \lt 0.29m.$ It means that need an integer value of m, s.t. there are two integer values possible between $0.285m$ & $0.29m$. This implies : $0.005m =3 \implies m = 600 \implies 171 \lt k \lt 174.$

The possible values of $k$ are : $172, 173$.

Now, coming to the question - it asks all values of $m$, but I have obtained only one value for $m = 600$. Can I take that the answer should be from $m=600$ to $m=799$ or so, based on the precision with which $\dfrac{2}{7}$ or $\dfrac{9}{31}$ is stated.

$\endgroup$
4
  • $\begingroup$ But, the question is not for all; but only two solutions. Anyway, there would not be infinite positive solutions, as the slope is negative (both, $a,b$ are positive (or, of the same sign)), so the line should cross the first quadrant with only two lattice points. $\endgroup$
    – jiten
    Dec 24, 2017 at 16:21
  • $\begingroup$ But, how to get the no. of lattice points lying on the line $7x + 31y =0$ is not clear to me. Request elaboration. $\endgroup$
    – jiten
    Dec 24, 2017 at 16:25
  • $\begingroup$ Agreed, but stated 'heuristic' in a wrong sense. Hence, requested elaboration. $\endgroup$
    – jiten
    Dec 24, 2017 at 16:30
  • $\begingroup$ The book takes the approach of taking $k$'s range in terms of P.S. $x_0, y_0$ values. If you want, I can detail the book's approach by editing OP. So, I proceeded that way. It also seems algebraically good. $\endgroup$
    – jiten
    Dec 24, 2017 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

It might be the case to collect my comments in an answer.

Does positive stand for strictly positive? In such a case, consider that once you have a solution $(x_0,y_0)$ of $7x+31y=m$, all the solutions have the form $(x_0+31k,y_0-7k)$ for $k\in\mathbb{Z}$. So $7\cdot 32+31\cdot 1=7\cdot 1+31\cdot 8=255$ looks like a good candidate.

My point is that $255$ can be represented as $7x+31y$ with $(x,y)>0$ in exactly two ways. The question is equivalent to finding the set of lines parallel to $7x+31y=0$ which go through exactly two lattice points in the first quadrant. So we may just pick a lattice point and count how many other lattice points lie on a parallel to $7x+31y=0$ through such point.

That is not an heuristic, that is an algorithm. Pick some $(x,y)>0$. If on a parallel to $7x+31y=0$ through such point there is just another lattice point, we have $x\in[32,62]$ and $y\in[1,7]$ or $y\in[8,14]$ and $x\in[1,31]$.

Pick some point, say $(x,y)=(25,18)$. The lattice points on the associated line are of the form $(25-31k,18+7k)$. These lattice points lie in the first quadrant iff $25-31k>0$ and $18+7k>0$, so $(25,18)$ is alone on the associated line.

Points which come in couples are given by $(x,y)\in[32,62]\times[1,7] \cup [1,31]\times[8,14]$.
The $7\cdot 31$ values of $m$ associated with these points are straightforward to compute:

$$\small\{255,262,269,276,283,286,290,293,297,300,304,307,311,314,317,318,321,324,325,328,331,332,335,338,339,342,345,346,348,349,352,353,355,356,359,360,362,363,366,367,369,370,373,374,376,377,379,380,381,383,384,386,387,388,390,391,393,394,395,397,398,400,401,402,404,405,407,408,409,410,411,412,414,415,416,417,418,419,421,422,423,424,425,426,428,429,430,431,432,433,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,473,474,475,476,477,478,480,481,482,483,484,485,487,488,489,490,491,492,494,495,496,497,498,499,501,502,504,505,506,508,509,511,512,513,515,516,518,519,520,522,523,525,526,527,529,530,532,533,536,537,539,540,543,544,546,547,550,551,553,554,557,558,560,561,564,567,568,571,574,575,578,581,582,585,588,589,592,595,599,602,606,609,613,616,620,623,630,637,644,651\}$$

$\endgroup$
15
  • $\begingroup$ Although not linked to the problem; I request code, if used, to generate the above values. In fact, that might make the logic more clear to me. $\endgroup$
    – jiten
    Dec 24, 2017 at 16:53
  • 1
    $\begingroup$ @jiten: nothing subtler than $7\text{Range}[32,62]+31\text{Range}[1,7]$. $\endgroup$
    – Jack D'Aurizio
    Dec 24, 2017 at 16:55
  • $\begingroup$ Any comments for my approach and solution are highly solicited. $\endgroup$
    – jiten
    Dec 24, 2017 at 17:09
  • 1
    $\begingroup$ @jiten: given $(x_0,y_0)>0$, you do not need that $\gcd(x_0,y_0)=1$ to count the number of lattice points on $7(x-x_0)+31(y-y_0)=0$ in the first quadrant. You just need to count how many times you can add/subtract $31$ from $x_0$ and subtract/add $7$ to $y_0$ while staying in the first quadrant. $\endgroup$
    – Jack D'Aurizio
    Dec 24, 2017 at 17:35
  • 1
    $\begingroup$ You only need to (extended) Euclidean algorithm to justify that all the solutions of $7x+31y=m$ are of the form $(x+31k,y-7k)$, but that is granted by the (co-)primality of $7$ and $31$. $\endgroup$
    – Jack D'Aurizio
    Dec 24, 2017 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .