Clarification on a Inverse modulo exercise

Question

Find integers $x$ and $y$ such that $49x + 100y = 1$. Which, if either, is the inverse of $49$, modulo $100$?

I know the answer to this is $x = 49$ and $y = -24$, but how do I arrive at that?

The argument starts with:

$$100 = 1(100) + 0(49)$$

$$49 = 0(100) + 1(49)$$

$$2 = 1(100) - 2(49)$$

The last step is:

$$1 = -24(100) + 49(49)$$

I just can't understand where the $-24$ and $49(49)$ came from.

Look gcd (100,49)=1 and you can express 1 as linear combination of 100 and 49. Hope so you know how to write that if not let me know i will show you the calculations. — , Dec 17 '15 at 18:16

score 3 · Answer 1 · answered Dec 17 '15 at 18:36

3

I think this will help you, if not you can ask for clarifications.

answered Dec 17 '15 at 18:36

1

let the equation be ax+ by =c , you can solve this type of equation iff gcd(a,b) | c , and process of finding solution is exactly same first write gcd(a,b) as a linear combination of a and b and multiply with appropriate integer. – Dec 17 '15 at 18:50

Aritra Das · Answer 2 · 2015-12-18T15:42:45.507

First of all, we begin by finding the gcd of $(49, 100)$ using Euclidean Division Algorithm, despite already knowing what it will be. (They're coprime) \begin{align*} 100&=49\times2+2 \\ 49&=2\times24+1 \\ 24&=24\times1+0 \end{align*} So, $1$ is the gcd of $100$ and $49$, but you already knew this.

And now, we keep substituting, from the last step upto the first: \begin{align*} 1&=49-2\times24 &\text{From the second equation}\\ &=49-(100-49\times2)\times24 &\text{From the first equation}\\ &=49-24\times100+48\times49 \\ \text{So,} \\ 1&=49\times49+(-24)\times100 &\text{And there you have it!} \\ \end{align*}

So, $$x=49, y=-24$$

Clarification on a Inverse modulo exercise

2 Answers2