对非负整数0≤m≤n,用C(n, m)= n!/ m!(n-m)! 表示组合数或者二项式系数
对素数p和正整数n,用V(p, n)表示使p^k整除n而p^(k+1)不整除n的非负整数k
用S(p, n)表示在p进制下n的各位数码之和
⑴ Legendre 公式: 对任何素数p和正整数n
V(p, n!) = floor(n/p)+floor(n/p²)+…+floor(n/p^a)
其中a = floor(log n / log p)
floor(x)表示不超过x的最大整数
⑵ Kummer 定理:
① V(p, n!) = (n - S(p, n)) / (p-1)
② V(p, C(n, m)) = (S(p, m)+S(p, n-m)-S(p, n))/(p-1)
V(p, C(n, m)) 正好等于p进制下n-m和m加法中的进位次数,也等于p进制下n减m的借位次数
对素数p和正整数n,用V(p, n)表示使p^k整除n而p^(k+1)不整除n的非负整数k
用S(p, n)表示在p进制下n的各位数码之和
⑴ Legendre 公式: 对任何素数p和正整数n
V(p, n!) = floor(n/p)+floor(n/p²)+…+floor(n/p^a)
其中a = floor(log n / log p)
floor(x)表示不超过x的最大整数
⑵ Kummer 定理:
① V(p, n!) = (n - S(p, n)) / (p-1)
② V(p, C(n, m)) = (S(p, m)+S(p, n-m)-S(p, n))/(p-1)
V(p, C(n, m)) 正好等于p进制下n-m和m加法中的进位次数,也等于p进制下n减m的借位次数