求37的45次方的92次方除以19的余数.最好用同余做

猪猪小帅 1年前 已收到1个回答 举报

容量有限 幼苗

共回答了15个问题采纳率:93.3% 举报

题:求37的45次方的92次方除以19的余数.最好用同余做.
符号说明:为方便打字,用双等号==取代三线等号≡表示同余.
题目转化: (37^45)^92 mod 19
亦即: 37^(45*92) mod 19
解一:
37^(45*92) mod 19==(-1)^(45*92) == 1
解二:
由费马小定理或欧拉(缩系计数函数)定理,37^18 ==1 mod 19
而45*92 mod 18==9*2==0 mod 18,即45*92=18k
故37^(45*92) mod 19==37^(18k)==(37^18)^k==1^k==1 mod 19

外一则:37^(45^92) mod 19
解一:37^(45^92) mod 19==(-1)^(45^92) ==-1 ==18
解二:45^92 mod 18 == 9^92==81^46==9^46==81^23==9^23==9*81^11==9^12
==81^6==9^6==81^3==9^3==9*81==9*9==81==9
即 45^92=18t+9
由费马小定理或欧拉(缩系计数函数)定理,37^18 ==1 mod 19
于是 37^(45^92) mod 19 ==37^(18t+9)==(-1)^(18t+9)==-1==18 mod 19

1年前

8
可能相似的问题
Copyright © 2022 YULUCN.COM - 雨露学习互助 - 16 q. 0.012 s. - webmaster@yulucn.com