# Simultaneous equations with a modulus

• May 5th 2011, 10:37 AM
Slimbiggins
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

-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.
• May 5th 2011, 10:47 AM
TheEmptySet
Quote:

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

-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

$-15a \equiv -5 \mod(26) \iff 15a \equiv 5 \mod(26)$

Now use the euclidean alogrithm to find 15 inverse mod 26

You should get 7

This gives

$7\cdot 15a \equiv 7 \cdot 5 \mod(26) \iff a \equiv 35 \mod(26) \iff a \equiv 9 \mod(26)$
• May 5th 2011, 10:52 AM
abhishekkgp
Quote:

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

-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:

http://latex.codecogs.com/png.latex?...\in \mathbb{Z}

substitute this in the second to get:

http://latex.codecogs.com/png.latex?...,(\,mod \, 26).

The last one is a linear congruence. You must know how to solve that. can you see what to do from here?
• May 5th 2011, 11:05 AM
Slimbiggins
Quote:

Originally Posted by TheEmptySet
So you have

$-15a \equiv -5 \mod(26) \iff 15a \equiv 5 \mod(26)$

Now use the euclidean alogrithm to find 15 inverse mod 26

You should get 7

This gives

$7\cdot 15a \equiv 7 \cdot 5 \mod(26) \iff a \equiv 35 \mod(26) \iff a \equiv 9 \mod(26)$

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.
• May 5th 2011, 11:09 AM
TheEmptySet
Quote:

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

$a\cdot 26 +b \cdot 15 =1$ now if you mod out by 26 you get

$b\cdot 15 \equiv 1 \mod{26}$ so b must be 15 inverse.
• May 5th 2011, 11:57 AM
Slimbiggins
Quote:

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

$a\cdot 26 +b \cdot 15 =1$ now if you mod out by 26 you get

$b\cdot 15 \equiv 1 \mod{26}$ 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.
• May 5th 2011, 12:09 PM
TheEmptySet
okay so you want to find 15 inverse mod 26

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

$26=1\cdot 15+11 \iff 11 = 26-1\cdot 15$

$15=1\codt 11 +4 \iff 4 = 15 -1\cdot 11$

$11=2\cdot 4+3 \iff 3 =11 -2\cdot 4$

$4 = 1\cdot 3+1$

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.

$1 = 4 - 1\cdot 3$

$1 = 4-1(11-2\cdot 4)=-1\cdot 11+3\cdot 4$

$1= -1\cdot 11+3(15 -1\cdot 11)=3\cdot 15-4\cdot 11$

$1 = 3\cdot 15-4\cdot (26-1\cdot 15)=7\cdot 15-4\cdot 26$

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

$1 = 7\cdot 15-4\cdot 26$

so we can see that 15 inverse is 7
• May 5th 2011, 01:01 PM
Slimbiggins
Thanks for all your help, I understand it now. Thanks again.