设a,b,n为整数,列出n^2(mod4)与a^2+b^2(mod4)的所有可能余数（n^2为n的2次方；a^2为a的2次方；b^2为b的2次方）要完整的证明或算法

Question

设a,b,n为整数,列出n^2(mod4)与a^2+b^2(mod4)的所有可能余数
（n^2为n的2次方；a^2为a的2次方；b^2为b的2次方）
要完整的证明或算法

Answer 1

(1)n^2(mod4)
若n是偶数,则存在整数k使得 n=2k,因此 n^2=4k^2,即 n^2 能被4整除,所以此时 n^2=0(mod4)；
若n是奇数,则存在整数k使得 n=2k+1,因此 n^2=(2k+1)^2=4k^2+4k+1.因为 4k^2 与 4k 均能被4整除,所以必有 n^2=1(mod4).
综上,n^2(mod4)只有两种可能:n是偶数时为0,n是奇数时为1.
(2)a^2+b^2(mod4)
若a,b均为偶数,由(1),a^2,b^2均能被4整除,所以 a^2+b^2 也能被4整除,此时有 a^2+b^2=0(mod4)；
若a,b一奇一偶,不妨设 a 是奇数,b是偶数,那么 a^2=1(mod4),b^2=0(mod4),所以 a^2+b^2=1(mod4)；
若a,b均为奇数,则 a^2=1(mod4),b^2=1(mod4),因此 a^2+b^2=2(mod4).
这就是 a^2+b^2(mod4) 的全部情况.