【xaio77论坛】己知a=18m=77求使a^x≡1(modm)成立的最小自然数x用...

【xaio77论坛】己知a=18m=77求使a^x≡1(modm)成立的最小自然数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 追答： 采纳不？ 追问： 可以

感谢回答，我学习了

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息