平方余数

令$r(a,n)$为$(a-1)^n+(a+1)^n$模$a^2$的余数，例如$a=7$，$n=3$有 $$r(7,3)\equiv (7-1)^3+(7+1)^3\equiv 6^3+8^3\equiv 728\equiv 42 \pmod {49},$$ 显然r的值会随n而变化，不过对$a=7$而言有 $$\max_{n}r(7,n)=42.$$ 求 $$\sum_{a=3}^{1000}\max_{n}r(a,n).$$

本题难度:

解答

令$f(a,n)=(a-1)^n+(a+1)^n$，则有 $$f(a,n)=(a-1)^n+(a+1)^n=2\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}a^{n-2k},$$ 因此若n为偶数，则有 $$f(a,n)\equiv2 \pmod {a^2},$$ 若$n$为奇数，则有 $$f(a,n)\equiv2a\binom{n}{n-1}=2an \pmod {a^2}.$$ 若$a$是奇数，则$a\mapsto 2na$是加法循环群$\mathbb Z_{a^2}$中的子群$a\mathbb Z_a$上的自同构，因此存在合适的素数n能将a在$\mathbb Z_{a^2}$中映射为$a^2-a$，这是该子群中的最大元素，也是$r(a,n)$能取到的最大值。 若$a$是偶数，则$2a\mapsto 2an$是加法循环群$\mathbb Z_{a^2}$中的子群$2a\mathbb Z_{a/2}$上的自同构， 因此也存在合适的素数n能将a在$\mathbb Z_{a^2}$中映射为$a^2-2a$，这是该子群中的最大元素，也是此时$r(a,n)$能取到的最大值。 从而结果为 \begin{align*} &\left(\sum_{j=1}^{499}(2j+1)^2-(2j+1)\right)+\left(\sum_{k=2}^{500}(2k)^2-4k\right) \\ =&(\frac{1000(1000+1)(2000+1)}{6}-1^2-2^2)-\frac{998(1000+3)}{2}-\frac{499(1000+4)}{2} \\ =&333833495-500497-250498 \\ =&333082500. \end{align*} 本题无需编程。 本题涉及的代数知识一般需要在本科及以上的数学系《抽象代数》一类的课程中学习，不具备相关知识的读者也可以通过编程自行找到$r(a,n)$随着n增加而周期性变化的规律。