请输入您要查询的字词:

 

单词 FactorialModuloPrimePowers
释义

factorial modulo prime powers


For n and any prime numberMathworldPlanetmath p, (n!)p is the productMathworldPlanetmathPlanetmath of numbers 1mn, where pm.

For natural numbersMathworldPlanetmath n,s and a given prime number p, we have the congruenceMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath

n!pi=0dnpii=0d((±1)nps+i(Ni!)p)(modps),

where Ni is the least non-negative residue of npi(modps). Here d+1 denotes the number of digits in the representationof n in base p. More precisely, ±1 is -1 unless p=2,s3.

Proof.

Let i0. Then the set of numbers between 1 andnpi is

{kp,k1,knpi+1}.

This is true for every integer i with pi+1n. So we have

npi!npi+1pnpi+1=(npi!)p.(1)

Multiplying all terms with 0id, where d is the largest power ofp not greater than n, the statement follows from the generalizationPlanetmathPlanetmath ofAnton’s congruence.∎

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:07:53