表达式求和

mathe

我们可以将引理1/2进行推广为
引理5：对于任意奇数\(q\),如果\((h,q)=1\),那么存在整数u,v使得\(u^2+v^2\equiv h\pmod q\).
证明方法同引理2类似，先得出引理1的对应推广结论，再利用类似方法得出，这里就不再详述了。

然后类似引理3证明过程，分别利用\(h\)和\(h^{-1}\)在模\(q=p^s\)下平方和表达形式，证明如果(h,q)=1,那么\(|S_a|=|S_{ah}|\)
然后我们可以得出
\((\sum_{t=0}^{q-1} \omega_q^{t^2})^2 =\sum_{m=0}^{s-1} |S_{p^m}|\varphi(p^{s-m-1})\sum_{(u,p^{s-m})=1}\omega_q^{u p^m}  +|S_{p^s}| \)
容易证明，对于\(m \lt s-1\),都有\(\sum_{(u,p^{s-m})=1}\omega_q^{u p^m}=0\)于是我们得到

引理6: 对于奇素数p的幂\(q=p^s\),\((\sum_{t=0}^{q-1} \omega_q^{t^2})^2 =|S_{p^{s-1}}|\sum_{u=1}^{p-1}\omega_q^{u p^{s-1}}+|S_{p^s}|=|S_{p^s}|-|S_{p^{s-1}}|=|S_{0}|-|S_{p^{s-1}}|\)

mathe

现在我们查看同余方程\(x^2+y^2\equiv 0\pmod q\)解的数目，其中q为奇素数的幂\(p^s\)。
首先容易证明，同余方程\(x^2\equiv -1 \pmod q\)对于\(p\equiv 3\pmod 4\)无解，对于\(p \equiv 1 \pmod 4\)正好存在两组解。
i) \(p \equiv 3 \pmod 4\):
   很显然只能\(x^2 \equiv y^2 \equiv 0 \pmod q\),
    所以通解为\(x \equiv u p^{\lfloor\frac{s+1}2\rfloor}, y \equiv v p^{\lfloor\frac{s+1}2\rfloor}, 0\le u \lt p^{s-\lfloor\frac{s+1}2\rfloor}, 0\le v \lt p^{s-\lfloor\frac{s+1}2\rfloor}\)
   所以解的数目为\(|S_0|=p^{2s-2\lfloor\frac{s+1}2\rfloor}\).
   于是\((p-1)|S_{p^{s-1}}|+|S_0|=p^2(p^{2s-2-2\lfloor\frac{s}2\rfloor})\)
  所以解的数目为\(|S_0|=p^{2s-2\lfloor\frac{s+1}2\rfloor}\).
   于是\((p-1)|S_{p^{s-1}}|=p^2(p^{2s-2-2\lfloor\frac s2\rfloor})-p^{2s-2\lfloor\frac{s+1}2\rfloor}=p^{2s-2\lfloor\frac s2\rfloor}-p^{2s-2\lfloor\frac{s+1}2\rfloor}\)
   容易看出s为偶数时\(|S_{p^{s-1}}|=0\), 而s为奇数时， \(|S_{p^{s-1}}|=p^{s-1}(p+1)\)
所以s为偶数时\(|S_{p^{s-1}}|-|S_0|=-p^s\),
   而s为奇数时,\(|S_{p^{s-1}}|-|S_0|=p^{s-1}(p+1)-p^{s-1}=p^s\)

ii) \(p \equiv 1 \pmod 4\):
   这时存在\(a^2 \equiv -1 \pmod q\), 并且只有a,-a这两个同余类的平方为-1.
  所以\(x^2+y^2 \equiv 0\pmod q\), 要么这个解如同i)中情况，
    对于另外一类，我们要求\(0 \le h \le \lfloor \frac{s-1}2\rfloor,  0\le u \lt p^{s-h}, 0\le v \lt p^{s-h}, (u,p)=1,x=up^h,y=vp^h\),
   而且\(u^2+v^2 \equiv 0 \pmod {p^{s-2h}}\), 我们知道这样的u,v在 \(0 \le u \lt p^{s-2h}, 0\le v \lt p^{s-2h}, (u,p)=1,(v,p)=1\)中有\(2 \varphi(p^{s-2h})=2p^{s-2h-1}(p-1) \)组。
  所以在  \(0\le u \lt p^{s-h}, 0\le v \lt p^{s-h}, (u,p)=1,(v,p)=1\)中共有\(2p^{s-1}(p-1)\)组解。
    所以这一类解的数目为\(2\sum_{h=0}^{\lfloor \frac{s-1}2\rfloor} p^{s-1}(p-1)=2\lfloor\frac{s+1}2\rfloor p^{s-1}(p-1)\)
得到\(|S_0|=2\lfloor\frac{s+1}2\rfloor p^{s-1}(p-1)+p^{2s-2\lfloor\frac{s+1}2\rfloor}\)

     于是\((p-1)|S_{p^{s-1}}|+|S_0|=p^2(p^{2s-2-2\lfloor\frac{s}2\rfloor}+2\lfloor\frac{s}2\rfloor p^{s-2}(p-1))=p^{2s-2\lfloor\frac{s}2\rfloor}+2\lfloor\frac s2\rfloor p^s(p-1)\)

解得\(|S_{p^{s-1}}|-|S_0|=\frac{p^{2s-2\lfloor\frac{s}2\rfloor}+2\lfloor\frac s2\rfloor p^s(p-1)-2\lfloor\frac{s+1}2\rfloor p^{s}(p-1)-p^{2s+1-2\lfloor\frac{s+1}2\rfloor}}{p-1}\)
于是s为偶数时\(|S_{p^{s-1}}|-|S_0|=\frac{p^s+sp^s(p-1)-sp^{s}(p-1)-p^{s+1}}{p-1}=-p^s\)
而s为奇数时\(|S_{p^{s-1}}|-|S_0|=\frac{p^{s+1}+(s-1)p^{s}(p-1)-(s+1)p^s(p-1)-p^s}{p-1}=-p^s\)

由此根据引理6证明了n是奇素数的幂时，题目是成立。我们只需要再计算n=2,4,8题目也成立，然后这个表达式求和问题就可以完全解决了。
由此结合引理4b，这个表达式问题最终获得证明。

mathe

https://zhuanlan.zhihu.com/p/564 ... 1936452557804410435

mathe

前面提到引理4应该有问题，我们改为
引理4b： 如果\((m,n)=1\), 那么\((\sum_{s=0}^{m-1}\omega_m^{s^2}\sum_{t=0}^{n-1}\omega_n^{t^2})^2=(\sum_{s=0}^{mn-1} \omega_{mn}^{s^2})^2\).

证明如下:
定义\(S_{m,u}\)为\(\{(a,b)|a^2+b^2=u \pmod m, 0\le a\lt m,0\le b\lt m\}\)
\((\sum_{s=0}^{m-1}\omega_m^{s^2})^2(\sum_{t=0}^{n-1}\omega_n^{t^2})^2=\sum_{u=0}^{m-1}\sum_{v=0}^{m-1}\omega_m^{u^2+v^2}\sum_{s=0}^{n-1}\sum_{t=0}^{n-1}\omega_n^{s^2+t^2}=\sum_{u=0}^{m-1}|S_{m,u}|\omega_m^u\sum_{v=0}^{n-1}|S_{n,v}|\omega_n^v\)
根据引理5，由于(m,n)=1, 我们知道\(|S_{m,u}|=|S_{m,nu}|, |S_{n,v}|=|S_{n,mv}|\)
由此得到
\((\sum_{s=0}^{m-1}\omega_m^{s^2})^2(\sum_{t=0}^{n-1}\omega_n^{t^2})^2=\sum_{u=0}^{m-1}|S_{m,nu}|\omega_m^u\sum_{v=0}^{n-1}|S_{n,mv}|\omega_n^v=\sum_{u=0}^{m-1}\sum_{v=0}^{m-1}\omega_m^{n(u^2+v^2)}\sum_{s=0}^{n-1}\sum_{t=0}^{n-1}\omega_n^{m(s^2+t^2)}=(\sum_{u=0}^{m-1}\omega_{m}^{nu^2})^2(\sum_{s=0}^{n-1}\omega_n^{ms^2})^2=(\sum_{u=0}^{m-1}\sum_{s=0}^{n-1}\omega_{mn}^{n^2u^2+m^2s^2+2mnus})^2=(\sum_{u=0}^{mn-1}\omega_{mn}^{u^2})^2\)