己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/08/31 22:01:32
己知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
再答: 采纳不?
再问: 可以
我们可以把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
再答: 采纳不?
再问: 可以
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x
己知m={x/|x-1|<a,a>0},N={x|x^2-5x+6≥0},若m∩n=空集,求a的取值范围.
取模运算,求证(x y) mod m =[(x mod m)(y mod m)] mod m
离散数学题目证明(x·y)(mod m)=((x mod m)·(y mod m))(mod m)
同余式a≡b(mod m)成立,a²≡b²(mod m)成立吗?如何证明?
设m>1,x,y和g都是正整数,且gcd(g,m)=1.如果x ≡y(modφ(m)),求证gx ≡gy(mod m).
设函数f(x)=x^3-9/2x^2+6x-a.(1)对于任意实数x,f'(x)≥m恒成立,求m
a,b,k为大于2的正整数a^k mod (k+1)=n;b^k mod (k+1)=m; 证明 n*m mod (k+
己知关于x的方程x+m/3-2x-1/2=m的解是非负数,求m的取值范围
同余的性质证明若ac ≡ bc (mod m) =0 则 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m
设集合M={(x,y)│y=x^2+2x},N={(x,y)│y=x+a},求使M∩N=空集成立的实数a的取值范围
已知(m-x)*(-X)+n(x+m)=x²+5X-6对于任意数x都成立,求m(n-1)+n(m+1)的值