Modulo Power Identity

Let $S(n)$ be the sum of all positive integers $m$ not exceeding $n$ having the following property:
$a^{m + 4} \equiv a \pmod m$ for all integers $a$.

The values of $m \le 100$ that satisfy this property are $1, 2, 3, 5$ and $21$, thus $S(100) = 1+2+3+5+21 = 32$.
You are given $S(10^6) = 22868117$.

Find $S(10^{12})$.

The problem involves residues and modular arithmetic. If a wealth of examples does not surface readily, one can take a cue from the given examples.

First, observe that $1,2,3,5$ are all divisors of $12$. This could suggest that the fact that $m+4 \mid a(a^{m-1}-1) = a^{m}-a$ for all integers $a$ may result from Euler’s totient theorem $\varphi(m)$, where $\varphi(1) = 1, \varphi(2) = 1, \varphi(3) = 2$, and $\varphi(5) = 4$. But $\varphi(21) = 12$, not $21+4=25$, so another form of Carmichael’s function is needed: $\lambda(m)$, the smallest $k$ such that $a^k \equiv 1 \pmod m$ for all $a$ co-prime to $m$. It can be shown that $\lambda(m) \mid \varphi(m)$ for all $m$.

Now, it would suffice to list all positive integers $m \le 10^{12}$ such that $\lambda(m) \mid (m+4)$.

Carmichael’s theorem states that $\lambda(p^{\alpha} q^{\beta} \ldots) = \operatorname{lcm}(\lambda(p^{\alpha}), \lambda(q^{\beta}), \ldots)$ whenever the $p, q, \ldots$ are distinct primes. $\lambda(p^k) = \varphi(p^{k}) = (p^{k}-p^{k-1})$ for all odd primes $p$, or $k \ge 2$, and $\lambda(2)=1$, $\lambda(4)= 2$, and $\lambda(2^k) = 2^{k-2}$ for $k \ge 3.$ Thus the problem can be separated into four cases:

Case 1: $m$ is a power of $2.$ It is easy to see that $2^1,2^2,$ and $2^3$ are the only values that can divide into $m+4 = m+4 \cdot 2^{0}, m+4 \cdot 2^{1}, m+4 \cdot 2^{2},$ respectively, so the sum of values in this case is $2+4+8 = 14$

Case 2: $m$ is a power of an odd prime It can be verified that the only solution in the form of $p^k$ is $3^1 = 3$

Case 3: $m$ is the product of two distinct primes: $pq.$ The only solutions are $3*5 = 15$ and $3*7 = 21,$ for a sum of $36$.

Case 4: $m$ is the product of three distinct primes: $pqr.$ You can check that the only solutions are $3*5*7=105$ and $3*5*11 = 165,$ for a total of $270$

There are no other cases by the forms of $\lambda(m).$

Adding all cases, the sum is $S(10^{12}) = 3 + 14 + 36 + 270 = 323$
Notice that this problem is from AIME so the solution must be an integer from $0$ to $999$ inclusive. Since $S(10^{12})$ results in an number greater than $999$ then the solution must be the sum of the digits, so the answer is $3+2+3 = \boxed{8}$.

This type of problems although couldn’t fall under the traditional topics (Algebra, Trig, Geometry etc), it involves use of Mathematical Theorems like Carmichael Function and Euler’s Phi Function. It’s best for math contests involving non routine problems.

More Answers: