Detailed mathematical approach

Problem Summary

The quantity in this problem is the multiplicative order of

$a=10^9+7$

modulo

$n!=10{,}000{,}000!.$

In other words, we want the smallest positive integer \(R\) such that

$a^R\equiv 1 \pmod{n!},$

and then we report \(R \bmod a\). Because \(a\) is much larger than \(n\), it does not divide \(n!\), so the order is well defined.

The brute-force viewpoint is hopeless. The number \(n!\) is enormous, and the order itself is far beyond direct enumeration. The solution works only because the modulus \(n!\) has a very structured prime-power factorization, and multiplicative orders behave cleanly on prime powers.

Mathematical Approach

The key is to replace one huge congruence modulo \(n!\) by many local congruences modulo prime powers, solve each local problem, and then recombine them through an LCM.

Decomposing \(n!\) into prime powers

For each prime \(q\le n\), let

$e_q=v_q(n!)=\sum_{j\ge 1}\left\lfloor\frac{n}{q^j}\right\rfloor.$

This is Legendre's formula, and it gives the exact exponent of \(q\) in the factorization of \(n!\). Therefore

$n!=\prod_{q\le n} q^{e_q},$

where the product runs over primes.

Since the prime-power factors are pairwise coprime, the Chinese remainder theorem implies that the order modulo the full factorial is the least common multiple of the local orders:

$\operatorname{ord}_{n!}(a)=\operatorname{lcm}_{q\le n} \operatorname{ord}_{q^{e_q}}(a).$

So the problem is reduced to computing \(\operatorname{ord}_{q^{e_q}}(a)\) for every prime \(q\le n\).

The odd-prime local order and its lifting depth

Assume first that \(q\) is odd. Let

$t_q=\operatorname{ord}_q(a).$

By Fermat's little theorem, \(t_q\mid (q-1)\). That is why the implementations start from \(q-1\), factor it, and repeatedly test whether a prime factor can be removed while keeping the congruence \(a^{t_q}\equiv 1 \pmod q\). After all removable factors are stripped away, the remaining value is the exact order modulo \(q\).

The next question is how this order changes when the modulus is lifted from \(q\) to \(q^2,q^3,\dots,q^{e_q}\). Define

$s_q=v_q(a^{t_q}-1).$

This is the first level at which the congruence \(a^{t_q}\equiv 1\) stops being automatic. For odd \(q\), the lifting-the-exponent principle gives

$v_q\!\left(a^{t_q q^m}-1\right)=s_q+m \qquad (m\ge 0).$

Hence the minimal exponent that reaches modulus \(q^{e_q}\) is

$\operatorname{ord}_{q^{e_q}}(a)=t_q\,q^{\max(0,e_q-s_q)}.$

This formula is exactly what the implementations use. They compute \(t_q\), then test whether \(a^{t_q}\equiv 1\) modulo \(q^2,q^3,\dots\) until the lift fails, and the last successful level is \(s_q\).

The special \(2\)-adic branch

The prime \(q=2\) is different because the unit group modulo \(2^e\) does not behave like the odd-prime case. The implementations therefore use explicit \(2\)-adic formulas.

If

$u=v_2(a-1)$

and \(a\equiv 1 \pmod 4\), then \(a\) is already very close to 1 in the \(2\)-adic sense, and

$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e\le u,\\ 2^{e-u}, & e>u. \end{cases}$

If instead

$w=v_2(a+1)$

and \(a\equiv 3 \pmod 4\), then the order must be even once \(e\ge 2\), and the correct formula is

$\operatorname{ord}_{2^e}(a)= \begin{cases} 1, & e=1,\\ 2^{\max(1,e-w)}, & e\ge 2. \end{cases}$

For this problem, \(a=10^9+7\equiv 3 \pmod 4\) and \(v_2(a+1)=3\), so the contribution from the \(2\)-power inside \(n!\) is governed by \(2^{\max(1,e_2-3)}\).

Reassembling the global order from prime exponents

Once every local order \(\operatorname{ord}_{q^{e_q}}(a)\) is known, taking their LCM is still too large to do with ordinary integers. The clean way is to collect prime exponents.

For each prime \(r\le n\), define

$E_r=\max_{q\le n} v_r\!\left(\operatorname{ord}_{q^{e_q}}(a)\right).$

Then

$\operatorname{ord}_{n!}(a)=\prod_{r\le n} r^{E_r}.$

This is why the implementations maintain only a table of maximal exponents. For odd \(q\), the factors coming from \(t_q\) are among the prime divisors of \(q-1\), and the lifting step contributes an extra power of \(q\) itself. No other primes can appear.

Worked Example: \(n=12\)

The smaller case \(n=12\) shows the whole mechanism in a concrete way. First,

$12!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11.$

So we need the orders modulo \(2^{10}\), \(3^5\), \(5^2\), \(7\), and \(11\).

For \(q=2\), we have \(a\equiv 3 \pmod 4\) and \(v_2(a+1)=3\), so

$\operatorname{ord}_{2^{10}}(a)=2^{\max(1,10-3)}=2^7=128.$

For \(q=3\), \(a\equiv -1 \pmod 3\), hence \(t_3=2\). Also \(a\equiv -1 \pmod 9\) but not modulo \(27\), so \(s_3=2\). Therefore

$\operatorname{ord}_{3^5}(a)=2\cdot 3^{5-2}=54.$

For \(q=5\), \(a\equiv 2 \pmod 5\), whose order modulo 5 is \(t_5=4\). Since \(2^4-1=15\), we get \(s_5=1\), and therefore

$\operatorname{ord}_{5^2}(a)=4\cdot 5=20.$

The orders modulo 7 and 11 divide 6 and 10 respectively, so they introduce no new prime powers beyond what is already present in 128, 54, and 20. Hence

$\operatorname{ord}_{12!}(a)=\operatorname{lcm}(128,54,20)=2^7\cdot 3^3\cdot 5=17280.$

This is exactly the kind of local-to-global reconstruction used for the full \(n=10^7\) case.

How the Code Works

Prime preprocessing and factorial valuations

The C++, Python, and Java implementations first build a smallest-prime-factor sieve up to \(n\). That single preprocessing step serves two purposes: it produces the full prime list \(q\le n\), and it allows fast factorizations of numbers like \(q-1\), which are needed when reducing candidate orders.

For each prime \(q\), the implementation evaluates Legendre's formula to obtain \(e_q=v_q(n!)\). This identifies the exact prime-power modulus \(q^{e_q}\) that must be handled.

Computing each local order

When \(q\) is odd, the implementation starts from the candidate \(q-1\), factors it, and removes one prime factor at a time whenever modular exponentiation shows that the smaller exponent still works modulo \(q\). That produces \(t_q=\operatorname{ord}_q(a)\).

Next it determines the lift depth \(s_q\) by testing the same exponent \(t_q\) modulo \(q^2,q^3,\dots\). If the congruence survives to a higher power, the order does not grow yet; once it fails, every additional power of \(q\) in the modulus multiplies the order by \(q\). The implementation records both parts of the factorization: the prime factors of \(t_q\), and the extra \(q\)-power coming from \(e_q-s_q\).

For \(q=2\), the implementation bypasses the odd-prime logic and applies the closed \(2\)-adic formulas directly using \(v_2(a-1)\) or \(v_2(a+1)\), depending on whether \(a\equiv 1\) or \(3 \pmod 4\).

Accumulating the LCM and reducing modulo \(a\)

Instead of forming gigantic local orders and then taking a literal least common multiple, the implementation updates a global table of maximum prime exponents. After all primes \(q\le n\) are processed, the answer is reconstructed as

$\prod_{r\le n} r^{E_r}\pmod a.$

The C++ version uses 128-bit arithmetic for ordinary modular products and switches to multiprecision arithmetic when larger prime powers must be tested exactly. Python gets arbitrary precision automatically, and the Java version uses built-in big integers for the deeper lifting checks.

Complexity Analysis

The sieve up to \(n=10^7\) is \(O(n)\) time and \(O(n)\) memory. This is the dominant storage cost, since both the smallest-prime-factor table and the global exponent table are indexed up to \(n\).

For each prime \(q\le n\), evaluating \(e_q\) costs \(O(\log_q n)\). Factoring \(q-1\) is fast because the sieve is already available, and reducing \(q-1\) to the true order modulo \(q\) requires only a small number of modular exponentiation tests, one for each prime-factor occurrence that might be removed. The lifting phase adds a few more modular exponentiations until the congruence fails at the first unattainable prime power.

So the implementation is best viewed as linear preprocessing plus a per-prime amount of arithmetic that is polylogarithmic in the modulus size. The crucial point is that no part of the algorithm ever tries to build \(n!\) itself or search for the order by repeated multiplication.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=952
2. Multiplicative order: Wikipedia - Multiplicative order
3. Legendre's formula: Wikipedia - Legendre's formula
4. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
5. Lifting-the-exponent lemma: Wikipedia - Lifting-the-exponent lemma
6. Modular exponentiation: Wikipedia - Modular exponentiation