设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/27 18:05:37
![设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.](/uploads/image/z/3701040-24-0.jpg?t=%E8%AE%BEn%E6%98%AF%E6%AD%A3%E6%95%B4%E6%95%B0%2Cp%E6%98%AF%E7%B4%A0%E6%95%B0%2C%28n%2Cp%26%238722%3B1%EF%BC%89%3Dk%2C%E8%AF%81%E6%98%8E%E5%90%8C%E4%BD%99%E6%96%B9%E7%A8%8Bx%5En%E2%89%A11%28mod+p%29%E6%9C%89k%E4%B8%AA%E8%A7%A3.)
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
设n是正整数,p是素数,(n,p−1)=k,证明同余方程x^n≡1(mod p)有k个解.
对素数p,存在原根g.
即g^i ≡ 1 (mod p),当且仅当i是p-1的倍数.
由此,对i = 0,1,2,...,p-2,g^i (mod p)两两不同余,
即mod p恰好取遍1,2,...,p-1.
显然,x = 0不是x^n ≡ 1 (mod p )的解.
对x = 1,2,...,p-1,存在i = 0,1,2,...,p-2,使x ≡ g^i (mod p).
于是x^n ≡ g^(ni) (mod p).
x^n ≡ 1 (mod p)当且仅当g^(ni) ≡ 1 (mod p),
当且仅当ni是p-1的倍数,
当且仅当i是(p-1)/k的倍数(这里用到k = (n,p-1)).
而在0,1,2,...,p-2中,(p-1)/k的倍数恰有k个,即0,(p-1)/k,2(p-1)/k,...,(k-1)(p-1)/k.
这就对应x^n ≡ 1 (mod p)的k个(不同的)解.