Open Source · 7 Languages · 1007 Problems + Bonus

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.