Detailed mathematical approach

Problem Summary

For each integer \(n \le N\), define \(M(n)\) as the largest residue \(a \lt n\) satisfying

$$a^2 \equiv a \pmod{n}.$$

The goal is to compute

$$\sum_{n=1}^{N} M(n)$$

for the large bound \(N=10^7\). The key observation is that these residues are exactly the idempotents modulo \(n\), and their structure is controlled by the prime-power factorization of \(n\).

Mathematical Approach

Step 1: Rewrite the Congruence

The defining condition is equivalent to

$$a^2 \equiv a \pmod{n}\iff a(a-1)\equiv 0 \pmod{n}.$$

This form is more informative because the two factors differ by \(1\), so

$$\gcd(a,a-1)=1.$$

Therefore every prime power dividing \(n\) must divide one of these two coprime factors completely.

Step 2: Prime-Power Blocks Force Local Choices

Write the factorization of \(n\) as

$$n=\prod_{i=1}^{k} q_i,\qquad q_i=p_i^{e_i},$$

where the numbers \(q_1,\dots,q_k\) are pairwise coprime prime powers. If \(q_i\mid a(a-1)\), then the prime underlying \(q_i\) cannot divide both \(a\) and \(a-1\), so the whole block \(q_i\) must divide exactly one of them. Hence for each \(i\),

$$a\equiv 0 \pmod{q_i}\qquad\text{or}\qquad a\equiv 1 \pmod{q_i}.$$

Conversely, any residue that is \(0\) or \(1\) modulo every \(q_i\) is automatically idempotent modulo \(n\), because locally \(0^2=0\) and \(1^2=1\), and the Chinese remainder theorem glues the local conditions into one residue modulo \(n\).

So idempotents modulo \(n\) are in one-to-one correspondence with the \(2^k\) ways to choose, for each prime-power block, whether the residue is \(0\) or \(1\).

Step 3: Encode an Idempotent by a Subset

Choose a subset \(U\subseteq\{1,\dots,k\}\). Let

$$u=\prod_{i\in U} q_i,\qquad v=\frac{n}{u}.$$

The subset \(U\) means: force the residue to be \(0\) on the blocks inside \(U\), and \(1\) on the complementary blocks. That is, solve

$$a\equiv 0 \pmod{u},\qquad a\equiv 1 \pmod{v}.$$

Because \(u\) and \(v\) are coprime, the Chinese remainder theorem gives a unique solution modulo \(n\).

Step 4: Closed Form for Each Candidate

Since \(a\equiv 0\pmod{u}\), write \(a=ut\). The second congruence becomes

$$ut\equiv 1 \pmod{v}.$$

As \(\gcd(u,v)=1\), a unique inverse exists modulo \(v\). Let \(t_U\) be the integer with

$$0\le t_U\lt v,\qquad ut_U\equiv 1 \pmod{v}.$$

Then the idempotent attached to \(U\) is

$$a_U = u\,t_U.$$

When \(U=\emptyset\), we get \(u=1\), \(a=1\). When \(U=\{1,\dots,k\}\), we get \(u=n\), which corresponds to \(a=0\). These two trivial idempotents can never beat a nontrivial larger residue, so the maximum only needs nonempty proper subsets. Therefore

$$M(n)=\begin{cases} 0, & n=1,\\ 1, & n>1 \text{ and } k=1,\\ \max\limits_{\emptyset\neq U\neq\{1,\dots,k\}} a_U, & k\ge 2. \end{cases}$$

The case \(k=1\) means \(n\) is a prime power. Then only \(0\) and \(1\) are idempotent, so the largest residue below \(n\) is \(1\).

Step 5: Worked Example

Take \(n=12\). Its prime-power blocks are

$$12=4\cdot 3.$$

There are four idempotent patterns:

$$\begin{aligned} (0 \bmod 4,\ 0 \bmod 3) &\Rightarrow a=0,\\ (1 \bmod 4,\ 1 \bmod 3) &\Rightarrow a=1,\\ (0 \bmod 4,\ 1 \bmod 3) &\Rightarrow a=4,\\ (1 \bmod 4,\ 0 \bmod 3) &\Rightarrow a=9. \end{aligned}$$

So the idempotents modulo \(12\) are \(\{0,1,4,9\}\), and therefore

$$M(12)=9.$$

The same construction for \(n=6=2\cdot 3\) gives the nontrivial idempotents \(3\) and \(4\), hence \(M(6)=4\), matching the standard checkpoint for this problem.

How the Code Works

The C++, Python, and Java implementations begin by building a smallest-prime-factor table up to the limit. That lets them factor each \(n\) quickly and compress repeated prime factors into the prime-power blocks \(q_i\) used in the derivation above.

If an \(n\) has only one distinct prime factor, the implementation immediately adds \(1\). Otherwise it enumerates every nonempty proper subset of the prime-power blocks. To make that fast, it precomputes the product attached to each subset, so each candidate only needs the subset product \(u\), the complementary factor \(v=n/u\), one modular inverse of \(u\) modulo \(v\), and one multiplication to recover \(a_U\). The maximum candidate is then added to the global sum. The Java implementation uses the same per-\(n\) mathematics inside a parallel outer summation.

Complexity Analysis

Building the smallest-prime-factor table with a linear sieve costs \(O(N)\) time and \(O(N)\) memory. For a fixed \(n\), the factorization step is cheap, and the dominant work is enumerating all subsets of the \(k=\omega(n)\) distinct prime factors. That contributes \(O(2^k)\) subset products and \(O(2^k \log n)\) time if the modular inverse is computed with the extended Euclidean algorithm.

A precise overall bound is therefore

$$O\left(N+\sum_{n=2}^{N} 2^{\omega(n)}\log n\right)$$

time and \(O(N)\) memory. For the actual bound \(N=10^7\), one has \(\omega(n)\le 8\), so no number ever needs more than \(2^8-2=254\) nontrivial subset checks. That is why the method is practical even though it explicitly searches all idempotent patterns for each \(n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=407
2. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
3. Idempotent elements: Wikipedia — Idempotent (ring theory)
4. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
5. Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic