6
$\begingroup$

Minimize the expression $152207x-81103y$ over the positive integers, given $x,y\in\mathbb{Z}.$

So the book takes me through modular arithmetic and how to find $\text{gcd}(a,b)$ in order to solve diophantine equations. Then this question pops up in the same chapter.

I know how calculate using modular arithmetic, I know how to find $\text{gcd}(a,b)$ and solve diophantine equations but I don't know how to bunch them up together in order to solve this.

How should I think?

$\endgroup$
4
$\begingroup$

Since $\gcd (152207,81103)=1111$ it is the same as minimum of $$1111(137x-73y)$$

Since $137x-73y=1$ is solvable (say $x=8$ and $y=15$) the answer is $1111$.

$\endgroup$
  • $\begingroup$ Thanks! Could you please elaborate on why we need to set the expression $137x-73y$ equal to $1$ and determine its solveability? $\endgroup$ – Parseval Feb 4 at 18:24
  • 1
    $\begingroup$ Ok I think I get it. It's because $=1$ gives the smallest positive integer. $\endgroup$ – Parseval Feb 4 at 18:25
4
$\begingroup$

Note $c=ax+by$ has integer solution if and only if $gcd(a,b)|c$ and if this exists then infinite no of integer solutions can be obtained from 1 solution by

$x=x_{0}+\frac{b}{d}k$ and $y=y_{0}-\frac{a}{d}k$

where $d$ is the gcd. And $x_{0},y_{0}$ are one solution which can be obtained from euclid's algorithm. (As will jagy has mentioned)

And also the defination of $gcd(a,b)$ is least positive value of the $ax+by=d$ where $x,y$ any integer.

$\endgroup$
2
$\begingroup$

$$ \gcd( 152207, 81103 ) = ??? $$

$$ \frac{ 152207 }{ 81103 } = 1 + \frac{ 71104 }{ 81103 } $$ $$ \frac{ 81103 }{ 71104 } = 1 + \frac{ 9999 }{ 71104 } $$ $$ \frac{ 71104 }{ 9999 } = 7 + \frac{ 1111 }{ 9999 } $$ $$ \frac{ 9999 }{ 1111 } = 9 + \frac{ 0 }{ 1111 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 1 & & 7 & & 9 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 15 }{ 8 } & & \frac{ 137 }{ 73 } \end{array} $$ $$ $$ $$ 137 \cdot 8 - 73 \cdot 15 = 1 $$

$$ \gcd( 152207, 81103 ) = 1111 $$
$$ 152207 \cdot 8 - 81103 \cdot 15 = 1111 $$

$\endgroup$
  • $\begingroup$ Can you please explain the continued fraction part? $\endgroup$ – Parseval Feb 4 at 18:59
  • $\begingroup$ @Parseval you just start with the formal "fractions" $\frac{0}{1}$ and $\frac{1}{0},$ which just serve to start the process and mean nothing in themselves. Then for each "partial quotient" $d=1,1,7,9$ you just update the numerator by $n_j + d \cdot n_{j+1} = n_{j+2}.$ Similar for denominator. The usefulness for this problem is that the little 2 by 2 cross products are $\pm 1$ For example $2 \cdot 8 - 15 \cdot 1 = 1$ $\endgroup$ – Will Jagy Feb 4 at 19:04
  • $\begingroup$ This is not an answer to the question. OP says they already know how to compute the gcd. They need to know how to go from that to a solution of the stated problem, not another way to compute the (extended) gcd. $\endgroup$ – Bill Dubuque Feb 9 at 0:31
0
$\begingroup$

Other people have have answered. But the thing to take away from this is the idea of Bezout's Lemma (sometimes known as Bezout's Identity).

If $M,N$ are integers with greatest common divisor $\gcd(M,N)$ then there will exist integers $a,b$ so that $Ma + Nb = \gcd(M,N)$.

Another way of putting this is

If $j,k$ are relatively prime integers, then there will exist integers $a,b$ so that $ja + kb = 1$.

If we note that $\gcd(M,N)|M$ and $\gcd(M,N)$ then $\gcd(M,N)|Ma + Nb$ for any integers $a,b$ which leads to a third way of putting this

(Version 3) If $M,N$ are integers then:

  1. For any integers $a,b$ the $Ma + Nb$ will be a multiple of $\gcd(M,N)$.

  2. Integers $c,d$ exist so that $Mc + Nd = \gcd(M,N)$.

and therefore

  1. For any multiple of $\gcd(M,N)$, say $k\gcd(M,N)$ for some integer $k$, then integers $a,b$ exists so that $Ma + Nb = k\gcd(M,N)$. (Just let $a = kc; b=kd$ where $c,d$ are as in 2. above.)

And this answers your question.

  1. $152207x−81103y$ will always be a multiple of $\gcd(152207, 81103) = 1111$

  2. $152207x - 81103y = 1111$ will be possible.

And as the smallest positive integer that is a multiple of $1111$ is $1111$, the smallest positive value of $152207x -88103y$ is $1111$.

Notice, we don't have to actually find the values that make this true. It's enough to know it can be done!

====

Addendum:

1) Note: I never said and never implied that any of those integer pairs were unique.

$Ma + Nb = k\gcd(M,N)$ will actually have an infinite number of solutions.

Notice $M(a \pm w\frac N{\gcd(M,N}) + N(b \mp w\frac M{\gcd(M,N)}) = Ma + Nb = k\gcd(M,N)$ will always be a solution. But all solutions will be is such a form.

2) To actually find a solution

$152207x -88103y =1111$ we can use Euclid Algorithm

$152207 = 81103 + 71104; 71104 = 152207 - 81103$

$81103 = 71104 + 9999; 9999 = 81103 - 71104 = 81103 -(152207-81103) = 2*81103-152207$

$71104 = 7*9999 + 1111; 1111 = 71104 - 7*9999=(152207 - 81103)-7(2*81103-152207)=8*152207- 15*81103$

$9999 = 9*1111 + 0$ thats as far as we can go.

So for $x = 8; y = -15$ we get $152207x+81103y = \gcd(152207, 81103)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.