数论关于同余的题目

n如果是素数的话直接取k = 1就行, n | (n-1)!+1是Wilson定理.
证明可以用配对: 由n是素数, mod n的既约剩余系为1, 2,..., n-1.
任意x = 1, 2,..., n-1, 存在唯一的即约剩余类y使xy = 1 (mod n).
由此将1, 2,..., n-1两两配对, 其中1和n-1分别与自身配对, 剩下的两两相乘 = 1 (mod n).
于是(n-1)! = 1·(n-1) = -1 (mod n), 即n | (n-1)!+1.

2.(i) 在mod p意义下, 有等式:
2 = -(p-2),
4 = -(p-4),
...
p-1 = -1.
相乘得(p-1)!! = (-1)^((p-1)/2)·(p-2)!! (mod p).
两边乘(p-1)!!即得((p-1)!!)² = (-1)^((p-1)/2)·(p-1)! = (-1)^((p+1)/2) (mod p) (用到Wilson定理).
(ii) 从(i)的结论中提出因子2得2^(p-1)·(((p-1)/2)!)² = (-1)^((p+1)/2) (mod p).
p是奇素数, 由Fermat小定理, 2^(p-1) = 1 (mod p), 即得结论.
(iii) 已在(i)中证明.

4. 既然做这个题应该知道中国剩余定理.
考虑同余方程组x = -i (mod a_i), i = 1, 2,..., k.
由a_1, a_2,..., a_k两两互素, 根据中国剩余定理, 上述方程组有解.
若b为解, 则a_i | b+i, i = 1, 2,..., k. 即b+1, b+2,..., b+k满足要求.