Detailed mathematical approach

Problem Summary

We work with the RSA modulus \(n=pq\) for the specific primes \(p=1009\) and \(q=3643\). A public exponent \(e\) is valid when

$1 \lt e \lt \varphi(n),\qquad \gcd(e,\varphi(n))=1,\qquad \varphi(n)=(p-1)(q-1).$

A message \(m\in\{0,1,\dots,n-1\}\) is called unconcealed if encryption leaves it unchanged:

$m^e \equiv m \pmod n.$

The goal is to find all valid exponents that minimize the number of unconcealed messages and then add those exponents together.

Mathematical Approach

The important observation is that we never need to test every message for every exponent. For a fixed \(e\), the number of fixed points of the map \(x\mapsto x^e \pmod n\) has a simple closed form, and that form depends only on two gcd values.

Counting fixed points modulo one prime

First work modulo a prime \(r\), where \(r\) is either \(p\) or \(q\). The congruence

$x^e \equiv x \pmod r$

can be rewritten as

$x(x^{e-1}-1)\equiv 0 \pmod r.$

So every solution is either \(x=0\) or a nonzero residue satisfying \(x^{e-1}=1\). The nonzero residues modulo \(r\) form a cyclic multiplicative group of size \(r-1\). In a cyclic group of order \(r-1\), the equation \(y^k=1\) has exactly \(\gcd(k,r-1)\) solutions. Therefore the number of unconcealed residues modulo \(r\) is

$N_r(e)=\gcd(e-1,r-1)+1.$

The extra \(+1\) is the zero solution.

Combining the two prime moduli

A residue class modulo \(n=pq\) is unconcealed exactly when its reductions modulo \(p\) and modulo \(q\) are both unconcealed. Because \(p\) and \(q\) are distinct primes, the Chinese Remainder Theorem gives a one-to-one correspondence between pairs of residues modulo \(p\) and \(q\) and residues modulo \(n\). Hence

$N(e)=N_p(e)N_q(e)=\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big).$

This is the central invariant of the problem. Once it is known, the original task is no longer about testing messages; it is about understanding how small the two gcd factors can be.

A universal lower bound for valid exponents

Since \(p\) and \(q\) are odd primes, both \(p-1\) and \(q-1\) are even, so \(\varphi(n)\) is even as well. Any valid RSA exponent must satisfy \(\gcd(e,\varphi(n))=1\), which forces \(e\) to be odd. Therefore \(e-1\) is even, and both gcd terms are at least 2:

$\gcd(e-1,p-1)\ge 2,\qquad \gcd(e-1,q-1)\ge 2.$

That immediately yields

$N(e)\ge (2+1)(2+1)=9.$

So 9 is the smallest unconcealed-message count any valid exponent could possibly have. The remaining question is whether the concrete primes \(1009\) and \(3643\) actually allow this lower bound to be reached.

Specializing to \(p=1009\) and \(q=3643\)

For the problem data we have

$p-1=1008=2^4\cdot 3^2\cdot 7,\qquad q-1=3642=2\cdot 3\cdot 607.$

To attain the lower bound 9, both gcd factors must be exactly 2. So the optimal exponents are precisely the valid \(e\) such that

$\gcd(e-1,1008)=2,\qquad \gcd(e-1,3642)=2.$

Equivalently, \(e-1\) must be even but not divisible by any of the odd prime factors \(3\), \(7\), or \(607\). This description is mathematically sharper than a brute-force message count, but it is the same quantity the implementation evaluates for every candidate exponent.

Worked examples

The sample mentioned in the problem statement uses \(p=19\), \(q=37\), and \(e=181\). Then

$\gcd(180,18)=18,\qquad \gcd(180,36)=36,$

so

$N(181)=(18+1)(36+1)=703=19\cdot 37.$

In other words, every message is unconcealed in that sample.

For the actual target primes, take \(e=11\). It is valid because \(\gcd(11,\varphi(n))=1\), and

$\gcd(10,1008)=2,\qquad \gcd(10,3642)=2.$

Therefore

$N(11)=(2+1)(2+1)=9,$

so the lower bound is attained. By contrast, \(e=5\) is also valid, but

$\gcd(4,1008)=4,\qquad \gcd(4,3642)=2,$

which gives \(N(5)=15\). This makes the optimization criterion completely explicit: minimize the gcd factors, not the size of \(e\).

How the Code Works

The C++, Python, and Java implementations all follow the same compact strategy. They fix the two primes, compute \(\varphi(n)=(p-1)(q-1)\), and iterate through every integer \(e\) with \(2 \le e \lt \varphi(n)\).

Inside that loop, the RSA validity condition is checked first: only exponents with \(\gcd(e,\varphi(n))=1\) are kept. For each valid exponent, the implementation evaluates

$\big(\gcd(e-1,p-1)+1\big)\big(\gcd(e-1,q-1)+1\big)$

directly, compares it with the best value seen so far, and updates the running sum of exponents that achieve the current minimum.

The C++ implementation also performs small sanity checks before the final scan. It compares the closed form with brute-force modular exponentiation on tiny prime pairs and confirms the stated sample count for \(p=19\), \(q=37\), and \(e=181\). Those checks do not alter the main algorithm; they only verify that the formula matches the underlying RSA fixed-point count.

Complexity Analysis

There are \(\varphi(n)-2\) candidates in the outer scan. Each candidate requires only a constant number of gcd computations, and each gcd uses the Euclidean algorithm in \(O(\log n)\) time. The total running time is therefore

$O(\varphi(n)\log n).$

The extra memory usage is \(O(1)\), since the implementation stores only a few integers for the current candidate, the best unconcealed count, and the accumulated sum. This is far better than checking all \(n\) messages for every valid exponent.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=182
2. RSA cryptosystem: Wikipedia - RSA (cryptosystem)
3. Chinese Remainder Theorem: Wikipedia - Chinese remainder theorem
4. Cyclic groups: Wikipedia - Cyclic group
5. Greatest common divisor: Wikipedia - Greatest common divisor
6. Euler's totient function: Wikipedia - Euler's totient function