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.

Sign In or Register to comment.