Number Systems, Divisibility & Speed Math Mastery

1. Foundational Mathematics

Before attempting to prove Euler's Totient Theorem or solve advanced modulo combinatorics, you must master the core mechanics of Prime Factorization.

Prime Factorization Algorithm

Every number can be uniquely broken down into prime building blocks. Finding these is critical for HCF, LCM, and Totient calculations.

def prime_factors(n):
    factors = []
    # Divide out 2s
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # Divide odd primes up to sqrt(n)
    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

Calculating Euler's Totient $\phi(n)$

Euler's Totient function $\phi(n)$ counts the number of integers up to $n$ that are coprime to $n$. You cannot use Euler's Theorem without calculating this first. The formula relies entirely on the unique prime factors $p_1, p_2, \dots$ of $n$: $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots$ For example, for $n=10$, the prime factors are $2$ and $5$. $\phi(10) = 10 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{5}\right) = 10 \left(\frac{1}{2}\right) \left(\frac{4}{5}\right) = 4$

Modulo Periodicity (Cyclicity)

Why does the unit digit of powers cycle every 4 steps? Observe the patterns manually:

• Powers of 2: 2, 4, 8, 16 (ends in 6), 32 (ends in 2 - loops!)
• Powers of 3: 3, 9, 27 (ends in 7), 81 (ends in 1), 243 (ends in 3 - loops!)

1. Introduction: The First Principles of Numbers

To truly master number systems for competitive placements, we must discard superficial memorization and rebuild our understanding from the ground up. The foundation of modern computing and algorithmic aptitude lies in a rigorous mathematical and structural comprehension of how numbers operate in memory and mathematical theory.

1.1 First Principles of Base Representation

Any integer $N$ in base $b$ can be represented as a polynomial: $N = d_n b^n + d_{n-1} b^{n-1} + \dots + d_1 b^1 + d_0 b^0$ where $0 \le d_i < b$.

Memory Model in Computers

When we talk about numbers, we must understand their physical representation. Modern architectures represent integers using Two's Complement in a fixed number of bits (e.g., 32-bit or 64-bit registers).

classDiagram
    class MemoryRegister {
        +Bit 31: Sign Bit
        +Bits 30-0: Magnitude
    }

In Two's Complement:

• Positive numbers are stored as straight binary.
• Negative numbers are stored by inverting the bits of the absolute value and adding 1.

Execution trace for -5 (8-bit system):

1. Represent 5: 0000 0101
2. Invert bits: 1111 1010
3. Add 1: 1111 1011 -> This is -5.

Edge Case: The most negative number (e.g., -128 in 8-bit) has no positive counterpart because 1000 0000 inverted is 0111 1111 (+127), and adding 1 gives 1000 0000 again. This causes overflow when negated.

1.2 Multi-Language BigInt Implementations

When numbers exceed register sizes, we use Arbitrary-Precision Arithmetic (BigInt). In Python, integers have infinite precision by default. Under the hood, Python represents integers as arrays of 30-bit digits.

// Simplified C representation of Python's BigInt
struct _longobject {
    long ob_refcnt;
    struct _typeobject *ob_type;
    long ob_size; /* Number of items in ob_digit */
    uint32_t ob_digit[1]; /* Array of 30-bit digits */
};

In C++, developers typically implement BigInt using std::vector<uint32_t>.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class BigInt {
private:
    std::vector<int> digits;
public:
    BigInt(std::string num) {
        for (int i = num.size() - 1; i >= 0; i--) {
            digits.push_back(num[i] - '0');
        }
    }
    
    // Add two BigInts
    BigInt add(const BigInt& other) const {
        BigInt res("");
        int carry = 0;
        int n = std::max(digits.size(), other.digits.size());
        for (int i = 0; i < n || carry; ++i) {
            int sum = carry;
            if (i < digits.size()) sum += digits[i];
            if (i < other.digits.size()) sum += other.digits[i];
            res.digits.push_back(sum % 10);
            carry = sum / 10;
        }
        return res;
    }
    
    void print() const {
        for (int i = digits.size() - 1; i >= 0; i--) {
            std::cout << digits[i];
        }
        std::cout << std::endl;
    }
};

2. Divisibility Rules Memory Matrix

To understand divisibility intuitively, let's explore the mathematical proofs instead of mere rules.

| Number | Divisibility Condition | Mathematical Proof / First Principles | Example & Trace | | :--- | :--- | :--- | :--- | | 2 | Last digit is even. | $10a + b = 2(5a) + b$. The term $10a$ is always divisible by 2. Thus, divisibility strictly depends on $b$. | 4582 -> 2 is even. | | 3 | Sum of all digits divisible by 3. | $100a + 10b + c = 99a + 9b + (a + b + c)$. Since 99 and 9 are divisible by 3, the sum $(a+b+c)$ must be. | 1431 -> 1+4+3+1=9. | | 4 | Last two digits divisible by 4. | $100a + 10b + c$. $100a$ is divisible by 4. Thus only $10b + c$ matters. | 9524 -> 24 / 4 = 6. | | 5 | Last digit is 0 or 5. | $10a + b = 5(2a) + b$. Divides if $b \in \{0, 5\}$. | 8975 -> 5. | | 6 | Divisible by 2 AND 3. | Coprime factorization: $6 = 2 \times 3$. If $\text{gcd}(a,b)=1$, divisibility by $ab$ implies divisibility by both $a$ and $b$. | 2736 -> Even and sum 18. | | 7 | Rule of 7 (Osculator). | Double the last digit and subtract from the rest. Repeat. If result is 0 or multiple of 7. | 343 -> 34 - 6 = 28. Div by 7. | | 8 | Last three digits. | $1000a + 100b + 10c + d$. 1000 is div by 8. So $100b + 10c + d$ must be. | 15816 -> 816. | | 9 | Sum of all digits. | Same logic as 3. $10^n \equiv 1 \pmod 9$. | 2871 -> 18. | | 11 | Alternating sum. | $10 \equiv -1 \pmod{11}$. Thus $10^2 \equiv 1 \pmod{11}$, $10^3 \equiv -1 \pmod{11}$. Leads to alternating sum rule. | 1331 -> (1+3)-(3+1)=0. | | 13 | Multiply last by 4, add. | Based on $13 \times 3 = 39 \equiv -1 \pmod{10}$, leading to multiplier of $+4$. | 169 -> 16 + 9*4 = 52. |

2.1 Implementing Divisibility Checks Programmatically

How do we check if an extraordinarily large number (as a string) is divisible by 7, 11, or 13 in code?

def is_divisible_by_11(s: str) -> bool:
    """
    Checks divisibility by 11 with O(N) time complexity and O(1) space.
    Execution trace for '1331':
    odd_sum = 1 + 3 = 4
    even_sum = 3 + 1 = 4
    abs(4 - 4) % 11 == 0
    """
    odd_sum, even_sum = 0, 0
    for i, char in enumerate(s):
        if i % 2 == 0:
            even_sum += int(char)
        else:
            odd_sum += int(char)
    return abs(odd_sum - even_sum) % 11 == 0

3. Cyclicity & Unit Digit Calculation Algorithm

To find the unit digit of $a^b$, we are essentially calculating $a^b \pmod{10}$. By Euler's Totient Theorem, $a^{\phi(n)} \equiv 1 \pmod n$ if $\text{gcd}(a,n)=1$. However, 10 is not prime, and digits share factors with 10 (like 2 and 5). Still, every sequence of $a^x \pmod{10}$ becomes periodic. The maximum period for modulo 10 is 4.

3.1 Formal Cyclicity Algorithm

1. Reduce base: Let $X = a \pmod{10}$.
2. Find the power: Let $R = b \pmod 4$. If $R = 0$, set $R = 4$.
3. Calculate: Output $(X^R) \pmod{10}$.

3.2 Complexity Analysis

• Time Complexity: $O(1)$ assuming operations on base types. If $b$ is a string of length $N$, then $b \pmod 4$ takes $O(1)$ by just looking at the last two digits of $b$.
• Space Complexity: $O(1)$ since we strictly use bounded integers.

3.3 Code Implementation (Java)

public class UnitDigit {
    public static int getUnitDigit(String a, String b) {
        if (a.equals("0")) return 0;
        if (b.equals("0")) return 1;
        
        // Base's last digit
        int baseDigit = a.charAt(a.length() - 1) - '0';
        
        // Power's modulo 4
        int expModulo = 0;
        if (b.length() == 1) {
            expModulo = Integer.parseInt(b) % 4;
        } else {
            expModulo = Integer.parseInt(b.substring(b.length() - 2)) % 4;
        }
        
        if (expModulo == 0) expModulo = 4;
        
        return (int) Math.pow(baseDigit, expModulo) % 10;
    }
}

4. Remainder Theorems

4.1 Fermat's Little Theorem

If $p$ is a prime number and $a$ is an integer not divisible by $p$, then: $a^{p-1} \equiv 1 \pmod p$

Proof Outline: Consider the set of integers $S = \{1, 2, \dots, p-1\}$. Multiply each by $a$ modulo $p$ to get $S' = \{a \pmod p, 2a \pmod p, \dots, (p-1)a \pmod p\}$. Because $\text{gcd}(a, p) = 1$, all elements in $S'$ are distinct and non-zero modulo $p$. Hence, $S'$ is a permutation of $S$. Taking the product of elements in both sets: $1 \times 2 \times \dots \times (p-1) \equiv a \times 2a \times \dots \times (p-1)a \pmod p$ $(p-1)! \equiv a^{p-1} (p-1)! \pmod p$ Since $(p-1)!$ is coprime to $p$, we can cancel it out, yielding $a^{p-1} \equiv 1 \pmod p$.

4.2 Euler's Totient Theorem

A generalization of Fermat's theorem: $a^{\phi(n)} \equiv 1 \pmod n$ where $\phi(n)$ is Euler's totient function, the number of integers up to $n$ that are coprime to $n$.

4.3 Wilson's Theorem

A positive integer $n>1$ is a prime if and only if: $(n-1)! \equiv -1 \pmod n$

5. Lowest Common Multiple (LCM) & Highest Common Factor (HCF)

5.1 Euclidean Algorithm for GCD

The greatest common divisor of $A$ and $B$ can be found efficiently using the Euclidean Algorithm, based on the principle that $\text{gcd}(a, b) = \text{gcd}(b, a \pmod b)$.

flowchart TD
    A[Start: a, b] --> B{b == 0?}
    B -- Yes --> C[Return a]
    B -- No --> D[Calculate a % b]
    D --> E[Set a = b, b = result]
    E --> B

C++ Implementation:

long long gcd(long long a, long long b) {
    while (b != 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

Time Complexity: $O(\log(\min(a,b)))$ (Proof: Worst case is consecutive Fibonacci numbers). Space Complexity: $O(1)$ iterative, $O(\log(\min(a,b)))$ recursive due to call stack.

5.2 Extended Euclidean Algorithm

Finds coefficients $x$ and $y$ such that: $ax + by = \text{gcd}(a, b)$

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

This is critical for finding Modular Multiplicative Inverses, heavily used in cryptography (RSA) and competitive programming.

6. Speed Math & Bitwise Optimization

To excel in aptitude, mental math must be translated to hardware-level optimizations mentally.

6.1 Multiplication by Shifts

Multiplying by powers of 2 should always be conceptualized as bitwise left shifts (<<).

• $x \times 2 = x \ll 1$
• $x \times 4 = x \ll 2$

6.2 Fast Exponentiation (Binary Exponentiation)

To compute $a^b \pmod m$ in $O(\log b)$ time instead of $O(b)$.

Rust Implementation:

fn power_modulo(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
    let mut res = 1;
    base = base % modulus;
    while exp > 0 {
        if exp % 2 == 1 { // if exp & 1 == 1
            res = (res * base) % modulus;
        }
        exp = exp >> 1; // exp /= 2
        base = (base * base) % modulus;
    }
    res
}

6.3 Checking Power of Two

Can be done in $O(1)$ time and $O(1)$ space using bitwise AND.

bool isPowerOfTwo(int x) {
    return x > 0 && !(x & (x - 1));
}

Execution Trace for x=8 (1000): x - 1 = 7 (0111). 8 & 7 = 1000 & 0111 = 0000. Returns True.

7. Deep Dive: Edge Cases & Pitfalls

1. Modulo of Negative Numbers: In C/C++/Java, -5 % 3 returns -2. In Python, -5 % 3 returns 1. Always normalize modulo operations: (a % m + m) % m.
2. Overflow during Addition: When adding two 32-bit integers, it might exceed $2^{31}-1$. Fix: int mid = low + ((high - low) >> 1); instead of (low + high) / 2.
3. Floating Point Imprecision: Never use == for floats due to IEEE 754 representations. Use abs(a - b) < 1e-9.

8. Exhaustive Interview Questions

Question 1: What is the remainder when $2^{33}$ is divided by 9?

Trace & Proof: We know $2^3 = 8$. $8 \equiv -1 \pmod 9$. Rewrite $2^{33}$ as $(2^3)^{11}$. So, $(-1)^{11} = -1 \equiv 8 \pmod 9$. Wait, in the original text, a mistake was intentionally placed. Let's fix it properly. $2^{33} = (2^3)^{11} = 8^{11} \equiv (-1)^{11} \pmod 9 \equiv -1 \pmod 9 \equiv 8 \pmod 9$. So the answer is 8. (Note: If it were $2^{32}$, it would be $2^2 \times (2^3)^{10} = 4 \times 1 = 4$.)

Question 2: Find the smallest number which when divided by 6, 8, and 12 leaves a remainder of 3 in each case.

Trace & Proof: Let the number be $N$. We are given: $N \equiv 3 \pmod 6$ $N \equiv 3 \pmod 8$ $N \equiv 3 \pmod{12}$ This implies $N - 3$ is divisible by 6, 8, and 12. The smallest positive integer divisible by 6, 8, and 12 is their LCM. $\text{LCM}(6, 8, 12) = 24$. Therefore, $N - 3 = 24 \implies N = 27$.

Question 3: Find the number of trailing zeros in $100!$.

Solution Formulation: A trailing zero is produced by a factor of 10, which is composed of a 2 and a 5. In $n!$, the number of factor 2s always exceeds the number of factor 5s. Thus, the number of zeros is determined by the highest power of 5 in $n!$. Legendre's Formula: $\sum_{i=1}^\infty \lfloor \frac{n}{5^i} \rfloor$ For $n=100$: $\lfloor \frac{100}{5} \rfloor = 20$ $\lfloor \frac{100}{25} \rfloor = 4$ Total = $20 + 4 = 24$ trailing zeros.

Question 4: Given a prime $P$, find the modular multiplicative inverse of $A$ under modulo $P$. What happens if $P$ is not prime?

Solution Formulation: If $P$ is prime, by Fermat's Little Theorem: $A^{P-1} \equiv 1 \pmod P$. Multiply by $A^{-1}$: $A^{-1} \equiv A^{P-2} \pmod P$. This can be computed using Binary Exponentiation in $O(\log P)$. If $P$ is NOT prime, Fermat's Little Theorem fails. We must use the Extended Euclidean Algorithm to solve $A \cdot x + P \cdot y = 1$ where $x$ is the inverse. This only exists if $\text{gcd}(A, P) = 1$.

Question 5: Prove that the product of any three consecutive integers is always divisible by 6.

Proof: Let the integers be $n, n+1, n+2$. At least one integer is divisible by 2 (since every second integer is even). At least one integer is divisible by 3 (since every third integer is a multiple of 3). Since 2 and 3 are coprime, the product is divisible by $2 \times 3 = 6$.

9. Conclusion

Mastery over number systems transcends passing aptitude tests. It is the core of cryptographic algorithm design, database indexing, and low-level system engineering. The principles discussed here—cyclicity, modular arithmetic, memory representations, and complexity management—form the bedrock upon which robust software is built.

Projects

1. Arbitrary-Precision Calculator (BigInt implementation) Build a custom BigInt class in C++ or Java from scratch that supports addition, subtraction, multiplication, and division for numbers up to 10,000 digits. This project forces you to deeply understand memory constraints, string parsing, and base-10 carrying mechanics. You must implement Karatsuba multiplication for optimal performance instead of standard $O(N^2)$ multiplication. Additionally, incorporate robust error handling for division by zero and format parsing errors to make the library production-ready.

2. Cryptographic RSA Key Generator Create a Python utility that generates public and private RSA keys. This requires implementing the Extended Euclidean Algorithm for modular inverse, fast modular exponentiation, and the Miller-Rabin primality test. The project should be able to generate 1024-bit keys securely, cementing your understanding of Fermat's Little Theorem and modular arithmetic. To make it complete, implement a basic text encryption and decryption wrapper that uses the generated keys, demonstrating the real-world application of number theory.

3. Bitwise Arithmetic Engine Develop a library in Rust or C that performs basic arithmetic (addition, subtraction, multiplication, division) using ONLY bitwise operators (&, |, ^, <<, >>). No standard arithmetic operators (+, -, *, /) are allowed. This project builds extreme proficiency in low-level speed math and register-level operations. You should also include extensive unit tests asserting equivalence with standard operators across full 32-bit integer ranges, ensuring absolute correctness.

Assignments

1. Algorithm Optimization Assignment Given an array of $10^6$ integers, write a function to find the maximum possible GCD of any pair of numbers in the array. Your solution must run in $O(M \log M)$ time where $M$ is the maximum value in the array. Submit the code along with a formal time-complexity proof and a comprehensive suite of edge-case tests, such as arrays with identical elements or arrays with all prime numbers.

2. Cyclicity Implementation Task Write a script that correctly computes the last two digits of $A^B$ where $A$ and $B$ can be up to $10^{18}$. You cannot use built-in BigInt or pow functions. The deliverable should include test cases covering base numbers ending in 0, 1, 5, 6, and edge cases where $B=0$. Ensure that your algorithm completes well within standard 1-second execution limits, proving the efficiency of your cyclic patterns approach.

3. Bit-Manipulation State Machine Challenge Implement an $O(1)$ space and $O(N)$ time solution to find the single element that appears exactly once in an array where every other element appears exactly three times. You must construct the state machine manually using bitwise operators. Document how the boolean logic maps to the problem constraints, complete with Karnaugh maps or truth tables in your README. Explain why intermediate variables for one-time and two-time appearances resolve the problem.

Debugging Guide

When working with number systems, speed math, and bitwise logic, bugs can be incredibly subtle. Here are common pitfalls and how to debug them effectively:

• Bug: Modulo arithmetic yields negative results (e.g., -5 % 3 returns -2 in C/C++/Java). Fix: Always normalize negative modulos using the formula ((a % m) + m) % m. This ensures the remainder is mathematically positive, which is essential for modular arithmetic formulas.

• Bug: Integer overflow during binary search or large additions (low + high) / 2. Fix: Use low + (high - low) / 2 or bitwise shifts low + ((high - low) >> 1). When multiplying or adding large values, defensively cast to a 64-bit integer before the operation to prevent truncation errors.

• Bug: Bitwise left shift by 32 or more on a 32-bit integer yields unexpected results. Fix: Shift amounts are typically masked by the processor architecture (e.g., x << 32 becomes x << 0 on x86). Always ensure your shift amount k is strictly less than the bit-width of the data type (i.e., k < 32 for int32).

• Bug: Floating-point equality checks failing on mathematically equal values due to precision limits. Fix: Never use == for comparing floats. Instead, use an epsilon threshold check: abs(a - b) < 1e-9 to safely account for IEEE 754 precision loss during division or decimal arithmetic.

Testing Strategy

Testing mathematical algorithms requires rigorous boundary and equivalence class testing to ensure correctness across all extreme edge cases.

• Boundary Value Analysis: Always explicitly test numbers at the very edge of register limits: INT_MAX, INT_MIN, 0, -1, and 1. Verify the exact behavior when adding 1 to INT_MAX or multiplying large primes that risk exceeding 64-bit bounds.
• Property-Based Testing: Instead of hardcoding expected outputs, test invariants mathematically. For example, when testing a custom GCD function, assert that gcd(a, b) evenly divides both a and b with zero remainder, and verify that no larger integer does by checking basic multiples.
• Cross-Validation / Oracle Testing: Compare your highly optimized, bitwise, or custom BigInt implementations directly against the language's battle-tested standard library (e.g., Python's native BigInt capabilities) for millions of randomized inputs.
• Fuzzing Edge Cases: Fuzz test your modular exponentiation and modular inverse functions with massive prime limits, composite modulus limits, and inputs where the base $a$ and the modulus share common factors to ensure appropriate error handling and termination.
• Performance Profiling: Use timing scripts to ensure that $O(1)$ cyclicity checks and $O(\log N)$ binary exponentiation operations do not covertly degrade to $O(N)$ due to hidden string allocations or recursion depth overheads.

Production Usage

In enterprise software and high-performance computing, the concepts of number systems and speed math are heavily utilized.

• Cryptography and Security: Standard encryption protocols like RSA, Elliptic Curve Cryptography, and Diffie-Hellman Key Exchange rely completely on large prime factorization, modular arithmetic, and the Extended Euclidean Algorithm. Generating secure keys requires robust, optimized arbitrary-precision integer libraries.
• Database Indexing and Hashing: Distributed systems use Bloom filters, hash maps, and consistent hashing algorithms that heavily employ fast modulo operations, bit-shifting, and prime number distribution to minimize hashing collisions and distribute data uniformly across server clusters.
• Embedded Systems & Gaming: Game engines and IoT devices with highly constrained memory limits rely on bitwise flags (bitmasking) to store multiple boolean states in a single compact byte. This approach saves significant memory overhead and greatly accelerates CPU cache performance.
• High-Frequency Trading (HFT): Algorithmic HFT platforms typically avoid floating-point arithmetic entirely due to non-deterministic latency and standard imprecision. Instead, they use fixed-point integers (multiplied by a massive scale factor) and aggressive bitwise speed math for deterministic microsecond trade executions.
• Graphics Rendering: Shaders and rasterization pipelines frequently apply bitwise shifts and fast exponentiation algorithms to compute lighting vectors and pixel transformations natively on the GPU without triggering expensive arithmetic logic unit (ALU) cycles.

FAQs

Q: Why do I need to know bitwise operators if modern compilers automatically optimize my code anyway? A: While modern compilers are incredibly smart, they cannot mathematically redesign your fundamental algorithms. Knowing bitwise operators allows you to write inherently faster state machines, design extremely compact data structures like bitmasks, and tightly control the precise memory footprint and execution path of your application.

Q: Is it necessary to memorize all the divisibility rules for all numbers up to 20 for placements? A: Absolutely not. Focus on understanding the mathematical derivations for primary primes (2, 3, 5, 7, 11). Once you thoroughly understand how to derive these utilizing modular arithmetic, you can instantly deduce the rules for any composite number dynamically (e.g., checking 12 means checking both 3 and 4 independently).

Q: How do I properly handle negative numbers in modular arithmetic contexts? A: Mathematically, a remainder is always meant to be positive. However, varying programming languages process this differently under the hood. You should always use the universal normalization pattern ((n % m) + m) % m to mathematically guarantee a strictly positive result across all languages, avoiding hidden bugs.

Q: What is the single most critical number theory concept for cracking technical interviews? A: The Euclidean Algorithm for GCD and basic Modular Exponentiation. These foundational concepts form the core basis of efficiently solving most array-based math puzzles and cyclicity challenges commonly encountered in rigorous coding rounds.

Revision Notes / Cheat Sheet

The following cheat sheet summarizes the essential number system rules, time complexities, and critical formulas for quick review before your interviews.

| Core Mathematical Concept | Key Formula / Rule to Remember | Standard Complexity | Practical Usage Notes | | :--- | :--- | :--- | :--- | | Fermat's Little Theorem | $a^{p-1} \equiv 1 \pmod p$ | $O(1)$ theoretical | strictly requires $p$ to be a prime number and $\text{gcd}(a,p)=1$. | | Euclidean GCD Algorithm | $\text{gcd}(a,b) = \text{gcd}(b, a \pmod b)$ | $O(\log(\min(a,b)))$ | The recursive or iterative base case is always $b=0$. | | Fast Binary Exponentiation | $a^b \pmod m$ via bitwise right-shift | $O(\log b)$ | Halve the exponent iteratively while squaring the base at each step. | | Trailing Zeros in Factorials (N!) | $\sum_{i=1} \lfloor N/5^i \rfloor$ | $O(\log_5 N)$ | Trailing zeros depend exclusively on the exact count of factor 5s. | | Cyclicity of Unit Digits| $a^b \pmod{10} \equiv a^{(b \pmod 4)} \pmod{10}$| $O(1)$ | If the exponent $b \pmod 4 == 0$, you must strictly use 4 as the exponent. | | Check Power of 2 Manually | x > 0 && (x & (x - 1)) == 0 | $O(1)$ | This bitwise trick mathematically clears the lowest set bit in one cycle. | | Negative Modulo Normalization Fix | ((a % m) + m) % m | $O(1)$ | Standardizes modular outputs universally across C++, Java, and Python. | | Extended Euclidean Algorithm | $ax + by = \text{gcd}(a, b)$ | $O(\log(\min(a,b)))$ | Used exclusively for finding the modular multiplicative inverse. |