Bezout's Identity: Finding A Pair of Integers

Question

There is only one integer $x$, between 100 and 200 such that the integer pair $(x, y)$ satisfies the equation $42x + 55y = 1$. What's the value of $x$ in this integer pair?

We know that

$$\begin{align} x &= x_0 + 5t \\ y &= y_0 - 4t \end{align}$$

But we need to know what $x_0, y_0$ are. By applying the GCD algorithm we can get the answer to be $x_0 = 17$ and $y_0 = 13$. So we need to find $100 \leq 17 + 5t \leq 200$. But treating this parametrically yields too many solutions. How do I discover the one solution?

Answer 1

First you need to find all integer solutions of $42x+55y=1$.[See this post]

Here $\gcd(42,55)=1$, so by Euclidean algorithm, $$1=42(-17)+55(13)\;[\text{check!}]$$

So integer solutions are $$x=-17+55r$$ $$y=13-42r$$ where $r \in \Bbb{Z}$

For your task, you need to find one $r$ so that $100 \leq x \leq 200$ and $r$ satisfies this.

Clearly for $r=1,2$, $x <100$. For $r=3$, we get $x=3(55)-17=\color{red}{148}$, which is the required number. For $r>3$ we get $x >200$ and if $r <0$ then $x<0$. Hence the required pair is $$(\color{red}{148},-113)$$

Answer 2

$$42x+55y=1\implies 42x\equiv 1\pmod {55}$$ $$\implies -13x\equiv (-55+42)x\equiv 42x\equiv 1 \pmod {55}$$ $$ \implies -52x\equiv 4(-13x)\equiv 4(1)\equiv 4 \pmod {55}$$ $$\implies 3x\equiv (55-52)x \equiv -52 x\equiv 4 \pmod {55}$$ $$\implies 54x\equiv (18)(3x)\equiv (18)(4)\equiv 72\equiv 17 \pmod {55}$$ $$ \implies -1x\equiv (54-55)x\equiv 54x \equiv 17 \pmod {55}$$ $$\implies x\equiv -17 \pmod {55}.$$

So $x=55z-17$ with $z\in \Bbb Z.$ And $100<x<200.$

So $100< 55z-17<200.$ So $117<55z<217$ so (obviously) $z=3$ and $x=55(3)-17=148.$

EXPLANATION: For the 2nd line we take the nearest multiple of $42$ to $55$ (which happens to be $42$ itself) so we transition from $42x$ to $(42-55)x=-13x $ because $|-13|<|42|.$

In the 3rd line we take nearest multiple of $-13$ to $-55,$ which is $(-13)4,$ so in the 4th line we transition from $-13x$ to $((-13)4+55)x=3x$ because $|3|<|-13|.$

In the 5th line we take the nearest multiple of $3$ to $55,$ which is $3(18),$ so we transition in the 6th line from $3x $ to $(3(18)-55)x=-1x$ because $|-1|<|3|.$ And that is as far as these steps can go.

Answer 3

Hint$\,\bmod 55\!:\ x\equiv \dfrac{1}{42}\equiv \dfrac{1}{6}\,\dfrac{1}7\equiv\dfrac{-54}6\,\dfrac{56}7\equiv -9(8)\equiv -17\equiv 38\ $ so $\ x = 38\!+\!55n$

Answer 4

First, you find a solution to $42x + 55y = 1$

\begin{array}{c|ccc|l|l} & 55 & 1 & 0 & &55 = 55(1)+42(0) \\ -1 & 42 & 0 & 1 & (55,1,0)+(-1)(42, 0, 1)=(13,1,-1) & 42 = 55(0)+42(1) \\ \hline -3 & 13 & 1 & -1 & (42, 0, 1) + (-3)(13,1,-1)=(3,-3,4)& 13 = 55(1)+42(-1) \\ -4 & 3 & -3 & 4 & (13,1,-1)+(-4)(3,-3,4)=(1, 13, -17)& 3=55(-3)+42(4) \\ & 1 & 13 & -17 & & 1=55(13)+42(-17) \end{array}

So $42(-17)+55(13)=1$. We get $(x_0,y_0)=(-17, 13)$.

Next you characterize the general solutions. $$(x,y)=(-17+55t, 13-42t)$$

Next, you search for the value of t that will put $x$ between $100$ and $200$. \begin{equation} 100 < -17 + 55t < 200 \\ 117 < 55t < 217 \\ \dfrac{117}{55} < t < \dfrac{217}{55} \\ 2 \frac{7}{55} < t < 3 \frac{52}{55} \\ t = 3 \\ \end{equation}

Finally, you compute $x$, $x = -17+55(3) = 148$