作业帮 > 数学 > 作业

己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/06/05 03:52:49
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x
用费马小定理和欧拉定理的知识求解,急.收到请速回复谢谢
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x
欧拉定理(a,m)=1,则a^φ(m)≡1 (mod m)
我们可以把77分成7×11来考虑,
即找使18^y≡1(mod 7)和18^z≡1(mod 11)的最小自然数y和z.
由欧拉定理可得18^6≡1 (mod 7) 和18^10≡1 (mod 11)
18≡4(mod 7),则4^6≡1(mod 7),6=2×3,易验证4^3≡1(mod 7),则18^3≡1(mod 7)
y最小为3.
18≡7(mod 11),则7^10≡(mod 7),10=2×5,易验证7^2和7^5模11均不为1,
所以z最小为10.
综合两者,3和10的最小公倍数为30,所以最小的x为30.18^30≡1(mod 77)
再问: 则4^6≡1(mod 7)怎么来的,能说清楚些吗?我看不明白,急,收到请速回复谢谢!
再答: 4和7互素,由欧拉定理可得4^φ(7)≡1 (mod 7) 由于7为素数所以φ(7)=6. 后面我有地方打错了,是: ”18≡7(mod 11),则7^10≡1(mod 11),10=2×5,易验证7^2和7^5模11均不为1“ 这里也是欧拉定理φ(11)=10
再答: 采纳不?
再问: 可以