Thread: Simultaneous equations with a modulus

Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

4a + b (mod 26) = 20
19a + b (mod 26) = 25

I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

4a + b (mod 26) = 20
-19a - b (mod 26) = -25

then add them to get:
-15a = -5

It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.

Originally Posted by Slimbiggins

Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

4a + b (mod 26) = 20
19a + b (mod 26) = 25

I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

4a + b (mod 26) = 20
-19a - b (mod 26) = -25

then add them to get:
-15a = -5

It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.

So you have



Now use the euclidean alogrithm to find 15 inverse mod 26

You should get 7

This gives

Originally Posted by Slimbiggins

Hi, Im have trouble figuring out how to solve simultaneous equations of the form:

4a + b (mod 26) = 20
19a + b (mod 26) = 25

I know how to do simultaneous equations normally but with the modulus I keep messing up somewhere.

I multiplied everything in the top equation by + 1 and everything in the bottom equation by -1 to get:

4a + b (mod 26) = 20
-19a - b (mod 26) = -25

then add them to get:
-15a = -5

It seems obvious to me that Im doing something wrong but I've had trouble finding out how to do this properly. Thank you.

Hi slimbiggins! welcome to the forum.
here we go:

first congruence:



substitute this in the second to get:

.

The last one is a linear congruence. You must know how to solve that. can you see what to do from here?

Originally Posted by TheEmptySet

So you have



Now use the euclidean alogrithm to find 15 inverse mod 26

You should get 7

This gives

Thank you, that was very clear but I not sure about how you got the multiplicative inverse. I thought the euclildean algorithm finds the gcd of two numbers.

Originally Posted by Slimbiggins

Thank you, that was very clear but I not sure about how you got the multiplicative inverse. I thought the euclildean algorithm finds the gcd of two numbers.

See post number #3 here to see how it is done

http://www.mathhelpforum.com/math-he...tml#post646421

If does but if they are corpime then youcan express 1 as a linear combination 15 and 26

now if you mod out by 26 you get

so b must be 15 inverse.

Originally Posted by TheEmptySet

See post number #3 here to see how it is done

http://www.mathhelpforum.com/math-he...tml#post646421

If does but if they are corpime then youcan express 1 as a linear combination 15 and 26

now if you mod out by 26 you get

so b must be 15 inverse.

Sorry, I'm having trouble understanding this. I looked at the other post but couldn't figure out where everything was coming from.
I looked at some other tutorials and was equally confused. I know how to do the extended euclidean alogrithm but in your post and
the other tutorials it looks very different from the way I was shown how to do it. Everything else made perfect sense but getting the
inverse has me stumped.

okay so you want to find 15 inverse mod 26

So you start with 26 and divide it by 15 to get









Now that we have the remainder of 1 we want to express it in terms of 26 and 15.
we back substitute to work our way back to the top.









So now we have 1 as a linear combination of 15 and 26



so we can see that 15 inverse is 7

Thanks for all your help, I understand it now. Thanks again.