Problem 271: Modular Cubes, Part 1

Mathematical Foundation

Theorem 1 (CRT Factorisation of Cube Roots). Let $N = p_1 p_2 \cdots p_k$ be a product of distinct primes. Then $n^3 \equiv 1 \pmod{N}$ if and only if $n^3 \equiv 1 \pmod{p_i}$ for every $i = 1, \ldots, k$.

Proof. Since the $p_i$ are pairwise coprime, $\mathbb{Z}/N\mathbb{Z} \cong \prod_{i=1}^{k} \mathbb{Z}/p_i\mathbb{Z}$ by the Chinese Remainder Theorem. Under this isomorphism, $n^3 \equiv 1 \pmod{N}$ corresponds to $n_i^3 \equiv 1 \pmod{p_i}$ for each component $n_i$. $\square$

Lemma 1 (Cube Roots of Unity mod $p$). Let $p$ be a prime. The number of solutions to $x^3 \equiv 1 \pmod{p}$ is $\gcd(3, p-1)$.

Proof. The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $p - 1$. Let $g$ be a generator and write $x = g^t$. Then $x^3 = 1$ iff $g^{3t} = 1$ iff $(p-1) \mid 3t$ iff $(p-1)/\gcd(3, p-1) \mid t$. The number of valid $t$ in $\{0, 1, \ldots, p-2\}$ is $\gcd(3, p-1)$. $\square$

Corollary. Among the 14 primes dividing $N$:

• Primes $p \equiv 1 \pmod{3}$: $\{7, 13, 19, 31, 37, 43\}$ (6 primes, each giving 3 cube roots of unity).
• Primes $p \not\equiv 1 \pmod{3}$: $\{2, 3, 5, 11, 17, 23, 29, 41\}$ (8 primes, each giving only the trivial root $x \equiv 1$).

Lemma 2 (Explicit Cube Roots). For a prime $p \equiv 1 \pmod{3}$, the three cube roots of unity modulo $p$ are $x = 1$ and $x = \frac{-1 \pm \sqrt{-3}}{2} \pmod{p}$, where $\sqrt{-3}$ denotes either square root of $-3$ modulo $p$ (which exists since $p \equiv 1 \pmod{3}$ implies $\left(\frac{-3}{p}\right) = 1$).

Proof. We have $x^3 - 1 = (x - 1)(x^2 + x + 1)$. The quadratic $x^2 + x + 1$ has discriminant $\Delta = -3$. By quadratic reciprocity and properties of the Legendre symbol, $\left(\frac{-3}{p}\right) = 1$ iff $p \equiv 1 \pmod{3}$. The roots follow from the quadratic formula over $\mathbb{F}_p$. $\square$

Theorem 2 (Total Count and Reconstruction). The total number of solutions to $n^3 \equiv 1 \pmod{N}$ with $0 < n < N$ is $3^6 = 729$. Each solution is uniquely determined by choosing one of the $\gcd(3, p_i - 1)$ cube roots modulo each $p_i$ and applying the CRT.

Proof. By Theorem 1 and Lemma 1, the solution set is a direct product $\prod_{i=1}^{14} R_i$ where $|R_i| = \gcd(3, p_i - 1)$. The total count is $\prod |R_i| = 3^6 \cdot 1^8 = 729$. Uniqueness of the CRT reconstruction is standard. $\square$

Editorial

We iterate over each prime, find all cube roots of unity. We then iterate over p in primes. Finally, find sqrt(-3) mod p by brute force or Tonelli-Shanks.

Pseudocode

For each prime, find all cube roots of unity
for p in primes
Find sqrt(-3) mod p by brute force or Tonelli-Shanks
else
Enumerate all 3^6 combinations via CRT

Complexity Analysis

• Time: Computing cube roots for each prime takes $O(p)$ in the worst case (or $O(\log^2 p)$ with Tonelli—Shanks). CRT reconstruction for each of the $3^6 = 729$ combinations costs $O(k)$ where $k = 14$. Total: $O(3^6 \cdot k) = O(10206)$.
• Space: $O(k)$ for storing roots and CRT intermediates.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 lll;

// Extended GCD
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular inverse of a mod m
ll modinv(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return ((x % m) + m) % m;
}

// Find cube roots of 1 mod p
vector<ll> cube_roots_of_unity(ll p) {
    vector<ll> roots;
    roots.push_back(1);
    if (p <= 3) return roots;
    if ((p - 1) % 3 != 0) return roots;
    // Find roots of x^2 + x + 1 = 0 mod p
    // x = (-1 +/- sqrt(-3)) / 2 mod p
    // Find sqrt(-3) mod p
    ll neg3 = p - 3;
    // Tonelli-Shanks for sqrt(neg3) mod p
    // Since p is small, just brute force
    ll sq = -1;
    for (ll i = 0; i < p; i++) {
        if ((i * i) % p == neg3) { sq = i; break; }
    }
    if (sq == -1) return roots;
    ll inv2 = modinv(2, p);
    ll r1 = (((p - 1) + sq) % p * inv2) % p;
    ll r2 = (((p - 1) + (p - sq)) % p * inv2) % p;
    if (r1 != 1) roots.push_back(r1);
    if (r2 != 1) roots.push_back(r2);
    return roots;
}

int main() {
    vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};
    ll N = 1;
    for (ll p : primes) N *= p;
    // N = 13082761331670030

    // For each prime, find cube roots of unity
    vector<vector<ll>> roots(14);
    for (int i = 0; i < 14; i++) {
        roots[i] = cube_roots_of_unity(primes[i]);
    }

    // CRT: for each combination, reconstruct n mod N
    // Precompute CRT coefficients: M_i = N / p_i, and M_i_inv = inverse of M_i mod p_i
    vector<ll> M(14), Minv(14);
    for (int i = 0; i < 14; i++) {
        M[i] = N / primes[i];
        Minv[i] = modinv(M[i] % primes[i], primes[i]);
    }

    // Enumerate all combinations using recursion
    // Use __int128 for intermediate computations
    lll total_sum = 0;
    int count = 0;

    // Iterative enumeration
    vector<int> idx(14, 0);
    while (true) {
        // Compute n via CRT
        lll n = 0;
        for (int i = 0; i < 14; i++) {
            lll term = (lll)roots[i][idx[i]] * Minv[i] % primes[i];
            term = term * M[i];
            n += term;
        }
        n %= (lll)N;
        if (n <= 0) n += N;
        if (n > 1 && n < N) {
            total_sum += n;
            count++;
        }

        // Increment indices
        int pos = 13;
        while (pos >= 0) {
            idx[pos]++;
            if (idx[pos] < (int)roots[pos].size()) break;
            idx[pos] = 0;
            pos--;
        }
        if (pos < 0) break;
    }

    // Print result
    // __int128 printing
    lll ans = total_sum;
    string s;
    if (ans == 0) s = "0";
    else {
        while (ans > 0) {
            s += ('0' + (int)(ans % 10));
            ans /= 10;
        }
        reverse(s.begin(), s.end());
    }
    cout << s << endl;
    return 0;
}

"""
Problem 271: Modular Cubes, Part 1

Find the sum of all n (0 < n < N) such that n^3 = 1 (mod N),
where N = 2*3*5*7*11*13*17*19*23*29*31*37*41*43 = 13082761331670030.
"""

from itertools import product
from functools import reduce

def cube_roots_of_unity(p):
    """Find all x with x^3 = 1 (mod p)."""
    roots = [1]
    if p <= 3 or (p - 1) % 3 != 0:
        return roots
    # Find roots of x^2 + x + 1 = 0 (mod p)
    # x = (-1 +/- sqrt(-3)) / 2 mod p
    # Find sqrt(-3) mod p by brute force (p is small)
    neg3 = (-3) % p
    sq = None
    for i in range(p):
        if (i * i) % p == neg3:
            sq = i
            break
    if sq is None:
        return roots
    inv2 = pow(2, -1, p)
    r1 = ((-1 + sq) * inv2) % p
    r2 = ((-1 - sq) * inv2) % p
    if r1 != 1:
        roots.append(r1)
    if r2 != 1:
        roots.append(r2)
    return roots

def crt(residues, moduli):
    """Chinese Remainder Theorem for pairwise coprime moduli."""
    N = reduce(lambda a, b: a * b, moduli)
    result = 0
    for r, m in zip(residues, moduli):
        Mi = N // m
        yi = pow(Mi, -1, m)
        result += r * Mi * yi
    return result % N

def solve():
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
    N = reduce(lambda a, b: a * b, primes)

    # Find cube roots of unity for each prime
    roots = [cube_roots_of_unity(p) for p in primes]

    # Enumerate all combinations via CRT
    total = 0
    count = 0
    for combo in product(*roots):
        n = crt(combo, primes)
        if 1 < n < N:
            total += n
            count += 1

    print(total)

if __name__ == "__main__":
    solve()