Modular Arithmetic

Jason Rosenhouse’s post about numbers mentions that he’s not touching modular arithmetic, so I suppose I should talk about that instead. Modular arithmetic is simply the arithmetic of remainders. In elementary or middle school, everyone learns that an odd number plus an odd number is an even number, an even plus an odd is odd, an odd times an even is even, and so on.

The arithmetic of odds and evens is simply arithmetic modulo 2, since we’re only concerned with whether an integer leaves a remainder of 0 or 1 when divided by 2. The three statements in the previous paragraph translate, in order, to 1 + 1 = 0 mod 2, 0 + 1 = 1 mod 2, and 0*1 = 0 mod 2. The mod operator is a shorthand for “modulo,” and pronounced either “modulo” or “mod”: “one plus one equals zero mod two.”

The same trick applies to any other integer. If a and b are any two integers, then the remainder a + b leaves when divided by 3 – or, in more technical language, the residue class of a + b mod 3 – only depends on the residue classes of a and b mod 3. To use random numbers as illustration, 2 + 8 = 10 is in the same residue class mod 3 as 5 + 2 = 7.

There’s one modular arithmetic everyone’s familiar with – arithmetic modulo 12, or sometimes 24. Four hours after ten o’clock is always two o’clock, regardless of whether it’s in the a.m. of 2006/2/1 or the p.m. of 2006/2/14. Likewise, 10 + 4 always equals 2 mod 12.

So we can add residue classes mod any integer n. We can also subtract, using the same principle. We can multiply, although multiplication sometimes acquires strange properties. For example, 2*3 = 0 mod 6, whereas in normal arithmetic, the product of two nonzero integers is always nonzero.

Division is somewhat trickier, though. Modular arithmetic is only defined for integers, not for rational numbers. It’s easy to tell that 17 = 7 mod 10, but what is 1/2 mod 10?

With normal integers, we can always form rational numbers. This is because for every nonzero integer a, there’s a rational number 1/a, with the property that a/a = 1. Then the fraction b/a = b*(1/a). So you may ask, is it even defined in modular arithmetic?

It turns out it is, sometimes. For a concrete example, let’s work mod 10. We have 3*7 = 21 = 1 mod 10, so we can define 1/3 to be 7, and 1/7 to be 3. In more technical language, 7 is the inverse of 3 and vice versa. Then division by 3 is essentially the same as multiplication by 7.

However, there exists no n such that 2*n = 1 mod 10. To see why, let’s work mod 2 instead of mod 10. We can do that because 2*5 = 10, so we can just let 1, 3, 5, 7, and 9 mod 10 be 1 mod 2, and 0, 2, 4, 6, and 8 mod 10 be 0 mod 2. We need to have 0*n = 1 mod 2, then. But that’s impossible, because 0*0 = 0*1 = 0 mod 2.

This holds for every integer other than 1 that either divides 10, or has a common factor with 10 greater than 1; the trick is to look at residue classes mod that number. Fortunately, it holds for all other integers. The numbers 2, 4, 5, 6, and 8, and of course 0, have the factors 2 or 5 in common with 10. For the others, we have 1*1 = 3*7 = 9*9 = 1 mod 10.

Not coincidentally, the best numbers to do modular arithmetic with are the prime numbers. If we work mod p, then since the only factors of p are itself and 1, the only common factor greater than 1 that n can have with p is p. But if n is divisible by p, then it must be 0 mod p. Therefore, all residue classes mod p except 0 have inverses.

Now, you may ask why anyone cares about modular arithmetic. The answer is, first, it’s important in computing. Much of computer science works mod 2, since gates only have two states – false, corresponding to 0, and true, corresponding to 1.

Second, in pure math, it’s very useful to use modular arithmetic since there’s a finite number of residue classes mod every n. My favorite example here is the equation a^2 – 7b^2 = 3. There are many solutions to the equation, like a = SQRT(3) and b = 0. But there are no solutions where both a and b are integers.

We can’t verify that with every possible pair of integers, since there are infinitely many integers. But we can verify that using modular arithmetic. If there’s a solution in integers, then there’s also a solution modulo every n. For example, let’s pick n = 7. The equation then becomes a^2 = 3 mod 7, since 7b^2 is obviously 0 mod 7.

Now that the equation is in modular arithmetic, we can just plug in every residue class mod 7 to see if it works. If a = 0 mod 7, then a^2 = 0 mod 7. If a = 1 mod 7, then a^2 = 1 mod 7. If a = 2, 3, 4, 5, 6 mod 7, then a^2 = 4, 2, 2, 4, 1 mod 7. In none of the cases is a^2 equal to 3 mod 7, so we can conclude that the equation has no solutions in integers.

9 Responses to Modular Arithmetic

  1. oztabvle4 says:

    online cash advances [URL=http://www.cashadvance.loans-about.com/online-cash-advances-1.html]online cash advances[/URL] cash advance loans [URL=http://www.cashadvance.loans-about.com/]cash advance loans[/URL]

  2. doemaar52 says:

    cash advance no checking [URL=http://www.cashadvance.loans-about.com/cash-advance-no-checking-1.html]cash advance no checking[/URL] cash advance no credit [URL=http://www.cashadvance.loans-about.com/cash-advance-no-checking-1.html]cash advance no credit[/URL]

  3. Stephen says:

    Hello, Aron –

    I have an embarrassingly stupid question. I can’t understand your mod2 examples. If you have 0+1, 0+1 = 1; 1/2 is 1, remainder 1? or 0, remainder 2? I also used the Java applet here: http://www.cut-the-knot.org/blue/Modulo.shtml

    And it still doesn’t work…ugh. I am also grinding through Schaum’s Outlines on Abstract algebra and have gotten everything rather easily so far, except for this *&$%!! section…

    help!

    Stephen B

  4. Stephen Answer says:

    In mod2 you can’t divide by 2 as it doesnt exist in the set {0,1}.

  5. One Hr Cash Loans…

    […]Modular Arithmetic « Abstract Nonsense[…]…

  6. Out of my examination, shopping for technology online can
    for sure be expensive, nevertheless there are some principles that
    you can use to help you get the best offers. There are
    constantly ways to find discount promotions that could help to make one to hold the best gadgets
    products at the lowest prices. Great blog post.

  7. Washing out and drying, it’s about time for a relaxing evening going over the posts on here… may have to nip out to the dump later with some recycling though!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: