How do you do modular arithmetic algebra?
The problem is 3x + 1 = 2 (mod 4)
I simplified it to 3x = 1 (mod 4), but now I'm completely lost. I know I can't just divide 3 by 1 because that doesn't give you an integer (correct me if I'm wrong). So what do I do next? I have a bunch of these problems to do, but if I can figure out how to do one, I can probably do the rest. Help would be appreciated.
Comments
In this case, if you try out small values of x, you can see that x = 3 works (3*3 = 9 = 1 in mod 4).
As you have probably noticed, modular arithmetic is not as straightforward as "normal" arithmetic. Whereas it's relatively easy to reverse multiplication with division under non-modular arithmetic, in modular arithmetic, it's not quite so simple.
Some problems, such as 4x = 1 (mod 4) have no solutions. Whether or not a solution exists depends on the factors of these numbers.
For your example, 3x = 1 (mod 4), you can tell that a solution is guaranteed to exist because 3 and 4 are relatively prime. This means that as we try out values of x from (x = 0) to (x = 3), we'll hit every possible value in mod 4 (in this case, the values 0, 1, 2, 3).
mod 4 arithmetic:
3 * 0 = 0
3 * 1 = 3
3 * 2 = 2
3 * 3 = 1
In general, for ax = c (mod m), if the values a and m are relatively prime, then as x ranges from {0, 1, 2, ..., m-1}, ax will eventually hit every integer from 0 to m-1 as well.