407 : 冪等元

$0 ≤ a ≤ 5$の$a$に対し$a^2 \mod 6$を計算すると、0,1,4,3,4,1 となる。

$a^2 = a \mod 6$を満たす最大の$a$の値は4である。 $a^2 = a \mod n$を満たす$a<n$の最大値を$M(n)$としよう。 つまり$M(6)=4$である。

$1 \leq n \leq 10^7$のときの$\sum M(n)$を求めよ。