Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 271: Modular Cubes, Part 1

Project Euler Problem 271 Solution

EulerSolve provides an optimized solution for Project Euler Problem 271, Modular Cubes, Part 1, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

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.