Detailed mathematical approach

Problem Summary

For integers \(n\) and \(m\), define \(f(n,m)\) as the smallest nonnegative integer \(x\) satisfying

$x \equiv \varphi(n)\pmod{n}, \qquad x \equiv \varphi(m)\pmod{m},$

and define \(f(n,m)=0\) when the system has no solution. The problem asks for

$\sum_{10^6 \le n \lt m \lt 1005000} f(n,m).$

A brute-force search over candidate values of \(x\) would be hopeless. The efficient route is to precompute Euler's totient function once, then solve each pair with the Chinese Remainder Theorem in its non-coprime form.

Mathematical Approach

For one pair \((n,m)\), write

$a=\varphi(n), \qquad b=\varphi(m).$

We must find the least nonnegative solution of

$x \equiv a \pmod{n}, \qquad x \equiv b \pmod{m}.$

The full sum is obtained by evaluating this quantity for every pair in the interval and adding the results.

Step 1: Precompute the Totient Values

The only residues that ever appear are \(\varphi(n)\) and \(\varphi(m)\), so the first job is to compute \(\varphi(k)\) for all \(k < 1005000\).

The sieve used by the implementation is the standard totient sieve: start with \(\varphi(k)=k\), and for each prime \(p\), update every multiple \(q\) of \(p\) by

$\varphi(q)\leftarrow \varphi(q)-\frac{\varphi(q)}{p}=\varphi(q)\left(1-\frac{1}{p}\right).$

After this preprocessing, every pair \((n,m)\) immediately gives the two residues \(a\) and \(b\).

Step 2: Determine When the Two Congruences Are Compatible

If \(x\) satisfies both congruences, then for some integers \(u\) and \(v\),

$x=a+nu=b+mv.$

Subtracting the two expressions gives the linear Diophantine equation

$nu-mv=b-a.$

Let

$g=\gcd(n,m).$

A standard theorem for linear Diophantine equations says that this equation has an integer solution if and only if \(g\) divides the right-hand side. Therefore the CRT system is solvable exactly when

$g \mid (b-a),$

or equivalently

$a \equiv b \pmod{g}.$

If this compatibility test fails, then \(f(n,m)=0\).

Step 3: Reduce the Problem to a Coprime Congruence

Assume the divisibility condition holds. Write

$n=gn_1, \qquad m=gm_1,$

so that \(\gcd(n_1,m_1)=1\). Dividing the linear equation by \(g\) gives

$n_1u-m_1v=\frac{b-a}{g}.$

Reducing this relation modulo \(m_1\) eliminates the term containing \(v\) and leaves

$n_1u \equiv \frac{b-a}{g}\pmod{m_1}.$

Because \(n_1\) and \(m_1\) are coprime, \(n_1\) has a modular inverse modulo \(m_1\). Hence

$u \equiv \frac{b-a}{g}\,n_1^{-1}\pmod{m_1}.$

This is the key simplification: one non-coprime CRT system becomes one ordinary modular inverse problem.

Step 4: Reconstruct the Smallest Nonnegative Solution

Choose the unique representative \(u_0\) with

$0 \le u_0 < m_1$

that satisfies the congruence above. Then

$x=a+nu_0$

solves the original system.

Why is this the smallest nonnegative solution? First, \(0 \le a < n\) for every relevant \(n\), so

$0 \le x < n+n(m_1-1)=nm_1=\operatorname{lcm}(n,m).$

Second, all solutions to the CRT system are congruent modulo \(\operatorname{lcm}(n,m)\). Therefore the representative lying in

$[0,\operatorname{lcm}(n,m))$

is exactly the least nonnegative one.

Step 5: Worked Example

Take the actual pair \((n,m)=(4,6)\). Then

$\varphi(4)=2, \qquad \varphi(6)=2.$

So we solve

$x \equiv 2 \pmod{4}, \qquad x \equiv 2 \pmod{6}.$

Here \(g=\gcd(4,6)=2\), and \(2-2=0\) is divisible by \(2\), so the system is solvable. We have

$n_1=2, \qquad m_1=3, \qquad \frac{b-a}{g}=0,$

hence

$2u \equiv 0 \pmod{3},$

so \(u_0=0\). Therefore

$f(4,6)=x=2+4\cdot 0=2.$

For a nontrivial shift with the same moduli, the system

$x \equiv 2 \pmod{4}, \qquad x \equiv 4 \pmod{6}$

leads to

$2u \equiv 1 \pmod{3}.$

The inverse of \(2\) modulo \(3\) is \(2\), so \(u_0 \equiv 2 \pmod{3}\), giving

$x=2+4\cdot 2=10.$

This matches the checkpoint used by the implementations and shows how the reduced congruence produces the minimal CRT solution directly.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they build a totient table up to the upper bound of the interval. Then they extract the 5000 relevant numbers \(n\) together with their totients so that the double loop only reads precomputed values.

For each pair \(n<m\), the implementation computes \(a=\varphi(n)\), \(b=\varphi(m)\), and \(g=\gcd(n,m)\). If \(a\not\equiv b\pmod{g}\), the pair contributes \(0\) and the loop moves on immediately.

Otherwise, the code divides by \(g\), uses the extended Euclidean algorithm to obtain the inverse of \(n/g\) modulo \(m/g\), normalizes the residue into the range \(0 \le u_0 < m/g\), and forms

$x=a+nu_0.$

The running total is accumulated in an integer type wide enough for the full answer, because the final sum is larger than what a signed 64-bit integer can safely hold.

Complexity Analysis

Let \(L=10^6\), \(R=1005000\), and \(N=R-L=5000\). The totient sieve up to \(R-1\) costs

$O(R\log\log R)$

time and \(O(R)\) memory.

The pair loop evaluates

$\binom{5000}{2}=12{,}497{,}500$

CRT systems. Each one performs a gcd computation and one extended-Euclid solve on integers of size \(O(R)\), so its arithmetic cost is \(O(\log R)\). The total running time is therefore

$O(R\log\log R + N^2\log R),$

with \(O(R)\) memory overall. The important point is that the quadratic factor comes from only 5000 values, not from one million values.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=531
2. Chinese Remainder Theorem: Wikipedia — Chinese Remainder Theorem
3. Euler's totient function: Wikipedia — Euler's totient function
4. Extended Euclidean algorithm: Wikipedia — Extended Euclidean algorithm
5. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse