Concepts of congruence and modular arithmetic

Welcome to the World of Modular Arithmetic!

Ever noticed how if it is 10 o'clock now, in 5 hours it will be 3 o'clock (not 15)? You have been using modular arithmetic your whole life without even knowing it! In this chapter, we are going to formalize this "clock math." It is a powerful tool used in everything from computer science and cryptography to scheduling and patterns in numbers. Don't worry if it seems a bit abstract at first—we will break it down step-by-step.

1. What exactly is Congruence?

At its heart, modular arithmetic is all about remainders. When we say two numbers are "congruent," we simply mean they leave the same remainder when divided by the same number.

The Definition

We say that two integers \( a \) and \( b \) are congruent modulo \( n \) if their difference \( (a - b) \) is exactly divisible by \( n \). We write this as:
\( a \equiv b \pmod{n} \)

A simpler way to think about it:
Imagine you divide \( a \) by \( n \) and get a remainder. Then you divide \( b \) by \( n \) and get a remainder. If those two remainders are exactly the same, then \( a \equiv b \pmod{n} \).

Example: Is \( 17 \equiv 5 \pmod{6} \)?
Method 1: \( 17 - 5 = 12 \). Since 12 is divisible by 6, the answer is Yes.
Method 2: \( 17 \div 6 = 2 \) remainder 5. \( 5 \div 6 = 0 \) remainder 5. Since the remainders match, the answer is Yes.

Quick Review Box

\( a \equiv b \pmod{n} \) means:
1. \( n \) divides \( (a - b) \)
2. \( a \) and \( b \) have the same remainder when divided by \( n \)
3. \( a = b + kn \) for some integer \( k \)

2. The Rules of the Game (Properties)

The best part about modular arithmetic is that it behaves very much like regular algebra. This makes it incredibly useful for simplifying huge numbers.

Addition and Subtraction

If \( a \equiv b \pmod{n} \) and \( c \equiv d \pmod{n} \), then:
\( a + c \equiv b + d \pmod{n} \)
\( a - c \equiv b - d \pmod{n} \)

Multiplication

If \( a \equiv b \pmod{n} \) and \( c \equiv d \pmod{n} \), then:
\( ac \equiv bd \pmod{n} \)

Analogy: Imagine you are looking for the last digit of \( 12 \times 13 \). The "last digit" is just math in modulo 10.
\( 12 \equiv 2 \pmod{10} \)
\( 13 \equiv 3 \pmod{10} \)
So, \( 12 \times 13 \equiv 2 \times 3 \equiv 6 \pmod{10} \).
The last digit is 6! We didn't even need to calculate \( 12 \times 13 = 156 \).

The Power Rule (The Superpower!)

If \( a \equiv b \pmod{n} \), then for any positive integer \( k \):
\( a^k \equiv b^k \pmod{n} \)

This is the most helpful rule for H3 problems involving large exponents.

Key Takeaway

In modular arithmetic, you can replace a big number with its smaller remainder at any point in an addition, subtraction, or multiplication problem to make the calculation easier.

3. How to Solve "Large Power" Problems

A common H3 question might ask: What is the remainder when \( 3^{100} \) is divided by 7?
Don't reach for your calculator—it will explode! Instead, follow these steps:

Step 1: Look for a pattern. We want to find a power of 3 that is close to a multiple of 7 (ideally leaving a remainder of 1 or -1).
\( 3^1 \equiv 3 \pmod{7} \)
\( 3^2 \equiv 9 \equiv 2 \pmod{7} \)
\( 3^3 \equiv 27 \equiv 6 \pmod{7} \). Wait! 6 is the same as -1 in modulo 7 (because \( 6 - 7 = -1 \)).

Step 2: Use the Power Rule. Since \( 3^3 \equiv -1 \pmod{7} \), let's use that.
We can write \( 3^{100} \) as \( (3^3)^{33} \times 3^1 \).
Substituting our congruence: \( (-1)^{33} \times 3 \pmod{7} \).

Step 3: Simplify.
\( (-1)^{33} \) is just \( -1 \) (since the exponent is odd).
So, \( -1 \times 3 = -3 \).
In modulo 7, \( -3 \) is the same as \( 4 \) (because \( -3 + 7 = 4 \)).
Final Answer: The remainder is 4.

Did you know? Mathematicians use this logic to create secure passwords for the internet. RSA encryption relies on the fact that modular exponentiation is easy to do but very hard to "undo" without a secret key!

4. Common Mistakes to Avoid

Even the strongest students can trip up on these "traps."

The Division Trap:
In normal algebra, if \( 2x = 2y \), you can divide by 2 to get \( x = y \). You cannot always do this in modular arithmetic!
For example: \( 2 \times 3 = 6 \) and \( 2 \times 1 = 2 \).
In modulo 4: \( 6 \equiv 2 \pmod{4} \).
So, \( 2 \times 3 \equiv 2 \times 1 \pmod{4} \).
If you "canceled" the 2, you would get \( 3 \equiv 1 \pmod{4} \), which is wrong!
Rule of thumb: Only divide both sides if the number you are dividing by shares no common factors with the modulus (i.e., they are "coprime").

The Decimal Trap:
Modular arithmetic only works with integers. If you see a fraction or a decimal, you are no longer in the realm of standard modular arithmetic.

5. Summary and Mental Checklist

When you see a modular arithmetic problem, ask yourself:
1. Can I simplify the base numbers by finding their remainders first?
2. If there is a high power, can I find a "cycle" or a power that results in 1 or -1?
3. Am I avoiding the "division trap"?
4. If I have a negative result (like -2 mod 5), have I added the modulus back (like -2 + 5 = 3) to get a positive remainder?

Don't worry if this seems tricky at first! Like many things in H3 Mathematics, modular arithmetic is a skill that gets much easier with practice. Try finding the remainder of your birthday divided by 7 to see what "day of the week" logic looks like!