Solution

Answer: 4617456485273129588

Let

$$N=13082761331670030.$$

We are asked to compute

$$S(N)=\sum_{\substack{1<x<N\ x^3\equiv 1\pmod N}} x.$$

1. Mathematical analysis

First factor $N$:

$$N=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31\cdot 37\cdot 41\cdot 43.$$

So $N$ is squarefree.

Step 1: Solve modulo each prime

For a prime $p$, the nonzero residues modulo $p$ form a cyclic group of order $p-1$.

The equation

$$x^3\equiv 1 \pmod p$$

therefore has exactly

$$\gcd(3,p-1)$$

solutions.

If $p\equiv 2 \pmod 3$, there is only one solution: $x\equiv 1$.
If $p\equiv 1 \pmod 3$, there are three cube roots of unity.

Among the primes dividing $N$,

$$7,13,19,31,37,43 \equiv 1 \pmod 3,$$

so each contributes $3$ solutions.

All the others contribute only $1$ solution.

Hence the total number of solutions modulo $N$ is

$$3^6 = 729.$$

One of them is $x=1$, which is excluded from the sum.

Step 2: Use the Chinese Remainder Theorem

Because $N$ is squarefree, every solution modulo $N$ corresponds uniquely to choosing a cube root modulo each prime factor.

The roots are:

modulo $7$: $1,2,4$
modulo $13$: $1,3,9$
modulo $19$: $1,7,11$
modulo $31$: $1,5,25$
modulo $37$: $1,10,26$
modulo $43$: $1,6,36$

and modulo every other prime only $1$.

Thus we can enumerate all $729$ CRT combinations and sum them.

2. Python implementation

from itertools import product
from sympy.ntheory.modular import crt

# The number from the problem
N = 13082761331670030

# Prime factors of N
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43]

# Compute all cube roots of unity modulo each prime
roots = []
for p in primes:
    r = [x for x in range(p) if pow(x, 3, p) == 1]
    roots.append(r)

# Enumerate all CRT combinations
total = 0

for residues in product(*roots):
    x = int(crt(primes, residues)[0])

    if 1 < x < N:
        total += x

print(total)

3. Code walkthrough

Finding cube roots modulo each prime

r = [x for x in range(p) if pow(x, 3, p) == 1]

This computes all residues satisfying

$$x^3 \equiv 1 \pmod p.$$

For example:

modulo $7$: $[1,2,4]$
modulo $13$: $[1,3,9]$

etc.

Enumerating all combinations

for residues in product(*roots):

Since each prime contributes independent choices, the Cartesian product gives every solution modulo $N$.

There are

$$3^6 = 729$$

such tuples.

Reconstructing the unique solution modulo $N$

x = int(crt(primes, residues)[0])

The Chinese Remainder Theorem reconstructs the unique integer

$$0 \le x < N$$

satisfying all congruences simultaneously.

Summing valid values

if 1 < x < N:
    total += x

The problem excludes $x=1$, so we omit it.

4. Verification

For the example $n=91=7\cdot 13$:

roots modulo $7$: $1,2,4$
roots modulo $13$: $1,3,9$

giving $3\times3=9$ total CRT combinations.

Excluding $1$, the remaining eight values are exactly

$$9,16,22,29,53,74,79,81,$$

whose sum is

$$363,$$

matching the statement.

Running the program for

$$N=13082761331670030$$

gives:

$$4617456485273129588.$$

Answer: 4617456485273129588

Project Euler Problem 271