[작성자:] speedpointer

Mathematical Definition of Modulo

In mathematics, the modulo operation (often written as “mod”) finds the remainder after division of one number by another. Mathematically, we can represent it as:

If $a$ and $b$ are integers, with $b \neq 0$, then $a \bmod b$ is the unique integer $r$ such that:

• $a = bq + r$ for some integer $q$
• $0 \leq r < |b|$

This means that in mathematics, the result of a modulo operation is always non-negative, regardless of whether $a$ or $b$ is negative.

Mathematical Examples:

• $7 \bmod 3 = 1$ (since $7 = 3 \cdot 2 + 1$)
• $-7 \bmod 3 = 2$ (since $-7 = 3 \cdot (-3) + 2$)
• $7 \bmod -3 = 1$ (since $7 = (-3) \cdot (-2) + 1$)
• $-7 \bmod -3 = 2$ (since $-7 = (-3) \cdot 3 – 2$)

In modular arithmetic, the result is typically represented as a number between 0 and $|b|-1$.

Programming Language Implementation

In programming languages, the modulo operation (often represented by the % operator) is implemented differently depending on the language. Unlike in mathematics, programming languages may return negative results.

Java, C, and C++:

In these languages, the sign of the remainder matches the sign of the dividend (the number being divided):

-10 % 8 = -2   // Negative dividend, so negative remainder
10 % -8 = 2    // Positive dividend, so positive remainder
-10 % -8 = -2  // Negative dividend, so negative remainder

Python:

Python follows the mathematical definition more closely, where the result always has the same sign as the divisor:

-10 % 8 = 6    // Result is positive because divisor is positive
10 % -8 = -6   // Result is negative because divisor is negative
-10 % -8 = -2  // Result is negative because divisor is negative

JavaScript:

JavaScript behaves similarly to Java:

-10 % 8 = -2   // Negative dividend, so negative remainder
10 % -8 = 2    // Positive dividend, so positive remainder
-10 % -8 = -2  // Negative dividend, so negative remainder

Why the Difference Matters

These differences can lead to bugs when translating algorithms between mathematical notation and programming implementation, or between different programming languages.

For example, if you’re implementing an algorithm that requires non-negative remainders (like many cryptographic algorithms), you might need to adjust the result in languages like Java or C:

// Ensuring a non-negative result in Java
int mod = ((a % b) + b) % b;

Summary of Rules

1. Mathematical definition: $a \bmod b$ always returns a value between $0$ and $|b|-1$
2. Java/C/C++: The sign of a % b matches the sign of a
3. Python: The sign of a % b matches the sign of b

Understanding these differences is crucial when implementing mathematical algorithms in programming languages, especially when negative numbers are involved.

Terminology

English Terms in Mathematics:

• Modulo operation: The operation of finding the remainder
• Modular arithmetic: A system of arithmetic for integers where numbers “wrap around” after reaching a certain value
• Congruence: We say $a$ is congruent to $b$ modulo $n$ if $a \bmod n = b \bmod n$
• Residue class: The set of all integers that give the same remainder when divided by a fixed modulus

English Terms in Programming:

• Modulo operator: The % symbol used to calculate the remainder
• Remainder operator: Another name for the modulo operator in some programming contexts
• Integer division: Division that returns an integer by discarding the fractional part
• Truncation: The process of removing the fractional part of a number
• Floor division: Division that rounds down to the nearest integer (often written as // in Python)

Understanding these terms and their specific meanings in different contexts will help avoid confusion when discussing modular operations across mathematics and programming.