试求整数 ∑(0≤i＜j≤111)C(111,i)C(111,j) 除以 29 的余数

wintex

试求整数 ∑(0≤i＜j≤111)C(111,i)C(111,j) 除以 29 的余数

wintex

wintex 发表于 2022-10-13 20:00
想請問

想請問

luyuanhong

wintex

luyuanhong 发表于 2022-10-16 18:36

老師這紅色是為什麼

luyuanhong

wintex 发表于 2022-10-16 21:01
老師這紅色是為什麼

在第 3 楼我的帖子中已经说过了：

因为 C(222,111) /2  必定是 29 的倍数，所以 C(222,111) /2 除以 29 的余数必定是 0 。

所以求 2^221-C(222,111)/2 除以 29 的余数，只需要求 2^221 除以 29 的余数就可以了。

lihp2020

1
C(222,111) 能被29 整除 不能用连续来说明
应该这样
29 是个 质数
222/29=7.58
也就是说 222!其中能被29^7整除 不能被29^8整除
同理
111/29=3.82
222!其中能被29^3整除 不能被29^4整除
222!/（111!^2） 上下约分 还能剩下一个29
所以能被29整除
这个要写出来 好些
lg： 这个数就不能被47整除
2
2^221关于29 求余数
1 用费马小定理 或者欧拉函数 2^28-1|29
可以得到2^a 和2^(a-k*28）关于29同余
也就是求2^25关于29的余数？？
手撸
2^25 =1024*1024*32
    = 9*9*3
        =81*3
        =23*3
        =69
        =11
（其中有些= 意思是同余号）

luyuanhong

楼上 lihp2020 的推导证明很好！

我已根据楼上帖子的思路，对我第 3 楼中的解法作了补充更正。