Minimize $152207x-81103y$ over the positive integers.

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?

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

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

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.

$$\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$$

• Can you please explain the continued fraction part? – Parseval Feb 4 at 18:59
• @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$ – Will Jagy Feb 4 at 19:04
• 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. – Bill Dubuque Feb 9 at 0:31

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.)

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!

====

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