证明 x^b = x mod p 的解的个数是 gcd(b-1,p-1).
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/12 23:31:37
证明 x^b = x mod p 的解的个数是 gcd(b-1,p-1).
如题
如题
设 g是mod p意义下的一个原根. 则 g^(p-1)=1 mod p
且对于 k=1,2...p-2: g^k不=1 mod p
接下来,当p不整除x时:
可设x=g^y mod p
原方程化为 by=y mod (p-1) (y=1,2...p-1)
即 (b-1)y=0 mod (p-1)
即 (b-1)/gcd(b-1,p-1) ·y=0 mod (p-1)/gcd(b-1,p-1)
即 y=0 mod (p-1)/gcd(b-1,p-1)
这个方程在y=1,2...p-1下恰有gcd(b-1,p-1)个解
所以x^b=x mod p 的解应该有gcd(b-1,p-1)+1个,gcd(b-1,p-1)个是指非零的
且对于 k=1,2...p-2: g^k不=1 mod p
接下来,当p不整除x时:
可设x=g^y mod p
原方程化为 by=y mod (p-1) (y=1,2...p-1)
即 (b-1)y=0 mod (p-1)
即 (b-1)/gcd(b-1,p-1) ·y=0 mod (p-1)/gcd(b-1,p-1)
即 y=0 mod (p-1)/gcd(b-1,p-1)
这个方程在y=1,2...p-1下恰有gcd(b-1,p-1)个解
所以x^b=x mod p 的解应该有gcd(b-1,p-1)+1个,gcd(b-1,p-1)个是指非零的
证明 x^b = x mod p 的解的个数是 gcd(b-1,p-1).
一个简单的数论证明P是一个质数,求证 x^b=x mod p 有 gcd(p-1,b-1)个解?我一不小心开出了两个一样
初等数论证明:x^b=x mod p 解的个数
请证明:p==1(mod)x
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
r是奇数质数p的原根 证明x^2≡r(mod p)无解
如果gcd(a b)=1 ,证明gcd(ab,c)=gcd(a,c)*gcd(b,c) 怎么证阿
初等数论同余问题p为质数,0<a<p,证明x≡b×(-1)∧(a-1)×(p-1)···(p-a+1)/a!(mod p
求ax ≡ 1 (mod b)中的x(a,b已知互质,即x有解) 即求ax=1+by 为什么可用ax+by=gcd(a,
一个多项式 p(x)=(x-b)^7*Q(x) 1 证明p(b)=p'(b)=0 2由此.找到a 和b 如果 (x-1)
p(x)为F上的不可约多项式,存在a0,使得p(a)=0,p(1/a)=0;证明任意b,如果p(b)=0,则p(1/b)
ax ≡ 1 (mod b)与ax+by=gcd(a,b)有何关系?