Modular Arithmetic, Congruence and Applications for SS 1

Modular Arithmetic

Performance Objectives

By the end of the lesson, students should be able to:

1. explain the concept of modular arithmetic;
2. perform addition, subtraction and multiplication in modular arithmetic;
3. explain the use of modular arithmetic to real lives;
4. describe the applications of modular arithmetic to algebraic processes.

Concept of Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” after reaching a certain value, called the modulus. It is often called “clock arithmetic” because the most familiar example is the 12-hour clock, where the hours cycle after 12.

Imagine a clock face. If it is 10 o’clock and 5 hours pass, the time will be 3 o’clock, not 15 o’clock. This is because the clock “resets” after 12. In modular arithmetic, we are interested in the remainder when a number is divided by the modulus.

The modulus is the number that determines the cycle length. For a 12-hour clock, the modulus is 12. For days of the week, the modulus is 7.

Congruence Relation

In modular arithmetic, when two numbers have the same remainder after being divided by the same modulus, they are said to be congruent. This relationship is written using the congruence symbol $\equiv$.

The expression $a \equiv b \pmod{m}$ means that $a$ is congruent to $b$ modulo $m$. This implies that $a$ and $b$ have the same remainder when divided by $m$. Alternatively, it means that $m$ divides the difference $(a – b)$ exactly, without any remainder.

For example, $15 \equiv 3 \pmod{12}$ because when 15 is divided by 12, the remainder is 3. Also, $15 – 3 = 12$, and 12 is divisible by 12.

Another example is $25 \equiv 4 \pmod{7}$. When 25 is divided by 7, the remainder is 4. Also, $25 – 4 = 21$, and 21 is divisible by 7.

Operations in Modular Arithmetic

The basic arithmetic operations of addition, subtraction, and multiplication can be performed in modular arithmetic. The key is to always find the remainder after performing the operation and dividing by the modulus.

Addition in Modular Arithmetic

To add two numbers in modular arithmetic, first add the numbers as usual, then divide the sum by the modulus and take the remainder as the result.

The procedure for addition modulo $m$ is:

1. Add the two numbers, say $a$ and $b$.
2. Divide the sum $(a + b)$ by the modulus $m$.
3. The remainder is the result of the addition in modular arithmetic.

Example 1: Calculate $7 + 8 \pmod{10}$.

Solution:

1. Add the numbers: $7 + 8 = 15$.
2. Divide the sum by the modulus: $15 \div 10$.
3. The remainder is 5.

Therefore, $7 + 8 \equiv 5 \pmod{10}$.

Example 2: Calculate $13 + 15 \pmod{7}$.

Solution:

1. Add the numbers: $13 + 15 = 28$.
2. Divide the sum by the modulus: $28 \div 7$.
3. The remainder is 0 (since $28 = 4 \times 7$).

Therefore, $13 + 15 \equiv 0 \pmod{7}$.

Subtraction in Modular Arithmetic

To subtract two numbers in modular arithmetic, first subtract the numbers as usual. If the result is negative, add multiples of the modulus until the result becomes a positive number within the range of 0 to $m-1$.

The procedure for subtraction modulo $m$ is:

1. Subtract the second number from the first number, say $a – b$.
2. If the result $(a – b)$ is negative, add the modulus $m$ to it repeatedly until the result is positive and less than $m$.
3. If the result $(a – b)$ is positive, divide it by $m$ and take the remainder.

Example 3: Calculate $3 – 7 \pmod{10}$.

Solution:

1. Subtract the numbers: $3 – 7 = -4$.
2. Since the result is negative, add the modulus (10) to it: $-4 + 10 = 6$.

Therefore, $3 – 7 \equiv 6 \pmod{10}$.

Example 4: Calculate $20 – 5 \pmod{6}$.

Solution:

1. Subtract the numbers: $20 – 5 = 15$.
2. Divide the result by the modulus: $15 \div 6$.
3. The remainder is 3 (since $15 = 2 \times 6 + 3$).

Therefore, $20 – 5 \equiv 3 \pmod{6}$.

Multiplication in Modular Arithmetic

To multiply two numbers in modular arithmetic, first multiply the numbers as usual, then divide the product by the modulus and take the remainder as the result.

The procedure for multiplication modulo $m$ is:

1. Multiply the two numbers, say $a$ and $b$.
2. Divide the product $(a \times b)$ by the modulus $m$.
3. The remainder is the result of the multiplication in modular arithmetic.

Example 5: Calculate $4 \times 6 \pmod{7}$.

Solution:

1. Multiply the numbers: $4 \times 6 = 24$.
2. Divide the product by the modulus: $24 \div 7$.
3. The remainder is 3 (since $24 = 3 \times 7 + 3$).

Therefore, $4 \times 6 \equiv 3 \pmod{7}$.

Example 6: Calculate $5 \times 9 \pmod{12}$.

Solution:

1. Multiply the numbers: $5 \times 9 = 45$.
2. Divide the product by the modulus: $45 \div 12$.
3. The remainder is 9 (since $45 = 3 \times 12 + 9$).

Therefore, $5 \times 9 \equiv 9 \pmod{12}$.

Constructing Modular Tables

Modular tables can be created for addition, subtraction, or multiplication for a given modulus. These tables show the result of operations for all numbers within the modulus range (usually from 0 or 1 up to $m-1$).

Here is an example of an addition table modulo 5:

To construct such a table, simply perform the operation for each pair of numbers and write down the remainder modulo $m$. For example, in the table above, $3 + 4 = 7$, and $7 \equiv 2 \pmod{5}$. So the cell for $3+4$ contains 2.

Applications of Modular Arithmetic to Daily Life

Modular arithmetic is used in many real-life situations, especially those involving cycles or repeated patterns.

1. Time Calculation:

   The 12-hour clock operates on modulo 12, and the 24-hour clock (military time) operates on modulo 24. Days of the week operate on modulo 7.

   Example 7: If it is 9 AM now, what time will it be in 50 hours?

   Solution:

   1. We are working with a 24-hour cycle for simplicity, so the modulus is 24.
   2. Current time is 9. We need to find $9 + 50 \pmod{24}$.
   3. $9 + 50 = 59$.
   4. $59 \div 24 = 2$ with a remainder of $11$ (since $2 \times 24 = 48$, and $59 – 48 = 11$).

   So, in 50 hours, it will be 11 AM.

2. Days of the Week:

   The days of the week repeat every 7 days. We can assign numbers to the days, for example: Sunday = 0, Monday = 1, Tuesday = 2, Wednesday = 3, Thursday = 4, Friday = 5, Saturday = 6.

   Example 8: If today is Tuesday, what day of the week will it be in 100 days?

   Solution:

   1. Tuesday corresponds to the number 2. The modulus is 7.
   2. We need to find $2 + 100 \pmod{7}$.
   3. $2 + 100 = 102$.
   4. $102 \div 7 = 14$ with a remainder of $4$ (since $14 \times 7 = 98$, and $102 – 98 = 4$).

   The number 4 corresponds to Thursday. So, in 100 days, it will be Thursday.

3. Calendar Calculations:

   Modular arithmetic can be used to determine patterns in dates, such as finding the day of the week for a specific date in the future or past.

4. Computer Science and Cryptography:

   Modular arithmetic is fundamental in computer science, especially in areas like data encryption, error detection codes, and generating random numbers. For instance, in cryptography, messages are often encoded and decoded using modular arithmetic to ensure security.

5. Music:

   Musical notes repeat every 12 semitones (an octave). This is an application of modulo 12. For example, C, C#, D, D#, E, F, F#, G, G#, A, A#, B, then back to C. This cycle of 12 notes is a modular system.

Applications of Modular Arithmetic to Algebraic Processes

Modular arithmetic can be applied to solve algebraic equations where the solutions are restricted to a specific modulus. These are called linear congruences.

A linear congruence is an equation of the form $ax \equiv b \pmod{m}$, where $a$, $b$, and $m$ are integers, and $x$ is the unknown integer we want to find.

To solve a linear congruence, we need to find a value of $x$ (within the range of 0 to $m-1$) that satisfies the congruence.

Example 9: Solve for $x$ in $x + 5 \equiv 2 \pmod{6}$.

Solution:

1. To isolate $x$, subtract 5 from both sides of the congruence:
2. $x \equiv 2 – 5 \pmod{6}$
3. $x \equiv -3 \pmod{6}$
4. Since $-3$ is negative, add the modulus (6) to it until it is positive and less than 6:
5. $x \equiv -3 + 6 \pmod{6}$
6. $x \equiv 3 \pmod{6}$

The solution is $x = 3$. We can check this: $3 + 5 = 8$, and $8 \equiv 2 \pmod{6}$.

Example 10: Solve for $x$ in $3x \equiv 2 \pmod{5}$.

Solution:

We need to find a value for $x$ (from 0, 1, 2, 3, 4) such that when $3x$ is divided by 5, the remainder is 2.

1. Try $x = 0$: $3 \times 0 = 0 \equiv 0 \pmod{5}$ (Not 2)
2. Try $x = 1$: $3 \times 1 = 3 \equiv 3 \pmod{5}$ (Not 2)
3. Try $x = 2$: $3 \times 2 = 6 \equiv 1 \pmod{5}$ (Not 2)
4. Try $x = 3$: $3 \times 3 = 9 \equiv 4 \pmod{5}$ (Not 2)
5. Try $x = 4$: $3 \times 4 = 12 \equiv 2 \pmod{5}$ (This is 2!)

Therefore, the solution is $x = 4$.

Example 11: Find the value of $y$ in $4y – 1 \equiv 7 \pmod{9}$.

Solution:

1. Add 1 to both sides of the congruence:
2. $4y \equiv 7 + 1 \pmod{9}$
3. $4y \equiv 8 \pmod{9}$
4. Now, we need to find a value for $y$ (from 0, 1, 2, …, 8) such that $4y$ leaves a remainder of 8 when divided by 9.
5. Try values for $y$:
1. If $y = 0$, $4 \times 0 = 0 \equiv 0 \pmod{9}$
2. If $y = 1$, $4 \times 1 = 4 \equiv 4 \pmod{9}$
3. If $y = 2$, $4 \times 2 = 8 \equiv 8 \pmod{9}$ (This is 8!)

Therefore, the solution is $y = 2$.