# Math Help - linear congruences

1. ## linear congruences

Q1.find an inverse of 19modulo 43.

so far I have worked through euclids algorithm to find gcd(19,43)=1. however when I try to work the algorithm in reverse to solve 19x +43y=1 I get confused.

Q2. Solve 19x congruend to 17 mod 43.

I assume this will be easier to answer once I have the answer for q1?! I have attempted to solve this by trying to solve 19x-43t=17, again I have worked through euclids algorithm to find again that gcd(19,43)=1, however once again I get confused when trying to work the algorithm in reverse.

Q3. Solve the system 19x congruent to 17 mod 43 and
x congruent to 18 mod 19.

Again I assume this will be easier once I have solved q1 and 2.

2. ## Hi

Q2:

$19x \equiv 17 (mod 43)$

This means: $19x - 43k = 17$

Solve this diofanthine equation by first constructing the help equation, HE.

HE: $19x - 43k = 1$

You say you know Euclides Algorithm. Working it backwards can be tricky, and obv the correctnes of the solution depends on not making any mistakes here.

$1 = 5 - 1*4 \ = 5 -1*(19 - 3*5)$ $= 43 -2*19 -1*(19 - 3*(43 - 2*19))$ $= 43 - 2*19 - 1*19 + 3*43 - 6*19 \ = -9*19 + (-43)*(-4)$

So we end up with a solution to HE being $x = -9 \ \mbox{and}\ k = -4$

Now multiply both the x-solution and k-solution with 17.
So you get ONE solution for $19x - 43k = 17$

This solution is: $x = -153 \ \mbox{and} \ k = -68$

Now we write: $x = -153 + 43*n \ \mbox{for some integer n}$

Since we are often interested in the positive solutions we get $x = 19$

Q3. Try doing the same with Q3, and then you have to find an x satisfying both these equations.

3. please could you explain a couple of steps for me...

the first is how we got 43- 2x19 + 43 - 6x19 = -9 x 19 + (-43)x(-4)

and then how from x=-153 and k=-68 we produce x=-153+43n resulting in x=19?!

i have followed everything else you said thank you.

4. ## hi again

Hi!

When using Euclides algorithm backwards, you want to express the number 1, in terms of (in this particular case) 43 and 19.

So we "go backwards" by substituting (first step) 4 with $19 - 3*5$

Now it is important that YOU DO NOT write $3*5$ as $15$

In the next step you replace 5 with $43 - 2*19$

Then it is simply a matter of simplifying the expression.
And we end up with $-9 * 19 \ \mbox{and} \ (-43)*(-4)$

If you test this solution then this should come out to be just 1, which was our goal in the first place.
Then to make this a solution for $19x - 43k = 17$ , you need to multiply your solution with 17.

We are only interested in the x in this equation, and we prefer positive values on x.

So we can write $x = -153 + 43*n \ \mbox{for some integer n, in this case n=4}$

By doing so we can increase our x-value by multiples of 43.
And the lowest positive value for x is just $x = 19$

I´m not great at explaining this, esp. since I am very new at this myself...

5. No thats brilliant, thank you very much. Sorry to ask for further explanation I just want to ensure I have a full understanding should I be faced with another problem with different values.

6. No problemo.

And I agree, if one doesn´t learn how to solve different equations and fully understand the concept, then it´s pointless.