Problem Summary

We want all residues \(x\) satisfying

$$x^3\equiv1\pmod n,$$

and then we sum all nontrivial solutions, meaning all residues with \(1<x<n\). The default value used by the code is

$$n=13082761331670030=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43,$$

which is squarefree.

Mathematical Approach

1. Split the Problem Prime by Prime

Because \(n\) is squarefree, we may write

$$n=\prod_{i=1}^{k}p_i$$

with distinct primes \(p_i\). Then

$$x^3\equiv1\pmod n$$

is equivalent to the simultaneous system

$$x^3\equiv1\pmod{p_i}\qquad(i=1,\dots,k).$$

So the whole problem becomes:

1. find all cube roots of unity modulo each prime \(p_i\),

2. combine one local choice from each prime modulus using the Chinese Remainder Theorem.

2. How Many Cube Roots Exist Modulo a Prime?

For a prime \(p\), the nonzero residues modulo \(p\) form a cyclic multiplicative group of size \(p-1\). In a cyclic group of order \(p-1\), the equation

$$u^3=1$$

has exactly

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

solutions. Therefore:

1. if \(p\equiv2\pmod3\), then \(\gcd(3,p-1)=1\), so the only root is \(1\),

2. if \(p\equiv1\pmod3\), then \(\gcd(3,p-1)=3\), so there are three roots.

The code does not use a special generator argument; since every prime factor of the target \(n\) is small, it simply brute-forces all residues \(1\le x<p\) and keeps those with \(x^3\equiv1\pmod p\).

3. Small Local Examples

For \(p=7\), the roots are

$$R_7=\{1,2,4\},$$

because \(1^3\equiv2^3\equiv4^3\equiv1\pmod7\).

For \(p=13\), the roots are

$$R_{13}=\{1,3,9\}.$$

For primes such as \(5,11,17,23,29,41\), which are \(2\pmod3\), the local root set is just \(\{1\}\).

4. Chinese Remainder Reconstruction

Once we choose one root \(r_i\in R_{p_i}\) for every prime factor, there is a unique residue modulo \(n\) satisfying

$$x\equiv r_i\pmod{p_i}\qquad(i=1,\dots,k).$$

The implementation combines congruences two at a time. If we already know

$$x\equiv a_1\pmod{m_1},\qquad x\equiv a_2\pmod{m_2},$$

with \(\gcd(m_1,m_2)=1\), then the merged solution is

$$x=a_1+m_1\left((a_2-a_1)m_1^{-1}\bmod m_2\right).$$

This is exactly the formula implemented in crt_pair.

5. Why Enumeration Is Tiny

The default number \(n\) has 14 distinct prime factors. Among them, exactly six primes are \(1\pmod3\):

$$7,13,19,31,37,43.$$

Those contribute three local roots each. Every other prime contributes only one local root. Therefore the total number of global solutions is

$$3^6=729.$$

That is why a direct DFS over all CRT combinations is entirely practical.

6. Worked Checkpoint: \(n=7\)

The roots modulo \(7\) are \(\{1,2,4\}\). The trivial root \(1\) is excluded from the final sum, so the code returns

$$2+4=6.$$

This matches the checkpoint solve(7)=6.

7. Worked Checkpoint: \(n=91=7\cdot13\)

Here we combine

$$R_7=\{1,2,4\},\qquad R_{13}=\{1,3,9\}.$$

By CRT, each pair \((r_7,r_{13})\) gives exactly one solution modulo \(91\), so there are

$$3\cdot3=9$$

solutions in total. They are

$$1,\;9,\;16,\;22,\;29,\;53,\;74,\;79,\;81.$$

Excluding the trivial residue \(1\), the sum is

$$9+16+22+29+53+74+79+81=363,$$

which is exactly the checkpoint solve(91)=363.

8. Final Summation Rule

The DFS enumerates all global CRT solutions. At the leaf of the recursion, the code adds the residue only if

$$1<x<n.$$

That removes the always-present trivial solution \(x=1\) and keeps every nontrivial cube root of unity modulo \(n\).

How the Code Works

distinct_prime_factors extracts the distinct prime divisors of \(n\).

mod_pow tests local candidates by checking \(x^3\bmod p\).

crt_pair merges two congruences using an inverse computed by mod_inverse.

solve first builds roots_by_prime, then runs a DFS over all local root choices, updating the current CRT residue and modulus at each step.

The command-line interface supports --n=<value> and --skip-checkpoints.

Complexity Analysis

If the distinct prime factors are \(p_1,\dots,p_k\), then the number of DFS states is essentially

$$\prod_{i=1}^{k}\gcd(3,p_i-1).$$

Each transition performs only constant-time modular arithmetic at machine-word size, so the method is dominated by the number of local-root combinations.

Further Reading

1. Problem page: https://projecteuler.net/problem=271
2. Chinese Remainder Theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
3. Primitive roots and roots of unity modulo primes: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n