证明：259！+1 能被 269 整除

myyour

259的阶乘+1，证明这个数能被269整除。
能用笔算吗？

luyuanhong

题  证明：259！+1 能被 269 整除。

证  首先，我们知道，有一个 Wilson 定理：

    若 p 是一个素数，则 (p-1)!+1 必定能被 p 整除。

    例如：

    p=3 是一个素数，(p-1)!+1=(3-1)!+1=2!+1=2+1=3 能被 3 整除。

    p=5 是一个素数，(p-1)!+1=(5-1)!+1=4!+1=24+1=25 能被 5 整除。

    p=7 是一个素数，(p-1)!+1=(7-1)!+1=6!+1=720+1=721 能被 7 整除。

    在本题中，269 是一个素数，所以由 Wilson 定理可知：

    (269-1)!+1=268!+1 必定能被 269 整除。

          (268!+1)-(259!+1)=268!-259!

    =268×267×265×264×263×262×261×260×259!-259!

    =(268×267×265×264×263×262×261×260-1)×259!

    =(6226563019026776025600-1)×259!

    =6226563019026776025599×259!

    =269×23147074420173888571×259!

    可见，(268!+1)-(259!+1) 也能被 269 整除。

    所以，259!+1=(268!+1)-[(268!+1)-(259!+1)] 也必定能被 269 整除。

王守恩

luyuanhong 发表于 2021-4-27 17:34
题  证明：259！+1 能被 269 整除。

证  首先，我们知道，有一个 Wilson 定理：

259!+1=259!+1-268!-1+268!+1

=268!+1-(268!+1-259!-1)=268!-259!

=268×267×266×265×264×263×262×261×260×259!-259!

=(268×267×266×265×264×263×262×261×260-1)×259!

=(269-1)×(269-2)×(269-3)×(269-4)×(269-5)×(269-6)×(269-7)×(269-8)×260-1

=(1×2)×(3×4)×(5×6)×(7×8)×(269-9)-1

=9!+1=362881=1349×269

波斯猫猫

luyuanhong 发表于 2021-4-27 17:34
题  证明：259！+1 能被 269 整除。

证  首先，我们知道，有一个 Wilson 定理：

259!+1=259!+1-268!-1+268!+1

=268!+1-(268!+1-259!-1)=268!-259!      （！？）

王守恩

波斯猫猫 发表于 2021-4-27 20:54
luyuanhong 发表于 2021-4-27 17:34
题  证明：259！+1 能被 269 整除。

每一步的余数不变。

259!+1≡259!+1-268!-1+268!+1

≡268!+1-(268!+1-259!-1)≡268!-259!

≡268×267×266×265×264×263×262×261×260×259!-259!

≡(268×267×266×265×264×263×262×261×260-1)×259!

≡(269-1)×(269-2)×(269-3)×(269-4)×(269-5)×(269-6)×(269-7)×(269-8)×260-1

≡(1×2)×(3×4)×(5×6)×(7×8)×(269-9)-1

≡9!+1≡362881≡1349×269≡0  (mod 269)

luyuanhong

楼上 王守恩 的解答很好！已收藏。

awei

威尔逊定理简单证明：
在模p的简化剩余系F={1,2,3,……p-1}中，
{a，b}∈F，如果ab≡1 （mod p）
，那么a和b对于模p互为乘法逆元。
①除了1和p-1对于模p的乘法逆元是自身。
集合F中的其余元素对于模p的乘法逆元不是自身。
a^2≡1 （mod p），a只能是1或者-1。

②模p简化剩余系乘法逆元的唯一性。
假设{b,c}∈F，b≠c，ab≡1 （mod p），ac≡1 （mod p）
得ab≡ac (mod p)→abb≡abc （mod p)→b≡c （mod p)→b=c
由于b和c属于简化剩余系，又同余所以a和c只能相等,
与假设矛盾，故唯乘法逆元一性合理。

③由模p简化剩余系乘法逆元的唯一性，
即②，可以得出模p的简化剩余系中，
除了1和p-1外，互为乘法逆元的元素，两两成对，且各不相同。

④(p-1)!≡1×[2×3×4……×(p-2)]×(p-1)  (mod p)
中括号里的有p-2个，(p-2)/2对互为乘法逆元的数，
故(p-1)!≡1×1×(-1) ≡-1 (mod p）
这就是威尔逊定理的数学原理。