algebra911.com

Modular Arithmetic

Q: What's the difference between 'mod' as an operator and 'mod' in congruence?

The 'mod' operator (like in $10 \pmod{3}$) asks for a specific result: the remainder, which is $1$. The 'mod' in a congruence statement ($10 \equiv 4 \pmod{3}$) describes a relationship, stating that $10$ and $4$ belong to the same 'remainder class' modulo $3$.

Q: Is 8 mod 5 the same as 5 mod 8?

No, they are very different. $8 \pmod{5}$ asks for the remainder when $8$ is divided by $5$, which is $3$. $5 \pmod{8}$ asks for the remainder when $5$ is divided by $8$, which is $5$ itself, since $8$ goes into $5$ zero times.

Q: Can the remainder be a negative number?

In formal mathematics, the remainder $r$ must be in the range $0 \le r < n$, where $n$ is the modulus. Some programming languages might give a negative result, but you can always find the correct positive equivalent by adding the modulus. For example, if you get $-2 \pmod{5}$, the correct answer is $-2 + 5 = 3$.

Q: How is modular arithmetic used in computers?

It's used everywhere! Computers use it for cryptography to keep data secure, in hash tables to store data efficiently, and to handle operations involving cyclical data, like clocks or angles in graphics. It's fundamental to computer science.

Q: What does a ≡ b (mod n) actually mean in simple terms?

It means that $a$ and $b$ are 'the same' in a world that only counts up to $n$. Think of a 12-hour clock (modulo 12). $14$ o'clock and $2$ o'clock are different in a 24-hour world, but they point to the same spot on a 12-hour clock, so $14 \equiv 2 \pmod{12}$.

Q: Why is it sometimes called 'clock arithmetic'?

Because a clock is the perfect everyday example. When you go past 12 o'clock, the numbers don't keep getting bigger; they wrap around back to 1. This 'wrapping around' is the core idea of modular arithmetic.

Q: Can you divide in modular arithmetic?

Yes, but it's more complicated than regular division. You can't just divide by any number. It involves finding something called a 'modular multiplicative inverse,' which is a bit like finding a reciprocal. It's a more advanced topic usually studied after the basics.

Download as PDF

Ever wonder how computers handle time or how secret codes are made? The answer often involves modular arithmetic, a fascinating system of math that deals with remainders. It’s like asking what time it will be $8$ hours after $9$ o’clock—you’re using math that cycles back around!

Modular Arithmetic — an original Algebra911 reference diagram defining modular arithmetic with its key formula and a worked example. — Modular Arithmetic: The Math of Clocks and Codes

What Is Modular Arithmetic?

Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after they reach a certain value, which is known as the modulus. The most familiar example of modular arithmetic is a 12-hour clock. On a clock, the hours go from $1$ to $12$ and then start over again at $1$ . If it's $10$ o'clock now, in $5$ hours it won't be $15$ o'clock. Instead, you calculate $10 + 5 = 15$ , and then you realize that $15$ o'clock is the same as $3$ o'clock. You've just performed modular arithmetic.

In this system, we are primarily interested in the remainder after division. When you found that $15$ o'clock was $3$ o'clock, you were implicitly doing a division problem. You were finding the remainder when $15$ is divided by $12$ . Since $15 = 1 \times 12 + 3$ , the remainder is $3$ . We say that $15$ is congruent to $3$ modulo $12$ .

This "wrapping around" idea isn't just for clocks. It's a fundamental concept in number theory, computer science, cryptography, and many other areas of science and engineering. It gives us a powerful way to work with relationships between integers, especially when dealing with cycles or repeating patterns. Whether you're figuring out the day of the week a year from now or understanding how computers encrypt data, you are using the principles of modular arithmetic.

What Does 'Congruent Modulo n' Mean?

In regular algebra, we use the equals sign ( $=$ ) to state that two quantities are identical. In modular arithmetic, we use a special symbol for a similar, but different, relationship: the congruence symbol ( $) e q u i v) . T h e s t a t e m e n t \(a \equiv b (\mod n)$ is read as " $a$ is congruent to $b$ modulo $n$ ".

This statement means two key things that are actually equivalent to each other:

When you divide $a$ by $n$ , you get the same remainder as when you divide $b$ by $n$ .
The difference between $a$ and $b$ , which is $a - b$ , is an integer multiple of $n$ . In other words, $n$ divides $a - b$ evenly with no remainder.

a \equiv b (\mod n)

, then

n | (a - b)

Let's break this down with an example. Consider the statement $17 \equiv 5 (\mod 12)$ . Is this true? Let's check both conditions:

Condition 1 (Same Remainder): What is the remainder of $17 \div 12$ ? The remainder is $5$ . What is the remainder of $5 \div 12$ ? The remainder is also $5$ . Since the remainders are the same, the statement is true.
Condition 2 (Difference is a Multiple): What is the difference $17 - 5$ ? The result is $12$ . Is $12$ a multiple of the modulus, $12$ ? Yes, $12 = 1 \times 12$ . So the statement is true.

Notice that many numbers can be congruent to each other. For example, $29$ is also congruent to $5$ modulo $12$ , because $29 \div 12$ gives a remainder of $5$ . So we can write 5 \equiv 17 \equiv 29 \equiv -7 \pmod{12}, and so on. All these numbers belong to the same congruence class or residue class modulo $12$ .

How Do You Calculate the Result in a Modulo System?

Calculating a value in a modulo system, often written as $a (\mod n)$ , means finding the unique integer remainder $r$ when $a$ is divided by $n$ . This process is based on the Division Algorithm, which states that for any integers $a$ (the dividend) and $n$ (the divisor, where $n > 0$ ), there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

a = q n + r

, where

0 \leq r < n

The result of the operation $a (\mod n)$ is simply $r$ . The key constraint is that the remainder $r$ must be greater than or equal to $0$ and strictly less than the modulus $n$ . This ensures there is only one possible answer.

Here's the step-by-step process:

Take the number $a$ and the modulus $n$ .
Divide $a$ by $n$ to find the whole number quotient, $q$ .
Multiply this quotient by the modulus: $q \times n$ .
Subtract this result from the original number $a$ to find the remainder: $r = a - (q \times n)$ .

Example 1

Calculate $100 (\mod 13)$ .

Step 1: We need to find the remainder when $100$ is divided by $13$ .

Step 2: Divide $100$ by $13$ . We know that $13 \times 7 = 91$ and $13 \times 8 = 104$ . So, $13$ goes into $100$ a total of $7$ times. The quotient $q$ is $7$ .

Step 3: Multiply the quotient by the modulus: $7 \times 13 = 91$ .

Step 4: Subtract this from the original number to find the remainder: $100 - 91 = 9$ .

The remainder is $9$ . Since $0 \leq 9 < 13$ , this is our final answer.

Therefore, $100 \equiv 9 (\mod 13)$ .

What about negative numbers? The process is the same, but you need to be careful to ensure the remainder is positive. For example, to find $- 50 (\mod 8)$ : $- 50 \div 8$ is $- 6.25$ . We must choose a quotient $q$ such that $r$ is positive. If we choose $q = - 7$ (rounding down), we get $a = q n + r ⟹ - 50 = (- 7) (8) + r ⟹ - 50 = - 56 + r ⟹ r = 6$ . So, $- 50 \equiv 6 (\mod 8)$ .

How Do You Add, Subtract, and Multiply in Modular Arithmetic?

One of the most useful features of modular arithmetic is that you can perform operations like addition, subtraction, and multiplication. The rules are straightforward and allow you to simplify your calculations by keeping the numbers small.

Modular Addition

To add two numbers in a modulo system, you can either add them first and then find the remainder, or find the remainder of each number first, add them, and then find the remainder of the result. The second method is often much easier.

(A + B) \pmod{n} = ((A \pmod{n}) + (B \pmod{n})) \pmod{n}

Modular Subtraction

Subtraction works just like addition. You can subtract first and then find the remainder, or find the remainders first, subtract, and then find the remainder of the result.

(A - B) \pmod{n} = ((A \pmod{n}) - (B \pmod{n})) \pmod{n}

If the subtraction results in a negative number, simply add the modulus $n$ until you get a positive result in the range $[0, n - 1]$ .

Modular Multiplication

Multiplication follows the same pattern. This property is especially powerful because it prevents numbers from becoming huge and difficult to work with during intermediate steps.

(A \times B) \pmod{n} = ((A \pmod{n}) \times (B \pmod{n})) \pmod{n}

Example 2

Calculate $(87 + 115) (\mod 10)$ .

Method 1: Add first.

$87 + 115 = 202$ .

Now find the remainder of $202$ when divided by $10$ . The remainder is clearly $2$ .

So, $(87 + 115) \equiv 2 (\mod 10)$ .

Method 2: Find remainders first.

First, find $87 (\mod 10)$ . The remainder is $7$ .

Next, find $115 (\mod 10)$ . The remainder is $5$ .

Now, add the remainders: $7 + 5 = 12$ .

Finally, find the remainder of this sum: $12 (\mod 10)$ . The remainder is $2$ .

Both methods give the same answer, but the second method kept the numbers smaller and easier to manage.

Where Is Modular Arithmetic Used in Real Life?

Modular arithmetic might seem abstract, but it's one of the most widely applied mathematical concepts. You use it every day without even realizing it.

Telling Time: As we've discussed, 12-hour clocks are a perfect example of arithmetic modulo $12$ . Military and European time uses a 24-hour clock, which is arithmetic modulo $24$ .
Calendars and Dates: The days of the week operate on a 7-day cycle, which is arithmetic modulo $7$ . Months operate on a 12-month cycle, which is arithmetic modulo $12$ . This is how we can predict which day of the week a future date will fall on.
Cryptography: Keeping information secret is a major application. Simple ciphers, like the Caesar cipher, use modular arithmetic to shift letters. For example, to encrypt a message with a shift of $3$ , you replace 'A' with 'D', 'B' with 'E', and so on. When you get to the end of the alphabet, you wrap around: 'X' becomes 'A', 'Y' becomes 'B', etc. This is addition modulo $26$ . Modern, complex encryption systems like RSA also rely heavily on modular arithmetic with very large prime numbers.
Computer Science: Computers use modular arithmetic constantly. In programming, the '%' operator is the 'mod' operator. It's used in hash tables to assign data to specific memory locations, to generate pseudo-random numbers, and in computer graphics to handle cyclical values like angles or coordinates that wrap around a screen.
ISBN and UPC Codes: The check digits on barcodes for books (ISBN) and products (UPC) are calculated using modular arithmetic (typically modulo $10$ or $11$ ). This allows a scanner to detect if it has misread one of the digits, helping to prevent errors.

Example 3

If your birthday is on a Friday this year, what day of the week will it be on next year, assuming it is not a leap year?

Step 1: Identify the modulus.

The days of the week repeat in a cycle of $7$ . Therefore, we will be working modulo $7$ .

Step 2: Assign numbers to the days.

Let's set Sunday= $0$ , Monday= $1$ , Tuesday= $2$ , Wednesday= $3$ , Thursday= $4$ , Friday= $5$ , and Saturday= $6$ .

Step 3: Set up the problem.

A non-leap year has $365$ days. We want to find the effect of adding $365$ days to our starting day, which is Friday ( $5$ ). The calculation is $(5 + 365) (\mod 7)$ .

Step 4: Simplify the large number.

Instead of adding first, let's simplify $365 (\mod 7)$ . We divide $365$ by $7$ :

$365 \div 7 = 52 with a remainder of 1$

This is because $52 \times 7 = 364$ , and $365 - 364 = 1$ . So, $365 \equiv 1 (\mod 7)$ . This means that a full year is just one day longer than a perfect number of weeks.

Step 5: Solve the simplified problem.

We can now substitute $1$ for $365$ in our original problem:

$(5 + 365) (\mod 7) \equiv (5 + 1) (\mod 7)$

$6 (\mod 7)$

The result is $6$ .

Step 6: Interpret the result.

Looking back at our number assignments, a value of $6$ corresponds to Saturday. So, your birthday will be on a Saturday next year.

Key formulas for modular arithmetic by Algebra911.

What Are Common Mistakes to Avoid?

When you're first learning modular arithmetic, there are a few common pitfalls to watch out for. Being aware of them can save you a lot of confusion.

Confusing the Modulus and the Remainder: This is the most basic mistake. In the expression $19 (\mod 5) = 4$ , the modulus is $5$ (the number you are dividing by) and the remainder (the answer) is $4$ . Don't mix them up.
Forgetting the Range of the Remainder: The remainder $r$ in $a (\mod n)$ must always be in the range $0 \leq r < n$ . The remainder can be $0$ , but it can never be equal to or larger than the modulus. For example, $20 (\mod 5)$ is $0$ , not $5$ .
Getting Negative Remainders: While it's true that $- 2 \equiv 8 (\mod 10)$ , the standard answer for a calculation like $- 12 (\mod 10)$ should be a positive number in the required range. Some calculators or programming languages might output $- 2$ . To fix this, just add the modulus to your negative result until it becomes positive. For example, $- 2 + 10 = 8$ . So $- 12 \equiv 8 (\mod 10)$ .
Thinking Division Works Normally: You cannot simply divide in modular arithmetic as you do in regular arithmetic. For example, 4 \times 2 \equiv 8 \equiv 2 \pmod{6}. But you cannot 'divide by $2$ ' and say $4 \equiv 1 (\mod 6)$ , which is false. Division is a more complex operation that requires a concept called the modular multiplicative inverse, which only exists for certain numbers.

Quick Reference Guide

Here is a quick summary of the key terms and properties of modular arithmetic. Keep this handy as a reference while you practice.

Term / Notation	Definition	Example
Modulus	The number you are dividing by in a modular system. It defines the size of the 'cycle'.	In $14 (\mod 5)$ , the modulus is $5$ .
Congruence ( $\equiv$ )	$a \equiv b (\mod n)$ means $a$ and $b$ have the same remainder when divided by $n$ .	$14 \equiv 4 (\mod 5)$ because both have a remainder of $4$ .
Remainder	The integer left over after division. It must satisfy $0 \leq r < n$ , where $n$ is the modulus.	The remainder of $14 \div 5$ is $4$ .
Addition	(A + B) \pmod{n} \equiv (A \pmod{n} + B \pmod{n}) \pmod{n}	(9+8) \pmod{5} \equiv (4+3) \pmod{5} \equiv 7 \pmod{5} \equiv 2 \pmod{5}
Subtraction	(A - B) \pmod{n} \equiv (A \pmod{n} - B \pmod{n}) \pmod{n}	(3-9) \pmod{7} \equiv (3-2) \pmod{7} \equiv 1 \pmod{7}
Multiplication	$(A \times B) (\mod n) \equiv (A (\mod n) \times B (\mod n)) (\mod n)$	$(7 \times 6) (\mod 4) \equiv (3 \times 2) (\mod 4) \equiv 6 (\mod 4) \equiv 2 (\mod 4)$

Frequently Asked Questions

What's the difference between 'mod' as an operator and 'mod' in congruence?

The 'mod' operator (like in $10 (\mod 3)$ ) asks for a specific result: the remainder, which is $1$ . The 'mod' in a congruence statement ( $10 \equiv 4 (\mod 3)$ ) describes a relationship, stating that $10$ and $4$ belong to the same 'remainder class' modulo $3$ .

Is 8 mod 5 the same as 5 mod 8?

No, they are very different. $8 (\mod 5)$ asks for the remainder when $8$ is divided by $5$ , which is $3$ . $5 (\mod 8)$ asks for the remainder when $5$ is divided by $8$ , which is $5$ itself, since $8$ goes into $5$ zero times.

Can the remainder be a negative number?

In formal mathematics, the remainder $r$ must be in the range $0 \leq r < n$ , where $n$ is the modulus. Some programming languages might give a negative result, but you can always find the correct positive equivalent by adding the modulus. For example, if you get $- 2 (\mod 5)$ , the correct answer is $- 2 + 5 = 3$ .

How is modular arithmetic used in computers?

It's used everywhere! Computers use it for cryptography to keep data secure, in hash tables to store data efficiently, and to handle operations involving cyclical data, like clocks or angles in graphics. It's fundamental to computer science.

What does a ≡ b (mod n) actually mean in simple terms?

It means that $a$ and $b$ are 'the same' in a world that only counts up to $n$ . Think of a 12-hour clock (modulo 12). $14$ o'clock and $2$ o'clock are different in a 24-hour world, but they point to the same spot on a 12-hour clock, so $14 \equiv 2 (\mod 12)$ .

Why is it sometimes called 'clock arithmetic'?

Because a clock is the perfect everyday example. When you go past 12 o'clock, the numbers don't keep getting bigger; they wrap around back to 1. This 'wrapping around' is the core idea of modular arithmetic.

Can you divide in modular arithmetic?

Yes, but it's more complicated than regular division. You can't just divide by any number. It involves finding something called a 'modular multiplicative inverse,' which is a bit like finding a reciprocal. It's a more advanced topic usually studied after the basics.