己知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)