🦄 Hornsmith's Modular Inverse

Difficulty: Intermediate Tags: number-theory, math, extended-gcd, cryptography Series: CS 101

Problem

In the Hornsmith's forge, magical numbers can be "inverted" under modular arithmetic. Given two integers a and m, find the modular multiplicative inverse of a modulo m.

The modular inverse x satisfies: (a × x) mod m = 1

If no such inverse exists, return None.

Real-World Application

Modular inverses are fundamental to: - RSA Encryption - used in generating public/private key pairs - Cryptographic hashing - used in digital signatures - Error correction codes - used in data transmission - Random number generation - used in Monte Carlo simulations - Combinatorics - calculating binomial coefficients modulo prime

Input

data = {
    'a': int,  # The number to invert
    'm': int   # The modulus (must be positive)
}

Output

int or None  # The modular inverse x, or None if it doesn't exist

Constraints

• |a|, m ≤ 10^12
• m > 0
• If gcd(a, m) ≠ 1, no inverse exists (return None)

Examples

Example 1: Basic Inverse

Input: {'a': 3, 'm': 11}

Output: 4

Explanation: - (3 × 4) mod 11 = 12 mod 11 = 1 ✓ - So 4 is the modular inverse of 3 modulo 11

Example 2: Larger Numbers

Input: {'a': 10, 'm': 17}

Output: 12

Explanation: - (10 × 12) mod 17 = 120 mod 17 = 1 ✓ - So 12 is the modular inverse of 10 modulo 17

Example 3: No Inverse (Common Factors)

Input: {'a': 6, 'm': 9}

Output: None

Explanation: - gcd(6, 9) = 3 ≠ 1 - Since 6 and 9 share a common factor, no inverse exists - There's no x where (6 × x) mod 9 = 1

Example 4: Negative Number

Input: {'a': -3, 'm': 11}

Output: 7

Explanation: - (-3 × 7) mod 11 = -21 mod 11 = 1 ✓ - Negative numbers can have modular inverses too!

What You'll Learn

• The Extended Euclidean Algorithm (finding coefficients in Bézout's identity)
• When modular inverses exist (coprimality condition)
• How to handle negative numbers in modular arithmetic
• The mathematical foundation of RSA cryptography

Why This Matters

Technical interviews for cryptography, security, or backend roles often include: - Implementing Extended Euclidean Algorithm - Understanding modular arithmetic properties - Recognizing when solutions exist (gcd conditions) - Handling edge cases (negative numbers, large values)

Starter Code

def challenge_function(data):
    """
    Find the modular multiplicative inverse of a modulo m.

    Args:
        data: dict with keys 'a' (int) and 'm' (int)

    Returns:
        int: modular inverse x where (a * x) % m == 1
        None: if inverse doesn't exist (when gcd(a, m) != 1)
    """
    # Your implementation here
    pass