题目

关于扩展欧几里德算法
我要用扩展欧几里德算法计算-n*n' % r=1等式中的n',其中n为已知非负奇数,r=2^k,想问下 -n*n'%r=n*n'%r=1 是否成立,在运算过程中,是不是会有负号产生,计算出来的n'会不会是负数,如果是,忽略了它的负号会不会有影响?
以上式子可否化成,n'=-n^(-1)%r=(r-n)^(-1)%r 其中n^(-1)是不是n的导数,还是什么?如果有详解,小弟感激不尽|!

提问时间：2020-08-16

答案

-n*n'%r=n*n'%r=1不成立
n'如果算出是负数不能忽略符号
n'=-n^(-1)%r=(r-n)^(-1)%r可以化
其中n^(-1)是不是n的倒数?是数论倒数
n^(-1)*n被模r除余1