What is modular arithmetic?

Question

I always see questions on here that deal with this modular stuff, and I have no idea what any of it means, so I figured I would ask here.

So lets say we have $$a \equiv b\pmod n$$ The example on wiki is $$38\equiv 14\mod 12$$ This is because 38-14 = 24, which has a factor of 12. Why is it 12 instead of 24, 3, 4? It gives an practical example of a clock. I get that that is a mod 12 (I think) but how do I write that in the notation used above? This is just some self learning in the small spare time I have

Answer 1

If you do programming, you should be familiar with the usage of % as an operator that (depending on your language) is either the remainder after division or modulus operator (they are slightly different in how they handle negative numbers, but they are essentially the same idea). If you are not familiar with it, I suggest you get familiar with it, because it is an extremely useful tool used in a number of different applications.

If two numbers a, and b, are equivalent mod n, we write $a \equiv b \mod n$, which is really a shorthand for the assertion that $\exists \ c\in\Bbb Z : a - b = c\cdot n$, or that the difference between $a$ and $b$ is some integral multiple of $n$. There are a number of other forms that one could put that assertion in, but they are all essentially equivalent to this one.

While $38\equiv 14\mod 2$, $38\equiv 14\mod 3$, $38\equiv 14\mod 4$, $38\equiv 14\mod 6$, $38\equiv 14\mod 8$, $38\equiv 14\mod 18$, and $38\equiv 14\mod 24$ are all true, the reason wikipedia use $38\equiv 14\mod 12$ as an example is because the article draws an analogy between modular arithmetic and time with it. The reason they use 12 is because the article was written by Americans, who use the numbers from 1 up through 12 to identify hours of the day (because it would be just silly to use the numbers up through 24 like everyone else, and nobody I know numbers their hours up through 2, 3, 4, 6, 8, or 18). In terms of the 'time' analogy for modular arithmetic, it basically means that you will be identifying the hour of the day with the same ordinal after 14 hours from now as you will after 38 hours.

Answer 2

I like to think of modular arithmetic as the arithmetic you obtain when you set a particular number equal to zero. Suppose $4=0$. Then $9 = 2(4)+1 = 2(0)+1=1$. So you say that 9 is congruent to 1 mod 4, or $9\equiv 1(\mod 4)$. If you're doing math on a clock, then you would use $12=0$.

Answer 3

I suspect that the root of your confusion is the symbol "$\equiv$". It looks kind of like an equals sign, but it doesn't behave like equality at all!

When we write $a=b$ with an equals sign, we mean that $a$ and $b$ are the same thing. As a result, if we know $a=x$, $b=x$, and $a=y$, then we can conclude that $b=y$.

However, when we write $a\equiv b\pmod n$, we do not mean that $a$ is the same thing as "$b\pmod n$". For example, the following statements are true:

$$ 6 \equiv 0\pmod 2\\ 6 \equiv 0\pmod 3\\ 8 \equiv 0\pmod 2\\ $$

However, $8\not\equiv 0 \pmod 3$. Rather, $8\equiv 2\pmod 3$.

Now that you know to be careful around "$\equiv$", the other answers to your questions will hopefully make more sense!

As you learn how modular arithmetic works, eventually you'll see why we write a symbol $\equiv$ that looks so much like $=$. For any fixed modulus $n$, the relation $a\equiv b\pmod n$ behaves like equality. So as long as you treat the $\equiv$ and the $\pmod n$ as a single entity, the notation makes sense.