数论倒数又称逆元怎么算(因為我说习惯逆元怎么算了,下面我都说逆元怎么算)
数论中的倒数是有特别的意义滴
你以为a的倒数在数论中还是1/a吗
证明是对的难证明错嘚只要举一个反例
对于一些题目,我们必须在中间过程中进行求余否则数字太大,电脑存不下那如果这个算式中出现除法,我们是不昰对这个算式就无法计算了呢
但是a如果不是1,那么x就是小数
那数论中大部分情况都有求余,所以现在问题变了
那么x一定等于1/a吗
所以这時候我们就把x看成a的倒数,只不过加了一个求余条件所以x叫做 a关于p的逆元怎么算
比如2 * 3 % 5 = 1,那么3就是2关于5的逆元怎么算或者说2和3关于5互為逆元怎么算
这里3的效果是不是跟1/2的效果一样,所以才叫数论倒数
a的逆元怎么算我们用inv(a)来表示
这样就把除法,完全转换为乘法了 (?ω?),乘法超容易
(忘了说a和p互质,a才有关于p的逆元怎么算)
费马曾经说过:不想当数学家的数学家不是好数学家(( ̄▽ ̄)~*我随便说的别当嫃)
什么(,,? ? ?,,),这可是数论还敢写1/a
还记得扩展欧几里德吗?(不记得的话欧几里得会伤心的(╭ ̄3 ̄)╭?)
这个解的x就是a关于b的逆元怎么算
你看你看,出现了!!!(/≥▽≤/)
所以x是a关于b的逆元怎么算
证明不想看的孩子可以跳过。( ̄0  ̄)
然后一直递归到1为止,因为1的逆元怎么算就是1
这个方法不限于求单个逆元怎么算比前两个好,它可以在O(n)的复杂度内算出n个数的逆元怎么算
递归就是上面的写法加一個记忆性递归,就可以了
又学到新知识了o(*≧▽≦)ツ好开心
因为5是质数所以可以这样,理論依据是费马小定理
所以2^100的个位数是6
不好意思,写的有问题应该是
假如a是一个整数,p是一个质数那么如果a不是p的倍数,这个定理也鈳以写成
我只是根据原来奥数学的一些推得13L才是专家。
费马小定理:假如p是质数且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1
3L这个是用牛顿②项式定理
除a余数只和展开式最后一项C(n,n)b^n有关
定理我知道啊,关键是这一步“
对余的数学运算总不是那么显然的认为像楼上的转换成还是容易理解一些的吧?
我那种办法也是简化的 主要是除数5比较小 导致完全剩余系只有4个數
如果是大质数的话用这种方法就不好算了还是通过理论推好点。。
请教你是怎么看出这个规律来的