Modulo Arithmetic and Congruence

Modulo Arithmetic: Definition and Operations

Introduction to Modulo Arithmetic: "Clock Arithmetic"

Modulo arithmetic is a system of arithmetic for integers where numbers "wrap around" when they reach a certain value, called the modulus. It is often referred to as "clock arithmetic" because the hours on a clock (with modulus 12 or 24) are a common example.

On a standard 12-hour clock, after reaching 12, the hours cycle back to 1. If it is 9 o'clock and you want to know what time it will be in 5 hours, you calculate $9 + 5 = 14$. On a 12-hour clock, 14 hours is equivalent to 2 o'clock (since 12 hours make a full cycle). In terms of division, 14 divided by 12 gives a quotient of 1 and a remainder of 2. So, 14 hours is 1 full cycle of 12 hours plus 2 more hours. This is written in modulo notation as $14 \equiv 2 \pmod{12}$ (read as "14 is congruent to 2 modulo 12").

At its heart, modulo arithmetic is concerned with the remainder of an integer division. It provides a way to work with integers based on their remainders when divided by a fixed positive integer (the modulus).

Definition of the Modulo Operation ($a \pmod n$)

For any integer $a$ (the dividend, which can be positive, negative, or zero) and a positive integer $n$ (the modulus, $n > 0$), the modulo operation $a \pmod n$ (read as "$a$ modulo $n$") gives the unique remainder $r$ that satisfies the conditions of Euclid's Division Lemma when $a$ is divided by $n$.

According to Euclid's Division Lemma (extended to include any integer $a$ and positive integer $n$), for integers $a$ and $n > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = nq + r$, where $0 \le r < n$. The result of the modulo operation $a \pmod n$ is this unique remainder $r$.

Key characteristics of the result of the modulo operation, $a \pmod n$:

• The result is always an integer.
• The result is always non-negative ($r \ge 0$).
• The result is strictly less than the modulus ($r < n$).
• The result is unique for a given integer $a$ and positive modulus $n$.

Let's look at examples covering different cases of $a$:

• Positive $a$:
  • $17 \pmod 5$: Divide 17 by 5: $17 = 5 \times 3 + 2$. The remainder is 2, and $0 \le 2 < 5$. So, $17 \pmod 5 = 2$.
  • $20 \pmod 4$: Divide 20 by 4: $20 = 4 \times 5 + 0$. The remainder is 0, and $0 \le 0 < 4$. So, $20 \pmod 4 = 0$.
  • $7 \pmod {10}$: Divide 7 by 10: $7 = 10 \times 0 + 7$. The remainder is 7, and $0 \le 7 < 10$. So, $7 \pmod {10} = 7$.
• Zero $a$:
  • $0 \pmod 7$: Divide 0 by 7: $0 = 7 \times 0 + 0$. The remainder is 0, and $0 \le 0 < 7$. So, $0 \pmod 7 = 0$.
• Negative $a$: When $a$ is negative, we must find the quotient $q$ and remainder $r$ such that $a = nq + r$ and $0 \le r < n$. The quotient $q$ will typically be negative or zero.
  • $(-3) \pmod 5$: We need $q, r$ such that $-3 = 5q + r$ and $0 \le r < 5$. If we choose $q=0$, $-3 = 5(0) + (-3)$, $r=-3$ (not in range). If we choose $q=-1$, $-3 = 5(-1) + r \implies -3 = -5 + r \implies r = -3 + 5 = 2$. Remainder is 2, and $0 \le 2 < 5$. So, $(-3) \pmod 5 = 2$.
  • $(-10) \pmod 3$: We need $q, r$ s.t. $-10 = 3q + r$ and $0 \le r < 3$. If $q=-3$, $-10 = 3(-3) + (-1)$, $r=-1$ (not in range). If we choose $q=-4$, $-10 = 3(-4) + r \implies -10 = -12 + r \implies r = -10 + 12 = 2$. Remainder is 2, and $0 \le 2 < 3$. So, $(-10) \pmod 3 = 2$.
  • $(-18) \pmod 6$: We need $q, r$ s.t. $-18 = 6q + r$ and $0 \le r < 6$. If we choose $q=-3$, $-18 = 6(-3) + 0$. Remainder is 0, and $0 \le 0 < 6$. So, $(-18) \pmod 6 = 0$.

The modulo operation is the basis for the concept of congruence modulo $n$, which is discussed in the next section.

Arithmetic Operations in Modulo n

Arithmetic operations (addition, subtraction, multiplication) can be performed within modulo arithmetic. When we perform an operation modulo $n$, we are interested in the remainder of the result of the standard integer operation when divided by $n$. A key property of modulo arithmetic is that we can obtain the same result by performing the standard operation on the individual integers and then taking the result modulo $n$, or by first taking the modulo of the individual integers, performing the operation on the remainders, and then taking the modulo of that intermediate result.

Let $a$ and $b$ be any integers, and $n$ be a positive integer (the modulus). The operations modulo $n$ are defined as follows:

1. Addition Modulo n

The sum of $a$ and $b$ modulo $n$, denoted as $(a + b) \pmod n$, is the remainder when the ordinary integer sum $(a+b)$ is divided by $n$. A useful property for calculation is:

This property means you can find the remainders first, add them, and then find the remainder of that sum when divided by $n$.

Answer:

2. Subtraction Modulo n

The difference of $a$ and $b$ modulo $n$, denoted as $(a - b) \pmod n$, is the remainder when the ordinary integer difference $(a-b)$ is divided by $n$. The property for calculation is:

Answer:

3. Multiplication Modulo n

The product of $a$ and $b$ modulo $n$, denoted as $(a \times b) \pmod n$, is the remainder when the ordinary integer product $(a \times b)$ is divided by $n$. The property for calculation is:

Answer:

These properties show that the set of possible remainders modulo $n$, which is $\{0, 1, \ldots, n-1\}$, forms a closed system under addition, subtraction, and multiplication defined in this modular way. Modulo arithmetic is a key concept in number theory, abstract algebra, cryptography, computer science, and various real-world applications like scheduling and digital clocks.

Congruence Modulo: Definition and Properties

Defining Congruence Modulo n ($\equiv$)

The concept of congruence modulo $n$ is a central idea in number theory, formalized by Carl Friedrich Gauss. It provides an alternative perspective on modulo arithmetic, focusing on the relationship between integers that share the same remainder when divided by a fixed positive integer $n$, called the modulus.

Two integers $a$ and $b$ are said to be congruent modulo $n$ if they leave the same remainder when divided by the positive integer $n$. This relationship is denoted using the congruence symbol $\equiv$ and is written as:

where $n$ is the positive integer modulus ($n > 0$).

An equivalent definition of congruence modulo $n$, and one that is often more useful for proving properties, is that $a \equiv b \pmod n$ if and only if the difference between $a$ and $b$, i.e., $(a - b)$, is divisible by $n$.

This divisibility statement means that $a - b = nk$ for some integer $k$. Rearranging this equation gives $a = b + nk$, which shows that $a$ and $b$ differ by an exact multiple of $n$. This explains why they would leave the same remainder when divided by $n$: $a = nq_a + r$ and $b = nq_b + r$, so $a-b = n(q_a - q_b)$, which is a multiple of $n$.

Examples:

• $17 \equiv 2 \pmod 5$: When 17 is divided by 5, the remainder is 2. When 2 is divided by 5, the remainder is 2. Same remainders. Also, $17 - 2 = 15$, and 15 is divisible by 5 ($15 = 5 \times 3$).
• $20 \equiv 2 \pmod 6$: $20 = 6 \times 3 + 2$, $2 = 6 \times 0 + 2$. Same remainders (2). Also, $20 - 2 = 18$, and 18 is divisible by 6 ($18 = 6 \times 3$).
• $18 \equiv 0 \pmod 3$: $18 = 3 \times 6 + 0$, $0 = 3 \times 0 + 0$. Same remainders (0). Also, $18 - 0 = 18$, and 18 is divisible by 3 ($18 = 3 \times 6$).
• $(-3) \equiv 2 \pmod 5$: $-3 = 5 \times (-1) + 2$, $2 = 5 \times 0 + 2$. Same remainders (2). Also, $(-3) - 2 = -5$, and -5 is divisible by 5 ($-5 = 5 \times (-1)$).
• $10 \equiv -5 \pmod 5$: $10 = 5 \times 2 + 0$, $-5 = 5 \times (-1) + 0$. Same remainders (0). Also, $10 - (-5) = 10 + 5 = 15$, and 15 is divisible by 5 ($15 = 5 \times 3$).
• $1 \equiv 13 \pmod {12}$: $1 = 12 \times 0 + 1$, $13 = 12 \times 1 + 1$. Same remainders (1). Also, $1 - 13 = -12$, and -12 is divisible by 12 ($-12 = 12 \times (-1)$).

Congruence modulo $n$ partitions the set of integers into $n$ disjoint sets, where each set contains all integers that leave the same remainder when divided by $n$. These sets are called congruence classes or residue classes modulo $n$. The congruence class of an integer $a$ modulo $n$, denoted by $[a]_n$ or $\overline{a}$, is the set of all integers $x$ such that $x \equiv a \pmod n$. There are exactly $n$ distinct congruence classes modulo $n$, corresponding to the $n$ possible remainders $\{0, 1, \ldots, n-1\}$.

Example: Congruence classes modulo 4 ($n=4$):

• $[0]_4 = \{ \ldots, -8, -4, 0, 4, 8, \ldots \}$ (all integers divisible by 4)
• $[1]_4 = \{ \ldots, -7, -3, 1, 5, 9, \ldots \}$ (all integers leaving remainder 1 when divided by 4)
• $[2]_4 = \{ \ldots, -6, -2, 2, 6, 10, \ldots \}$ (all integers leaving remainder 2 when divided by 4)
• $[3]_4 = \{ \ldots, -5, -1, 3, 7, 11, \ldots \}$ (all integers leaving remainder 3 when divided by 4)

Every integer belongs to exactly one of these congruence classes modulo 4.

Properties of Congruence Modulo n

Congruence modulo $n$ is an equivalence relation on the set of integers. This is a strong property that means it satisfies reflexivity, symmetry, and transitivity. Furthermore, it is compatible with the basic arithmetic operations.

Let $a, b, c$ be integers and $n$ be a positive integer ($n > 0$).

1. Reflexive Property: $a \equiv a \pmod n$ for any integer $a$.

   Explanation: Check the equivalent definition: Is $(a - a)$ divisible by $n$? $a - a = 0$, and $0$ is divisible by any non-zero integer $n$ (since $0 = n \times 0$). Thus, $a \equiv a \pmod n$.

2. Symmetric Property: If $a \equiv b \pmod n$, then $b \equiv a \pmod n$.

   Explanation: Given $a \equiv b \pmod n$. By the equivalent definition, $a - b$ is divisible by $n$. This means $a - b = nk$ for some integer $k$. Multiply both sides by -1: $-(a - b) = -nk$, which simplifies to $b - a = n(-k)$. Since $k$ is an integer, $-k$ is also an integer. Thus, $b - a$ is divisible by $n$. By the equivalent definition, this means $b \equiv a \pmod n$.

3. Transitive Property: If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a \equiv c \pmod n$.

   Explanation: Given $a \equiv b \pmod n$ and $b \equiv c \pmod n$.

   By the equivalent definition:

   $\quad a - b = nk_1$ for some integer $k_1$.

   [From $a \equiv b \pmod n$]

   $\quad b - c = nk_2$ for some integer $k_2$.

   [From $b \equiv c \pmod n$]

   Add the two equations:

   $\quad (a - b) + (b - c) = nk_1 + nk_2$

   Simplify the left side and factor $n$ from the right side:

   $\quad a - c = n(k_1 + k_2)$

   Since $k_1$ and $k_2$ are integers, their sum $k_1 + k_2$ is also an integer (closure under addition for integers). Thus, $a - c$ is divisible by $n$. By the equivalent definition, this means $a \equiv c \pmod n$.

These three properties together establish that congruence modulo $n$ is an equivalence relation, meaning it formally partitions the set of integers into distinct congruence classes.

Properties of Congruence with Arithmetic Operations

The congruence relation is highly compatible with the basic arithmetic operations (addition, subtraction, and multiplication). If numbers are congruent modulo $n$, performing the same arithmetic operation on them maintains the congruence relationship modulo $n$.

Let $a, b, c, d$ be integers and $n$ be a positive integer ($n > 0$). If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then:

4. Addition Property: $a + c \equiv b + d \pmod n$. (If two numbers are congruent to two other numbers, their sum is congruent to the sum of the others, all modulo $n$).

   Example: $10 \equiv 3 \pmod 7$ and $15 \equiv 1 \pmod 7$. Add the left sides and right sides: $10+15 = 25$, $3+1 = 4$. Is $25 \equiv 4 \pmod 7$? Check the difference: $25 - 4 = 21$. 21 is divisible by 7 ($21 = 7 \times 3$). So $25 \equiv 4 \pmod 7$. The property holds.

5. Subtraction Property: $a - c \equiv b - d \pmod n$. (If two numbers are congruent to two other numbers, their difference is congruent to the difference of the others, all modulo $n$).

   Example: $10 \equiv 3 \pmod 7$ and $15 \equiv 1 \pmod 7$. Subtract the left sides and right sides: $10-15 = -5$, $3-1 = 2$. Is $-5 \equiv 2 \pmod 7$? Check the difference: $(-5) - 2 = -7$. -7 is divisible by 7 ($-7 = 7 \times (-1)$). So $-5 \equiv 2 \pmod 7$. The property holds.

6. Multiplication Property: $a \times c \equiv b \times d \pmod n$. (If two numbers are congruent to two other numbers, their product is congruent to the product of the others, all modulo $n$).

   Example: $10 \equiv 3 \pmod 7$ and $15 \equiv 1 \pmod 7$. Multiply the left sides and right sides: $10 \times 15 = 150$, $3 \times 1 = 3$. Is $150 \equiv 3 \pmod 7$? Check the difference: $150 - 3 = 147$. $147$ is divisible by 7 ($147 = 7 \times 21$). So $150 \equiv 3 \pmod 7$. The property holds.

7. Exponentiation Property: If $a \equiv b \pmod n$, then $a^k \equiv b^k \pmod n$ for any non-negative integer $k$. (Raising congruent numbers to the same non-negative integer power preserves congruence).

   Explanation: This property can be proven by repeatedly applying the multiplication property. If $a \equiv b \pmod n$, then $a \times a \equiv b \times b \pmod n$, so $a^2 \equiv b^2 \pmod n$. Repeating this $k$ times gives $a^k \equiv b^k \pmod n$. For $k=0$, $a^0=1, b^0=1$ (if $a, b \neq 0$), $1 \equiv 1 \pmod n$. If $a$ or $b$ is 0, the definition needs care, but the property still holds.

   Example: $2 \equiv 5 \pmod 3$ (since $2-5=-3$, divisible by 3). Let $k=3$. $2^3 = 8$. $5^3 = 125$. Is $8 \equiv 125 \pmod 3$? Check the difference: $8 - 125 = -117$. $-117$ is divisible by 3 (sum of digits $1+1+7=9$, divisible by 3; $-117 = 3 \times (-39)$). So $8 \equiv 125 \pmod 3$. The property holds.

These properties are extremely useful for simplifying calculations involving large numbers, particularly when only the remainder is important (e.g., finding the last digit of a large power, which is equivalent to calculating modulo 10). For example, to find the last digit of $2^{50}$, we need to calculate $2^{50} \pmod{10}$.

Answer:

Modulo arithmetic and congruence modulo $n$ are fundamental concepts that provide a powerful framework for analyzing integers based on their remainders and simplifying calculations involving cyclical patterns.