题目是:给定奇质数p和整数a,求x^2+y^2≡a(modp)的同余解的个数。 我们可以看作传球问题,每次“传球”的动作是加一个平方数。 则其转移矩阵(记为M)满足a(i,j)= 1,i=j;2,i-j为模p的二次剩余;0,i-j为模p的非二次剩余。 我们需要计算M^2。 该矩阵为循环矩阵,因此循环等比数列(公比为p次单位根的p项等比数列)均为其特征向量,它们对应的特征值是p(一重),以及±(-1)^((p-1)/4)*√p(各为(p-1)/2重)。) M^2也为循环矩阵,且其特征值为M的特征值的平方:p^2(一重),以及(-1)^((p-1)/2)*p(p-1重)。 易知,一个由实数组成的循环矩阵若有p-1个特征根相等,则除主对角线以外的所有元素相等。记主对角线上的元素为s,其他元素为t,则有: s+(p-1)t=p^2 s-t=(-1)^((p-1)/2)*p 因此,s=p+(-1)^((p-1)/2)*(p-1),t=p-(-1)^((p-1)/2)。 s对应a为p的倍数时的方法数,t对应a不为p的倍数时的方法数。 |
|