Fermat定理求3的1025次方mod15
收藏:
0
点赞数:
0
评论数:
0
5个回答

Fermat-欧拉定理

a^f(n)=1 (modn)

n=15=3*5 (没有必要15是素数, 3和5是素数 )

f(15)=15(1-1/3)(1-1/5) =8

1025=127*8+9

3^1025=3^(8*127+9)=((3^8)^127 )*3^9

3^1025 mod15

=((3^8)^127 )*3^9 mod15

=1^127 *3^9 mod15=3^9 mod15=19683 mod15=3

3^1025 mod15=3

点赞数:
0
评论数:
0
相关问题
关注公众号
一起学习,一起涨知识