己知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 追答： 采纳不？ 追问： 可以