Idempotents

If we calculate $a^2 \bmod 6$ for $0 \leq a \leq 5$ we get: $0,1,4,3,4,1$.

The largest value of $a$ such that $a^2 \equiv a \bmod 6$ is $4$.
Let’s call $M(n)$ the largest value of $a \lt n$ such that $a^2 \equiv a \pmod n$.
So $M(6) = 4$.

Find $\sum M(n)$ for $1 \leq n \leq 10^7$.

First, let’s observe the properties of $M(n)$ for some small values of $n$.

– $M(1) = 0$ since $a < 1$ means $a$ can only be $0$, hence no $a^2 \equiv a \pmod{1}$. - $M(2) = 1$ since $a = 1$ is the largest value such that $1^2 \equiv 1 \pmod{2}$. - For even values of $n > 2$: since $a^2 – a = a(a-1)$, $n \cdot k = a(a-1)$ for some $k \in \mathbb{Z}^+$. It is easy to notice that $(a=2,n=2)$ or $(a=n-2, n=n)$ are the largest possible solutions, because if we increase $a$ further it jumps over $n$. So, $M(n) = n – 2$ for $n > 2$ and even.
– Let’s check the case of $n$ being an odd prime $p$. Then $p$ divides $a(a-1)$, so according to the property of primes either $p$ divides $a$ or $a-1$. If $p$ divides $a$, then $a = p \cdot k$ for some integer $k$, but since $a < p$, it follows that $k=0$ which gives $a=0$, but $0^2 \neq 0 \pmod{p}$ because $p$ is a prime number. If $p$ divides $a-1$, then $a-1 = p \cdot k$, and $k=1$ satisfies $a=p-1$ which is less than $p$ . So in the case of prime $p$, $M(p) = p - 1$. - For $n = p^k$ where $p$ is a prime number and $k \geq 2$, similar to above, $n | a(a - 1)$, so $p \leq a \leq p^2 - 1$. Beyond $p^2 - 1$, if $a$ increments, $a(a-1)$ increments much faster and will exceed $n = p^k$, hence $M(n) = min(p^k - 2, p^2 - 1) = p^k - 2$. - For odd non-primes we can apply unique prime factorization and show that $M(n) = n - 2$. To find $\sum_{n=1}^{10^7} M(n)$, for each $n \leq 10^7$, add $M(n)$ to a running total. For even values $n$, $M(n) = n - 2$. For odd primes $n$, $M(n) = n - 1$. For powers of primes $n$, $M(n) = n - 2$. For all other odd numbers which are not primes or powers of primes, $M(n) = n - 2$. The sum would be obtained with a function or algorithm iterating through the numbers up to $10^7$, identifying each number type, and adding the corresponding $M(n)$. However, due to the large number of iterations, computing this directly may be resource and time-consuming. Since this touches on concepts of number theory, and the range is until $10^7$, you would most likely need a computer algorithm utilizing efficient prime checking and factorization methods to solve this in a reasonable amount of time. Specifically, you would start by generating a list of primes up to $10^7$, then iterate over the range, and for each number, you check if it's even, a prime, a power of a prime or an odd non-prime and add corresponding $M(n)$ values. For an analytical approach to this problem, you might be able to use ideas from analytic number theory, such as the Prime Number Theorem or Dirichlet's theorem, to estimate the number of prime numbers or the number of prime powers in the interval, which might help compute the sum more directly; it would be a more complex route, and it's outside of the domain of a general high-school level math, requiring an understanding of analysis and number theory at the undergraduate/graduate level.

More Answers: