【信息安全第三章同余习题】把剩余类1(mod 5)写成模15的剩余类之和

把剩余类1(mod 5)写成模15的剩余类之和。

类似于这个思路。

你可以这么想，15/5=3，(mod 15)=(mod 5)(mod 3)

如果要得到1(mod 5)，需要有3个 1(mod 5)(mod 3)

而在15的能达到这个条件的三个数是1,6,11

所以和就是 1(mod 5)=1(mod 15)+6(mod 15)+11(mod 15).

（个人理解）

26. 如果p是素数,并且p≡3(mod 4),那么[(p-1)/2]!≡±1(mod p)证明

证：
由威尔逊(wilson)定理，
(p-1)!≡-1(mod p), 以下用==表同余。
其中各乘项(分别为1,2,…, p-1) 构成素数p的缩剩余系(或简化剩余系，既约剩余系，简称缩系)。
易见，在缩系的各个剩余类中各取一个代表元，所构成的代表元的连乘积≡-1 mod p.
易见可取这些代表元为 ±1,±2,…,±(p-1)/2, 于是连乘得到
(-1)¹* ([(p-1)/2]!)^2≡-1(mod p),
又p=3 mod 4,故(-1)^{[(p-1)/2)]=(-1)}(1+2t)=-1
([(p-1)/2]!)^2≡1 mod p
故[(p-1)/2]!≡±1(mod p),得证。

例如 由wilson 定理得 6!≡-1 mod 7 ≡1,2,3,-3,-2,-1之积,
从而 (3!)^2 ≡1 mod 7验证了题目的结论：
当p=4k+3，([(p-1)/2]!)^2==1 mod p, [(p-1)/2]!==±1(mod p)

外一则，同理，
当p=4k+1时，([(p-1)/2]!)^2==-1 mod p.
如4!≡-1 mod 5 ≡ 1,2,-2,-1之积, 从而 (2!)^2 == -1 mod 5