Forums -> Social

### Player: Smaug Subject: Simultaneous equations

2008-12-26 08:57:17
How do you solve a pair of simultaneous equations in mod 26? Eg. 7 = 20a+b mod26 11 = 18a+b mod26-
1 viriol2008-12-26 14:36:02
What is mod? :P-

2 cc12418155002008-12-26 17:30:43
I was a mod,in the 60\'s -

3 RealChosenOne2008-12-26 19:34:44
@Smaug You have two possibilities: Either you solve it in the same way as a linear system of equations in every topological space (Use Gauß\'s algorithm and determine the solutions in your space.), but you have to keep track of the matrix operations and check, if they eliminate possible solutions. Or you transform it in the space \\IR and solve it as usual with Gauß\'s algorithm and transform the solutions back in your mod-space.-

4 Smaug2008-12-26 19:43:53
Umm... I\'m not that good at maths, I\'ve no idea what Gauss\'s algorithm is... Isn\'t there a simpler way? If I subtract I get 2a = -4 mod 26 = 22 mod 26, so a = 11 mod 13, but I don\'t know if i can substitute a mod13 result into a mod26 equation...-

5 RealChosenOne2008-12-26 23:07:00
You cannot put a mod 13 directly into the equation. You have to tranform it to mod 26 first, which in this case yields to a_1 = 0+ 11 mod 26 = 11 mod 26 and a_2 = 13 + 11 mod 26 = 24 mod 26. Now you put in a_1 and a_2 and get the solutions b_1 and b_2 respectively.-

6 RealChosenOne2008-12-26 23:10:23
By the way, what you have done is a simple version of Gauß\'s algorithm, but never mind, if you don\'t know it, you won\'t need it. The way you are handling this (subtracting and substituting) works perfectly, too.-

7 Smaug2008-12-27 07:51:53
Oh, right. Thanks!-

8 Smaug2008-12-27 07:56:24
Then 7 = 20a+b mod26, substituting in a=11 I get b = 7 - 220 mod26 = -213 mod26 so my simplest solution is a=11, b = 21 ?-

9 RealChosenOne2008-12-27 19:38:44
The first pair of solutions should be correct, but you have also to put in a_2 from which you get another pair of solutions. In this system of equations you have two pairs of solutions. You cannot simply drop one.-

10 Smaug2008-12-28 08:26:10
Oh, OK. Thanks!-

11 Smaug2008-12-28 19:14:02
It\'s not homework! It\'s for cracking the affine shift cipher.-

12 Smaug2008-12-28 19:15:08
I\'m very interested in that kind of thing - http://www.cipher.maths.soton.ac.uk/ has some interesting ones.-