0

I've been solving example questions from a book,there was some equation in the variables of x and y - $$8x=29+3y$$,I was required to find the minimum ratio between its LCM and GCD ,(x and y are integers).

So,I was proceeding well but i got stuck at a point where it said: Say,we found one value of each x and y to be $$x=1$$ and $$y=-7$$ . And it implies that the form of possible integer solutions for x and y respectively will be : $$x=3n+1$$ and $$y=8n-7$$ (n is a natural no).

This form works ,but I have no idea as to how they deduced the general form for possible solutions? I need a little assistance as to how these work. Thank you

Sharique Ahmad
  • 59
  • this is hard to read. Did you really mean $y-8x=29+3y$? Why not write that as $2y+8x=-29$ or the like? Note that writing it that way makes it obvious that there are no integers with this property. – lulu May 04 '22 at 19:08
  • If this is just a formatting problem, please see this tutorial on formatting. – lulu May 04 '22 at 19:09
  • It's a number theory problem, the original equation was- 8x-3y=29 . I was supposed to find the minimum ratio between the LCM AND GCD OF x and y where both x and y are integers. I got stuck on the part where they said "we know the form of possible solutions for x and y are as follows - x=3n+1 and y=8n+7 , where we found the first values by hit and trial and it came out to be x=1 and y=-7 – Sharique Ahmad May 04 '22 at 19:11
  • Once again, please review the formatting tutorial. Now it looks like you are writing $-8x-3y=-29$ but I doubt that's what you intended. Please edit your post using MathJax. – lulu May 04 '22 at 19:16
  • Oh,my apologies. I've made the necessary rectifications,thank you – Sharique Ahmad May 04 '22 at 19:19
  • With the equation, $8x-3y=29$, I don't think $(x,y)=(1,-7)$ is the minimum. That gives a ratio of $7$ but $(4,1)$ gives a ratio of $4$ and $(-29, -87)$ gives a ratio of $3$. So, all you have to show is that a ratio of $1$ or $2$ is not possible. – lulu May 04 '22 at 19:20
  • The minimum values are for the next part and that is kind of intuitive to me but I can't get the gist of how they deduced the both equations for x and y with one value(s) of each. Maybe I'm unfamiliar to the general idea behind this. – Sharique Ahmad May 04 '22 at 19:24
  • Well, note that $29=27+2=3\times k +2$. So we have $8x-3y=3k+2$ Since $8x=3\times 2x+2x$ we see that $2x-2=3y+3k+6x$. Thus $3$ divides $2x-2=2(x-1)$ Since $3$ does not divide $2$ we must have $3,|,(x-1)$ hence $x-1=3n$ or $x=3n+1$ as desired. – lulu May 04 '22 at 19:28
  • Perhaps a quicker way to see it is to note that we must have one of $x=3n$, $x=3n+1$, $x=3n+2$. Just try each case to see that only $3n+1$ gives an integer for $y$. Of course, this method depends on $3$ being a small number. – lulu May 04 '22 at 19:30
  • Aha, thank you ! I kind of thought it had something to do with modular arithmetic but i couldn't quite proceed,thank you again for the assistance. – Sharique Ahmad May 04 '22 at 19:36

3 Answers3

1

Suppose I have two solutions $(x_1,y_1)$ and $(x_2,y_2)$. They must satisfy $$ 8x_1 = 29 + 3 y_1 \\ 8x_2 = 29 + 3 y_2 $$ Now subtract these equations to get $$ 8(x_1 - x_2) = 3(y_1-y_2) $$ Since $8$ and $3$ are coprime, we must have $(x_1-x_2)|3$ and $(y_1-y_2)|8$. Thus, the solutions for $x$ are spaced out by multiples of $3$ and the solutions for $y$ are spaced out by multiples of $8$.

Further, once you have any individual solution, you can get the rest by just adding or subtracting $3$ from $y$ and $8$ from $x$ the same number of times. This can be seen from $8(x+3n) = 29 + 3(y + 8n) \Longrightarrow 8x + 24n = 29 + 3y + 24n$, which is clearly satisfied if $8x = 29 + 3y$.

eyeballfrog
  • 22,485
  • Thank you.I thought this much,for x and y to be integers x shoud divide 3 and y should divide 8 but I couldn't proceed on that,I totally overlooked it,it makes sense now. Have a good day – Sharique Ahmad May 04 '22 at 19:44
0

$$x=8^{-1}\cdot 29=2^{-1}\cdot 2=2\cdot 2=4=1 (\mod 3).$$

$$x=3n+1.$$

$$8(3n+1)=29+3y \Leftrightarrow y=8n-7.$$

hpbhpb
  • 41
  • This was the closest one to what my approach was.I just overlooked something very obvious that I could write $$1 (mod 3)$$ as 3n+1 and later substitute the x into the original equation. Thank you so much,good day. – Sharique Ahmad May 04 '22 at 20:05
0

We can reduce the gcd by successively removing $an+b$ where the $a$ is the smallest, i.e. $$\gcd(u,v)=\gcd(u-v,v)$$

$\begin{align}\gcd(8n-7,3n+1) &=\gcd(5n-8,3n+1)&\small-(3n+1)\\ &=\gcd(2n-9,3n+1)&\small-(3n+1)\\ &=\gcd(2n-9,n+10)&\small-(2n-9)\\ &=\gcd(n-19,n+10)&\small-(n+10)\\ &=\gcd(29,n+10)&\small-(n+10)\end{align}$

Now since $29$ is a prime number the gcd is either $1$ (in general) or $29$ (when $n=29k-10$).

If we take as a convention that gcd and lcm are positive then $$\gcd(x,y)\operatorname{lcm}(x,y)=|xy|$$

This gives us a quadratic polynomial in $n$ to minimize for the ratio $R=\dfrac{lcm}{gcd}=\dfrac{|xy|}{gcd^2}$

  • $\gcd=1$

$R=\dfrac{|(8n-7)(3n+1)|}{1^2}=|(8n-7)(3n+1)|$

It has two roots $-\frac 13$ and $\frac 78$ and since the quadratic is increasing outside the roots, we only have to test the following integer values

$$R(-1)=30\quad R(0)=7\quad R(1)=4$$

The minimum is clearly $4$ obtained for $n=1$ i.e. $(x=4,y=1)$

  • $\gcd=29$ when $n=29k-10$

$R=\dfrac{|(8n-7)(3n+1)|}{29^2}=|24k^2-17k+3|$

It has two roots $\frac 13$ and $\frac 38$ and since the quadratic is increasing outside the roots, we only have to test the following integer values

$$R(0)=3\quad R(1)=10$$

The minimum is clearly $3$ obtained for $k=0\iff n=-10$ i.e. $(x=-29,y=-87)$

And this is also the global minimum.

zwim
  • 28,563