Here are the one-sentence summaries for each major topic in this study guide.

Intro to Modular Arithmetic

Modular arithmetic is a system of "clock math" where numbers wrap around after reaching a certain value called the modulus, focusing on remainders from division.

Modulo in C++

C++ uses the % operator to find the remainder of integer division, which is essential for tasks like managing data in circular arrays and other algorithms.

Modular Addition

Adding numbers in a modular system involves adding them normally and then taking the remainder, a key technique for preventing integer overflow in programs.

Modular Subtraction

Modular subtraction requires a special adjustment by adding the modulus to handle potential negative results and keep numbers within the desired positive range (0 to n-1).

Modular Multiplication

Multiplying numbers in a modular system involves multiplying first and then taking the remainder, which prevents the product from exceeding data type limits in code.

Applications in CS

Modular arithmetic is fundamental in computer science for creating efficient hash tables, basic cryptography like Caesar ciphers, and managing circular data structures.

Intro to Modular Arithmetic

1. Clock Analogy: The easiest way to visualize modular arithmetic is a 12-hour clock; 4 hours past 10 o'clock is 2 o'clock, not 14.
2. Core Idea: It is a system of arithmetic for integers that focuses only on the remainder after division by a fixed integer (the modulus).
3. Formal Definition: $a \pmod{n}$ is the remainder when $a$ (the dividend) is divided by $n$ (the divisor or modulus).
4. Congruence: Two integers $a$ and $b$ are congruent modulo $n$ if they have the same remainder when divided by $n$. This is written as $a \equiv b \pmod{n}$.
5. Remainder Range: The result of $a \pmod{n}$ is always an integer in the range $[0, n-1]$.

Modulo in C++

1. Syntax: The modulo operator in C++ is the percent sign (%). The expression a % n calculates the remainder.
2. Integer Division vs. Modulo: In C++, / with integers performs integer division (discards the remainder), while % returns only the remainder.
3. Circular Indexing: Use index % array_size to wrap an index around in a circular array, ensuring it stays within bounds.
4. Division by Zero: a % 0 is undefined and will cause a runtime error (crash) in C++. Always check if the divisor is non-zero.
5. Positive Integers: For positive integers a and n, a % n in C++ behaves exactly as expected in standard mathematics.

Modular Addition

1. The Property: $(a + b) \% n = ((a \% n) + (b \% n)) \% n$. This is the fundamental rule for modular addition.
2. Preventing Overflow: Applying the modulo at each step of a sum keeps intermediate results small, preventing them from exceeding the maximum value of a data type like int.
3. Step-by-Step Reduction: For long sums, it's better to calculate (a % n + b % n) % n rather than (a + b) % n to avoid overflow.
4. Associativity: Modular addition is associative: $((a+b)\%n + c)\%n = (a + (b+c)\%n)\%n$. This allows for chaining operations.
5. Identity Element: The identity element for modular addition is 0, since $(a + 0) \% n = a \% n$.

Modular Subtraction

1. The Property: $(a - b) \% n = ((a \% n) - (b \% n) + n) \% n$. The + n is crucial for handling negative results.
2. C++ Negative Results: The expression a % n in C++ can return a negative result if a is negative. For example, -5 % 3 is often -2.
3. Normalization: To ensure the result is always in the range $[0, n-1]$, use the + n trick: (result % n + n) % n.
4. Clock Analogy (Reverse): Subtraction is like moving backward on a clock. 2 o'clock minus 4 hours is 10 o'clock, not -2 o'clock. (2 - 4 + 12) % 12 = 10.
5. Safe Subtraction Function: A robust C++ function for modular subtraction always includes the normalization step to avoid bugs with negative intermediate values.

Modular Multiplication

1. The Property: $(a * b) \% n = ((a \% n) * (b \% n)) \% n$. This rule mirrors the one for modular addition.
2. Overflow Risk: Multiplication causes numbers to grow much faster than addition, making overflow a significant risk with standard integer types.
3. Intermediate Modulo: To multiply large numbers, always apply the modulo after each multiplication step to keep the product manageable.
4. Data Types: When multiplying, intermediate products like (a % n) * (b % n) might still overflow. Use a larger data type (like long long in C++) for the temporary calculation.
5. Modular Factorials: This property is essential for calculating constructs like $k! \pmod{n}$ without computing the full, enormous value of $k!$.

Applications in CS

1. Hash Tables: The modulo operator is used to map a key's large hash code to a smaller index in an array, e.g., index = hash(key) % table_size.
2. Cryptography: Simple ciphers like the Caesar Cipher use modular addition to shift letters. encrypted_char = (original_char + shift) % 26.
3. Circular Buffers/Queues: The modulo operator helps manage the read and write pointers in a circular buffer, allowing them to wrap around to the start of the array.
4. Random Number Generation: Linear Congruential Generators (a basic type of PRNG) use modular arithmetic to produce a sequence of pseudo-random numbers.
5. Competitive Programming: Modular arithmetic is critical for solving problems with large numbers where you only need to output the answer modulo a specific value (often $10^9 + 7$).

Topic: Modular Addition

Topic: Modular Subtraction

Topic: Modular Multiplication

❌ MISTAKE: Forgetting to handle negative results in subtraction.

• Why it happens: In C++, (-5 % 12) might be -5, not 7. Directly using this result in further calculations can lead to incorrect answers or array out-of-bounds errors.
• ✅ Instead: Always normalize negative results. Use the formula (result % n + n) % n to guarantee the result is in the range [0, n-1].
• Topic: Modular Subtraction

❌ MISTAKE: Allowing intermediate overflow in multiplication.

• Why it happens: Calculating (a * b) % n seems simple, but if a and b are large, the intermediate product a * b might overflow before the modulo is applied.
• ✅ Instead: Apply the modulo at each step: ((a % n) * (b % n)) % n. Also, cast to a larger data type (e.g., long long in C++) for the intermediate multiplication to be safe: (1LL * (a % n) * (b % n)) % n.
• Topic: Modular Multiplication

❌ MISTAKE: Using modulo with floating-point numbers.

• Why it happens: The % operator in C++ is only defined for integer types. Trying to use it with float or double will cause a compilation error.
• ✅ Instead: If you need to perform a similar operation on floating-point numbers, use the fmod() function from the <cmath> library, e.g., fmod(7.5, 2.2).
• Topic: Modulo in C++

❌ MISTAKE: Assuming a / n and a % n are unrelated.

• Why it happens: Students often learn the two operators separately and forget their direct mathematical relationship from the Division Algorithm.
• ✅ Instead: Remember that they are two parts of the same whole: a == (a / n) * n + (a % n). The original number can always be reconstructed from its integer quotient and remainder.
• Topic: Modulo in C++

❌ MISTAKE: Dividing by zero.

• Why it happens: In applications like hash tables, the size of the table might be dynamic or come from user input, which could potentially be zero.
• ✅ Instead: Always add a check to ensure the modulus is not zero before performing a % operation to prevent a runtime crash.
• Topic: Modulo in C++

Example: Circular Array Indexing

Problem: You have an array of 7 elements (indices 0-6). If you are at index 5 and you move forward 4 spots, what is your new index?

Solution:

Step 1: Identify the components.

• Reasoning: We need the current position, the movement, and the size of the array (the modulus).
• Work: Current index a = 5. Movement b = 4. Array size n = 7.

Step 2: Apply the modular addition formula.

• Reasoning: We are moving forward, so we use addition. The result must wrap around, so we use the modulo operator.
• Work: new_index = (a + b) % n = (5 + 4) % 7

Step 3: Calculate the result.

• Reasoning: Perform the standard arithmetic operations.
• Work: 9 % 7 = 2

Answer: The new index is 2.

⚠️ Common pitfall: Simply adding 5 + 4 = 9 and forgetting that index 9 is out of bounds for an array of size 7. The modulo operator is essential for wrapping the index correctly.

Topic: Modulo in C++

Example: Safe Modular Subtraction

Problem: Using a modulus of 12, calculate (3 - 8) % 12 in a way that guarantees a positive result.

Solution:

Step 1: Perform the initial subtraction.

• Reasoning: The first part of the operation is the standard subtraction.
• Work: 3 - 8 = -5

Step 2: Apply the safe modular subtraction formula.

• Reasoning: The result is negative. A direct % in C++ might give -5. We must use the + n trick to normalize it.
• Work: result = (-5 % 12 + 12) % 12

Step 3: Calculate the intermediate and final results.

• Reasoning: Evaluate the expression step-by-step.
• Work: (-5 + 12) % 12 = 7 % 12 = 7

Answer: The result is 7.

⚠️ Common pitfall: Calculating (3 - 8) % 12 directly and getting -5, then using this incorrect negative result in subsequent calculations. Always normalize to the [0, n-1] range.

Topic: Modular Subtraction

Example: Preventing Overflow in Multiplication

Problem: Calculate $(1,000,000,006 \times 1,000,000,008) \pmod{1,000,000,007}$. Let $n = 1,000,000,007$.

Solution:

Step 1: Recognize the overflow risk.

• Reasoning: Multiplying two large numbers like these will exceed the capacity of a standard 32-bit int and likely even a 64-bit long long.
• Work: We must use the modular multiplication property: (a * b) % n = ((a % n) * (b % n)) % n.

Step 2: Reduce each number modulo n first.

• Reasoning: We can simplify the numbers before multiplying. Notice that $1,000,000,006$ is $n-1$ and $1,000,000,008$ is $n+1$.
• Work:
  • $a \% n = 1,000,000,006 \% 1,000,000,007 = -1 \equiv n-1$
  • $b \% n = 1,000,000,008 \% 1,000,000,007 = 1$

Step 3: Multiply the reduced numbers and take the final modulo.

• Reasoning: Now we are multiplying small numbers, which avoids overflow.
• Work: ( (n-1) * 1 ) % n = (1,000,000,006 * 1) % 1,000,000,007 = 1,000,000,006

Answer: The result is 1,000,000,006.

⚠️ Common pitfall: Trying to compute 1000000006 * 1000000008 directly in code, causing an immediate overflow and yielding a completely wrong answer.

Topic: Modular Multiplication