Doubt in the method of finding the positive integral solutions of a linear equation in two variables.

Question

We want to find the positive integral solutions of the equation $$ 7x+12y=220 $$ I'm reading Higher Algebra by Hall and Knight (one of the greatest books ever written in mathematics), in Chapter X, just after article 138 (Indeterminate Equations) we have this solution

Divide throughout by 7, the smaller coefficient; thus $$ x+ y + \frac{5y}{7} = 31 + \frac{3}{7} \\ x+y + \frac{5y-3}{7} =31 ~~~.............................(1) $$ Since $x$ and $y$ are to be integers, we must have $$ \frac{5y-3}{7} = integer \\ \text{and therefore} ~~~~~~~~~~~~~~~~~~\color{red} {\frac{15y-9}{7}}= integer \\ \text{that is} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~2y-1 +\frac{y-2}{7} =integer \\ \text{and therefore}~~~~~~~~~~~~~~~~~~~~~~ \color{blue}{\frac{y-2}{7}} =integer= p~suppose\\ \therefore y-2 = 7p \\ y= 7p+2 ~~...................................(2) $$ Substituting this value of $y$ in $(1)$, $$ x+ 7p +2 + 5p +1 = 31 \\ x= 28-12p $$

Now, I know for any integral value of $p$ we will get a corresponding integral $x$ and $y$ (although we need to careful as we want only positive values of $x$ and $y$).

What's bothering me are the steps which are colored above, I mean why did we multiply by $3$ to get $15y-9$ and and then why did we leave out $2y-1$ in the blue colored step? For the multiplication by 3, they clarify

When we obtained $\frac{5y-1}{7}=integer$, we multiplied by 3 in order to make the coefficient of $y$ differ by unity from the multiple of 7. A similar artifice should always be employed before introducing a symbol to denote the integer.

My question: Can we always find a number like that? Such that when we multiply it to the coefficient of the variable it will differ by the multiple of denominator just by unity.

Can someone please guide me to some resources where I can find such artifices? I searched for these things in Chrystal's Algebra but couldn't find anything related to "integral solutions of an equation".

Answer 1

As $7$ and $12$ are coprime, simply start from a Bézout's relation, which always can be found with the extended Euclidean algorithm, but here you have obviously $$3\cdot 12 -5\cdot 7=1n \enspace\text{ whence }\enspace \forall N,\;3N\cdot 12-5N\cdot 7=N.$$ Therefore, we have a first solution: $x_0=-5N,\enspace y_0=3N$.

Now, if $(x,y)$ is any other solution, we have $$-5N\cdot 7+3N\cdot 12=N=7x+12y, \enspace\text{whence}\quad 7(x+5N)=12(3N-y).$$ Remember $7$ and $12$ coprime, so by Gauß' lemma, $7\mid 3N-y$ and $12\mid x+5N$. Furthermore, if we write $3N-y=7k$, $\;x+5N=12\ell$, the above equality simplifies to $ \ell=k$, and the general solution can be written as $$x=12k -5N, \quad y=3N-7k.$$

Answer 2

Yes, as long as your fraction is simplified, such a number exists, and is called a modular inverse.

The method that they've used here isn't actually a very good one for solving general Diophantines of form $ax+by=c$; what you want is the Extended Euclidean Algorithm.

Answer 3

A simple method $$7x+12y=220~~~~(1)$$ Let $$x=x_1-12n, y=y_1+7n~~~~~(2),$$ where $(x_1, y_1) $ is the first basic solution for example $y_1=2,x_1=28$ Now let us impose $x,y>0$, we get $n<7/3, n>-2/7 \implies n=0,1,2$ so three solutions: $(28,2), (16,9)$ and $(4,16)$

Note: For $ax+by=c$ if gcd(a,b)=1, then take $x=x_1\pm bn, y=y_1 \mp an$

The general result: $$ N=[\frac{c}{ab}],~ or~ [\frac{c}{ab}]+1$$ according as the remainder $R$ when $c$ is divided by $ab$ gives positive integral solution when $ax+by=R$ or not, respectively. Here $[.]$ represents GIF.

In your exanple when 220 is divided by 84, the remainder is 52 and $7x+12y=52$ admits a solution $(4,2)$, so $N=2+1=3$.