Congruence & Residue Classes Modular arithmetic formalizes remainders using congruence a ≡ b (mod n), partitioning integers into distinct sets called residue classes, forming the basis for operations within a modulus.

Modular Operations & Overflow Addition, subtraction, and multiplication can be performed under a modulus at each step to manage large numbers and prevent integer overflow, a crucial technique in programming.

Modular Division & Inverses Division in modular arithmetic requires finding a modular multiplicative inverse, which exists only when a number and the modulus are coprime and is often found using an algorithm.

Binary Exponentiation This powerful technique, also known as exponentiation by squaring, efficiently calculates (a^b) % m in logarithmic time, avoiding overflow and time limits with large exponents.

Fermat's Little Theorem (FLT) FLT provides a shortcut for finding the modular inverse of a number when the modulus is prime, by calculating a^(p-2) (mod p), simplifying division problems significantly.

Chinese Remainder Theorem (CRT) CRT solves systems of simultaneous congruences with different, pairwise coprime moduli, enabling the reconstruction of a number from its remainders.

Congruence & Residue Classes

1. Congruence Definition: a ≡ b (mod n) means n divides (a - b). It's a statement about remainders.
2. Equivalence Relation: Congruence is reflexive (a ≡ a), symmetric (a ≡ b implies b ≡ a), and transitive (a ≡ b and b ≡ c implies a ≡ c).
3. Residue Classes: The modulus n partitions all integers into n sets, [0], [1], ..., [n-1], based on their remainder when divided by n.
4. Canonical Representative: We typically use the smallest non-negative integer in a residue class (e.g., 2 for the class [..., -3, 2, 7, ...] (mod 5)).
5. Negative Numbers: Mathematically, -8 mod 5 ≡ 2. In C++, -8 % 5 is -3. To correct this, use (a % n + n) % n.

Modular Operations & Overflow

1. Addition: (a + b) % m = ((a % m) + (b % m)) % m.
2. Subtraction: (a - b) % m = ((a % m) - (b % m) + m) % m. The + m prevents negative results.
3. Multiplication: (a * b) % m = ((a % m) * (b % m)) % m.
4. Intermediate Modulo: Applying % m after each step prevents intermediate values from exceeding long long limits in C++.
5. Time Complexity: Basic modular operations (add, subtract, multiply) are constant time, O(1).

Modular Division & Inverses

1. Division by a: Dividing by a is equivalent to multiplying by its modular inverse, a⁻¹.
2. Inverse Existence: The modular multiplicative inverse a⁻¹ (mod m) exists if and only if gcd(a, m) = 1 (i.e., a and m are coprime).
3. Extended Euclidean Algorithm: This algorithm finds integers x and y such that ax + my = gcd(a, m). If gcd(a, m) = 1, then x is the modular inverse of a modulo m.
4. Complexity: The Extended Euclidean Algorithm runs in O(log(min(a, m))) time.
5. Implementation: The inverse x returned by the algorithm might be negative, so it must be adjusted to (x % m + m) % m.

Binary Exponentiation

1. Purpose: To compute (a^b) % m efficiently, especially for large b.
2. Core Idea: It uses the binary representation of b. If the i-th bit of b is 1, the term a^(2^i) is multiplied into the result.
3. Time Complexity: The algorithm runs in O(log b) time because it processes one bit of the exponent b per iteration.
4. Implementation: It can be implemented iteratively (safer and often faster) or recursively.
5. Overflow Prevention: All intermediate multiplications are performed under the modulus m to prevent overflow.

Fermat's Little Theorem (FLT)

1. Statement: If p is a prime number, then for any integer a not divisible by p, we have a^(p-1) ≡ 1 (mod p).
2. Modular Inverse: A direct corollary is a^(p-2) ≡ a⁻¹ (mod p). This is the primary use of FLT in competitive programming.
3. Condition: FLT only applies when the modulus p is a prime number.
4. Application: To compute (x / a) % p, we can calculate (x * a^(p-2)) % p using binary exponentiation for the a^(p-2) part.
5. Euler's Totient Theorem: A generalization of FLT for a composite modulus m: a^φ(m) ≡ 1 (mod m) for a coprime to m.

Chinese Remainder Theorem (CRT)

1. Purpose: Solves a system of simultaneous linear congruences, like x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), ...
2. Condition: The moduli m₁, m₂, ... must be pairwise coprime (i.e., gcd(mᵢ, mⱼ) = 1 for i ≠ j).
3. Unique Solution: The system has a unique solution modulo M = m₁ * m₂ * ... * mₖ.
4. Constructive Method: It finds the solution by iteratively combining congruences. For two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂), the solution is x = r₁ + k * m₁ where k is found by solving r₁ + k * m₁ ≡ r₂ (mod m₂). This requires a modular inverse.
5. Application: Useful for problems where calculations are needed modulo a very large number that can be factored into smaller, pairwise coprime numbers.

Congruence Relation: A relationship between two integers, a and b, indicating they have the same remainder when divided by a positive integer n, written as a ≡ b (mod n).

• Used in context: Since 17 - 2 = 15, which is divisible by 5, we can state the congruence relation 17 ≡ 2 (mod 5).
• Topic: Congruence & Residue Classes

Modulus: The integer n in the expression a ≡ b (mod n), which serves as the divisor.

• Used in context: In competitive programming, a common modulus is 10^9 + 7 because it's a large prime number.
• Topic: Congruence & Residue Classes

Residue Class: A set of all integers that have the same remainder upon division by a given modulus n.

• Used in context: The residue class of 2 modulo 5 is {..., -8, -3, 2, 7, 12, ...}.
• Topic: Congruence & Residue Classes

Modular Multiplicative Inverse (MMI): For an integer a, its inverse a⁻¹ is an integer such that (a * a⁻¹) ≡ 1 (mod m).

• Used in context: To divide by 3 modulo 7, we multiply by its inverse, 5, because (3 * 5) = 15 ≡ 1 (mod 7).
• Topic: Modular Division & Inverses

Coprime: Two integers are coprime (or relatively prime) if their greatest common divisor (GCD) is 1.

• Used in context: A modular inverse for a modulo m exists only if a and m are coprime.
• Topic: Modular Division & Inverses

Binary Exponentiation: An algorithm for computing a^b % m in O(log b) time, essential for calculations involving large exponents.

• Used in context: We used binary exponentiation to calculate 3^1000 (mod 101) without causing an overflow.
• Topic: Binary Exponentiation

System of Congruences: A set of two or more congruence relations with a single variable that must be solved simultaneously.

• Used in context: We need to find an x that satisfies both x ≡ 2 (mod 3) and x ≡ 3 (mod 5), which is a system of congruences.
• Topic: Chinese Remainder Theorem (CRT)

Mathematical Modulo vs. C++ Remainder Operator (%)

Memory trick: C++ % is a remainder operator; it cares about the division a = qn + r. Math mod is a congruence operator; it cares about the residue class [a].

Topic: Congruence & Residue Classes

Fermat's Little Theorem vs. Extended Euclidean Algorithm

Memory trick: Fermat is for Fast prime moduli. Euclidean is for Everything else (and for finding GCD).

Topic: Modular Division & Inverses

❌ MISTAKE: Forgetting to take the modulus after each multiplication, causing overflow.

• Why it happens: In a long chain of multiplications like (a*b*c*d) % m, students might try to compute a*b*c*d first, which can easily exceed the long long limit.
• ✅ Instead: Apply the modulus at each step: res = (a % m); res = (res * b) % m; res = (res * c) % m; ...
• Topic: Modular Operations & Overflow

❌ MISTAKE: Getting a negative result from subtraction and using it directly.

• Why it happens: Calculating (5 - 10) % 12 might give -5. In modular arithmetic, results must be in the range [0, m-1].
• ✅ Instead: Use the safe subtraction formula: (a - b) % m = ((a % m) - (b % m) + m) % m. For example, (5 - 10 + 12) % 12 = 7.
• Topic: Modular Operations & Overflow

❌ MISTAKE: Trying to find a modular inverse when gcd(a, m) != 1.

• Why it happens: Forgetting that the inverse only exists if the number and modulus are coprime. For example, 2⁻¹ (mod 4) does not exist because gcd(2, 4) = 2.
• ✅ Instead: Always check if gcd(a, m) == 1 before attempting to find the inverse. If not, division by a is undefined for that modulus.
• Topic: Modular Division & Inverses

❌ MISTAKE: Using Fermat's Little Theorem when the modulus is not a prime number.

• Why it happens: Misremembering the conditions for FLT. Applying it to mod 10 (composite) would give an incorrect inverse.
• ✅ Instead: Check if the modulus is prime. If it's prime, use FLT. If it's composite, you must use the Extended Euclidean Algorithm (or Euler's Totient Theorem).
• Topic: Fermat's Little Theorem (FLT)

Binary Exponentiation (Iterative)

Calculates (base^exp) % mod.

Step 1: Initialization

• What happens: Initialize result = 1. The loop will multiply into this value.
• Key indicator: result starts at the multiplicative identity.

Step 2: Reduce Base

• What happens: Update base = base % mod. This ensures the base is within the desired range from the start.
• Key indicator: Initial base value is handled.

Step 3: Loop while exp > 0

• What happens: Iterate through the bits of the exponent exp.
• Key indicator: A while loop that continues as long as exp has bits left to process.

Step 4: Check the Last Bit

• What happens: If the last bit of exp is 1 (i.e., exp % 2 == 1), multiply the current base into the result.
• Key indicator: if (exp & 1) or if (exp % 2).
• Common error: Forgetting to take the modulus after multiplication: result = (result * base) % mod.

Step 5: Square the Base

• What happens: Square the base and take the modulus: base = (base * base) % mod. This prepares the base for the next bit position (e.g., from a^1 to a^2, a^2 to a^4, etc.).
• Key indicator: base is squared in each iteration.
• Common error: Squaring a large base can cause overflow if you don't use long long and take the modulus.

Step 6: Halve the Exponent

• What happens: Right-shift the exponent by one (exp = exp / 2 or exp >>= 1). This effectively moves to the next bit.
• Key indicator: exp is halved.

Visual flow: Initialize res=1 → Loop (exp > 0) → If exp is odd, res = (res*base)%mod → base = (base*base)%mod → exp = exp/2 → Return res

Topic: Binary Exponentiation

Extended Euclidean Algorithm

Finds x, y and g such that ax + by = g where g = gcd(a, b).

Step 1: Base Case

• What happens: If b is 0, then gcd(a, 0) = a. The equation is a*x + 0*y = a, so we can choose x=1 and y=0.
• Key indicator: The recursive function stops when the second parameter is zero.

Step 2: Recursive Call

• What happens: Make a recursive call with gcd(b, a % b). This is the standard Euclidean algorithm step. The call will return x₁, y₁ such that b*x₁ + (a % b)*y₁ = g.
• Key indicator: extendedGcd(b, a % b).

Step 3: Update Coefficients

• What happens: We know a % b = a - floor(a/b) * b. Substitute this into the equation from the recursive call: b*x₁ + (a - floor(a/b)*b)*y₁ = g.
• Key indicator: Algebraic manipulation after the recursive call returns.

Step 4: Determine x and y for the current step

• What happens: Rearrange the equation to match the form a*x + b*y = g. We get a*y₁ + b*(x₁ - floor(a/b)*y₁) = g. So, the current x is y₁ and the current y is x₁ - floor(a/b)*y₁.
• Key indicator: x = y_prev, y = x_prev - (a/b) * y_prev.

Visual flow: Call gcd(a,b) → Base case b=0? (Return a,1,0) → No → Recurse gcd(b, a%b) → Get back g, x₁, y₁ → Set x = y₁, y = x₁ - (a/b)y₁ → Return g, x, y

Topic: Modular Division & Inverses

• When to use: To formally reason about remainders and the structure of integers.
• Example: 14 ≡ 4 (mod 10) because 14 - 4 = 10, which is divisible by 10.
• Common error: Confusing a mod n = r (an operation returning a value) with a ≡ r (mod n) (a statement of relation).

Topic: Congruence & Residue Classes

Fermat's Little Theorem (for Modular Inverse)

• When to use: For modular division (x / a) % p when p is prime. You calculate (x * a^(p-2)) % p.
• Example: Find 3⁻¹ (mod 7). Here a=3, p=7. We calculate 3^(7-2) mod 7 = 3^5 mod 7. 3^5 = 243. 243 % 7 = 5. So, 3⁻¹ ≡ 5 (mod 7).
• Common error: Applying this formula when the modulus is not prime.

Topic: Fermat's Little Theorem (FLT)

Example: Calculating a large power

Problem: Calculate $13^{11} \pmod{101}$.

Solution:

Step 1: Use Binary Exponentiation.

• Reasoning: The exponent 11 is too large for direct calculation without potential overflow and is inefficient. Binary exponentiation is O(log b).
• Work: First, write the exponent 11 in binary: $11_{10} = 1011_2$. This means $11 = 8 + 2 + 1$.

Step 2: Decompose the power.

• Reasoning: Based on the binary representation, we can write $13^{11}$ as $13^8 * 13^2 * 13^1$.
• Work: We will calculate the powers of 13 by repeated squaring, modulo 101.
  • $13^1 \equiv 13 \pmod{101}$
  • $13^2 \equiv 169 \equiv 68 \pmod{101}$
  • $13^4 \equiv 68^2 \equiv 4624 \equiv 79 \pmod{101}$
  • $13^8 \equiv 79^2 \equiv 6241 \equiv 80 \pmod{101}$

Step 3: Combine the required terms.

• Reasoning: Multiply the terms corresponding to the '1' bits in the binary representation of the exponent (1, 2, 8).
• Work: $13^{11} \equiv 13^8 \cdot 13^2 \cdot 13^1 \pmod{101}$ $\equiv (80 \cdot 68) \cdot 13 \pmod{101}$ $\equiv (5440) \cdot 13 \pmod{101}$ $\equiv (87) \cdot 13 \pmod{101}$ $\equiv 1131 \pmod{101}$ $\equiv 20 \pmod{101}$

Answer: $13^{11} \pmod{101} = 20$.

⚠️ Common pitfall: Forgetting to take the modulus after each multiplication. For example, calculating 80 * 68 first gives 5440. A larger problem could easily exceed long long capacity if the modulus isn't applied immediately.

Topic: Binary Exponentiation

Example: Modular Division using FLT

Problem: Calculate $(100 / 17) \pmod{23}$.

Solution:

Step 1: Verify conditions for Fermat's Little Theorem.

• Reasoning: To divide by 17, we need its modular inverse. Since the modulus 23 is a prime number, we can use FLT.
• Work: The modulus p = 23 is prime. The number a = 17 is not divisible by 23. Conditions are met.

Step 2: Find the modular inverse of 17.

• Reasoning: According to FLT, $17^{-1} \equiv 17^{23-2} \equiv 17^{21} \pmod{23}$. We can compute this with binary exponentiation.
• Work: Calculate $17^{21} \pmod{23}$.
  • $17^1 \equiv 17 \equiv -6 \pmod{23}$
  • $17^2 \equiv (-6)^2 \equiv 36 \equiv 13 \pmod{23}$
  • $17^4 \equiv 13^2 \equiv 169 \equiv 8 \pmod{23}$
  • $17^8 \equiv 8^2 \equiv 64 \equiv 18 \equiv -5 \pmod{23}$
  • $17^{16} \equiv (-5)^2 \equiv 25 \equiv 2 \pmod{23}$ Exponent $21 = 16 + 4 + 1$. $17^{21} \equiv 17^{16} \cdot 17^4 \cdot 17^1 \pmod{23}$ $\equiv (2 \cdot 8 \cdot 17) \pmod{23}$ $\equiv (16 \cdot 17) \pmod{23}$ $\equiv 272 \pmod{23}$ $\equiv 19 \pmod{23}$ So, $17^{-1} \equiv 19 \pmod{23}$.

Step 3: Perform the multiplication.

• Reasoning: Division by 17 is now multiplication by its inverse, 19.
• Work: $(100 / 17) \pmod{23} \equiv (100 \cdot 19) \pmod{23}$ $\equiv (100 \pmod{23}) \cdot 19 \pmod{23}$ $100 = 4 \cdot 23 + 8$, so $100 \equiv 8 \pmod{23}$. $\equiv (8 \cdot 19) \pmod{23}$ $\equiv 152 \pmod{23}$ $152 = 6 \cdot 23 + 14$, so $152 \equiv 14 \pmod{23}$.

Answer: $(100 / 17) \pmod{23} = 14$.

⚠️ Common pitfall: Assuming you can perform floating-point division and then take the modulus, e.g., (100.0/17.0) % 23. This is mathematically incorrect and will produce the wrong answer.

Topic: Fermat's Little Theorem (FLT)