Modular Arithmetic Basics

1. An Intuitive Start: Clock Arithmetic

Before diving into formal definitions, let's build some intuition. You've used modular arithmetic your whole life, probably without thinking about it, every time you've told time. If it's 10:00 AM and you have a 4-hour meeting, you know it will end at 2:00 PM, not 14:00. In a sense, on a 12-hour clock, 14 "is the same as" 2.

This idea of numbers "wrapping around" is the core of modular arithmetic. The following video provides an excellent introduction using this clock analogy.

As the video explains, we have several ways to think about this:

• The Clock Method: What time would it be on a clock with n hours?
• The Remainder Method: What is the remainder when you divide a number by n?

For example, 16 is "the same as" 4 on a 12-hour clock because the remainder of 16 divided by 12 is 4.

2. Formalizing Congruence

Now, let's translate this intuition into a precise mathematical statement.

We use the symbol $\equiv$ to denote congruence. The statement $a\equiv b(\mathrm{mod}n)$ is read as "a is congruent to b modulo n". The integer $n$ is called the modulus.

There are two equivalent ways to define this:

Definition 1: Based on Divisibility
Two integers $a$ and $b$ are congruent modulo $n$ if their difference, $a-b$, is a multiple of $n$.

$a\equiv b(\mathrm{mod}n)⟺n\mid (a-b)$

This is the formal definition you'll most often see in textbooks.

Definition 2: Based on Remainders
Two integers $a$ and $b$ are congruent modulo $n$ if they have the same remainder when divided by $n$.

This directly connects to our clock intuition and the Division Algorithm from our first lesson. The following video elegantly links these two definitions together.

Having these equivalent definitions is powerful. The divisibility definition is often best for proofs, while the remainder definition is usually best for computations.

3. Arithmetic with Congruences

The reason modular congruence is so useful is that it preserves the operations of addition and multiplication. This allows us to build a consistent system of arithmetic.

The fundamental rules are:
If $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$, then:

1. Addition: $a+c\equiv b+d(\mathrm{mod}n)$
2. Multiplication: $ac\equiv bd(\mathrm{mod}n)$
3. Powers: $a^k\equiv b^k(\mathrm{mod}n)$ for any positive integer $k$. (This is a direct consequence of the multiplication rule).

Since you have experience with proofs, it's worthwhile to see why these rules hold. The algebraic arguments are quite direct.

The real power of these rules is computational. They allow us to simplify large calculations by reducing intermediate numbers modulo $n$. Instead of calculating with big numbers and finding the remainder at the end, we can find remainders at every step.

This next video shows this principle in action.

Let's try an example that combines these rules.

4. Properties of Congruence: An Equivalence Relation

The congruence relation $\equiv$ shares three fundamental properties with the standard equality relation $=$. For any integers $a,b,c$ and a modulus $n\ge 2$:

1. Reflexive: $a\equiv a(\mathrm{mod}n)$
   • (Any number is congruent to itself.)
2. Symmetric: If $a\equiv b(\mathrm{mod}n)$, then $b\equiv a(\mathrm{mod}n)$
   • (You can swap the sides.)
3. Transitive: If $a\equiv b(\mathrm{mod}n)$ and $b\equiv c(\mathrm{mod}n)$, then $a\equiv c(\mathrm{mod}n)$
   • (If $a$ is like $b$ and $b$ is like $c$, then $a$ is like $c$.)

A relation that satisfies these three properties is called an equivalence relation. This is a central concept in abstract algebra because it allows us to partition a set into disjoint subsets, called equivalence classes. We'll explore this more in the coming lessons.

Conclusion

In this lesson, we established the fundamental concepts of modular arithmetic. This is the bedrock upon which we will build our first major algebraic structure.

Key Takeaways:

• Congruence Modulo n: $a\equiv b(\mathrm{mod}n)$ means that $n$ divides $a-b$, or equivalently, that $a$ and $b$ have the same remainder when divided by $n$.
• Modular Arithmetic: We can perform addition and multiplication with congruences. The key computational trick is to reduce numbers modulo $n$ at each step to keep the calculations simple.
• Equivalence Relation: Congruence is an equivalence relation, meaning it is reflexive, symmetric, and transitive, just like equality.

Preview of the Next Lesson:
Now that we understand how to do arithmetic with congruences, we are ready to formalize our "clock". We will define the set of integers modulo n, written as ${\mathbb{Z}}_n$, which consists of the remainders $\{0,1,2,\dots ,n-1\}$. We will then investigate the properties of this set under addition and see that it forms a structure known as a cyclic group.