How to solve the equations with modulo m

[KFC]

I am reading a paper on random numbers generation on congruential method

785 = 308a + k (mod 1024)
930 = 785a + k (mod 1024)

the solution is a=69 and k=13

Here is how I solve the problem. I multiply both side with 1024 such that the "mod" on the right side gone ,i.e.

785*1024 = 308a + k
930*1024 = 785a + k

subtract one from another gives

477a = 148480 ===> a = 311.2788

but this is wrong. What is the right way to solve this kind of equations?

Thanks.

 

[dodo]

Hi, KFC,
brace yourself for a mouthful.

I don't think there is a straightforward procedure; a solution can be found by some manipulation, but you need to learn a lot of new things to do such manipulations. Ill try to enumerate these below if you're interested.

First, this is not an equal sign. It is called "congruency", and mathematicians use three dashes instead of two, like this: ≡ (you can copy and paste it if needed). (Sometimes people in forums would write == to type quickly; the important thing is to recognize that it is a different relation.) This is important, because congruency is defined this way: x ≡ y (mod m) means that the difference x - y is a multiple of m. That's the definition.

In your example, the difference 308a + k - 785 is a multiple of 1024. (Same with the other line.) Now, "being a multiple of 1024" means that there exists some integer, call it "c", such that 308a + k - 785 = 1024c. And now this is a real equality sign.

As you see, the definition allows you to turn the congruences into equations with a true = sign, at the expense of adding an extra variable. In the end, you get 2 equations on 4 variables,

308a + k - 785 = 1024c
785a + k - 930 = 1024d

for some integers c and d. (This is OK, we will get rid of the c and d in a minute.) Now you can do the kind of manipulations you're used to; for example, subtract the two equations to eliminate the k:

145 - 477a = 1024(d-c)

Now, (d-c) is an integer, so the last equation reads "the difference 145 - 477a is a multiple of 1024". Using again the definition of congruency,

477a ≡ 145 (mod 1024)

Now we have a congruence on only one variable. The idea will be to find a solution for "a", and then substitute it in one of the two original congruences in order to solve for the "k". But to do that, you need to learn a few things about how to manipulate congruences directly.

First, you can add, subtract and multiply values on both sides of the congruence (and "sides" mean the expressions separated by the ≡, but not the (mod 1024); consider the mod 1024 untouchable for the moment). Note that I didn't say "divide": there are some special rules to divide at both sides, but you don't need that now. So, for the moment: add, subtract and multiply, leaving the (mod 1024) as it is. You can also substitute any number by another in the same congruency class: turn 1026 into 2, or viceversa; any two numbers with the same residue modulo 1024 can substitute for one another. In this respect; negative numbers "wrap around": -1 ≡ 1023, -2 ≡ 1022, and so on.

Second, there is a way to "cancel something out" (to get rid of the 477 next to the "a"). Some numbers have modular "inverses", for example: 7 is the inverse of 3 (mod 10), because 3*7 = 21 ≡ 1 (mod 10). So, when working modulo 10, if you have to eliminate the 7 in a congruence like 7a ≡ 2 (mod 10), you can multiply at both sides by 3, obtaining 3*7a ≡ 6 (mod 10); the 3*7 becomes a 1 (and disappears, since multiplying by 1 does nothing).

We will do something similar here: you need the inverse of 477 when working modulo 1024. One important thing you need to know, is that inverses only exist if 477 is "coprime", or "relatively prime", to 1024: both terms mean the same thing, namely, that 477 and 1024 have no common factor (other than the obvious 1). You're lucky in this case, since 1024 is a power of 2 (it is only made of 2's and nothing else; no 3's, no 5's, no nothing), while 477 have no 2's in it. Otherwise you'd have to learn about simplifying the common factor (the "special rules" about dividing I mentioned before), but it is not the case here.

There is an algorithm to obtain modular inverses, called "extended Euclidean algorithm" (feel free to google). The descriptions from the internet could be confusing; if it helps, I wrote a post recently about that, here:

https://www.physicsforums.com/showthread.php?t=477863

I used this algorithm to calculate the inverse of 477 (mod 1024), and after ten minutes of handywork obtained 629. (Easy to check: 629*477 = 300033 = 1024*293 + 1)

So, multiplying both sides of "477a ≡ 145" by 629, and keeping only the remainders modulo 1024, we end up with

a ≡ 145*629 = 91205 ≡ 69 (mod 1024)

We are almost there! Substituting a=69 into the first original congruence,

308*69 + k ≡ 785 (mod 1024)
k ≡ 785 - 308*69 (mod 1024)
k ≡ -20467 (mod 1024)

In order to "wrap around" the negative -20467, I can substitute it by 20*1024 - 20467:
k ≡ 20*1024 - 20467 (mod 1024)
k ≡ 13 (mod 1024)

And we are done: a=69, k=13. (Buffff...!)

 

[I like Serena]

I used this algorithm to calculate the inverse of 477 (mod 1024), and after ten minutes of handywork obtained 629. (Easy to check: 629*477 = 300033 = 1024*293 + 1)

I found a faster way to do the mod-inverse:

http://www.wolframalpha.com/input/?i=477a+=+145+mod+1024"

Good explanation though!