数论:逆元

今天讲讲逆元

逆元

首先,我们先引入一个概念:同余 

什么是同余?

若 数论:逆元 与 数论:逆元除以正整数p有一样的余数,那么我们说a与b在模p的意义下同余,即,数论:逆元 数论:逆元数论:逆元

同余还有同余类和剩余系,大佬们或者学有余力的读者可以自行百度,至少我是不会的啦

那么我们来讲讲什么是逆元 

数论:逆元 数论:逆元,则a与b互为逆元。

那逆元有什么用呢?

这又涉及一个知识点:取模

因为a/b%p数论:逆元(a%p/b%p)%p,所以我们要找到一个东西使得它数论:逆元,这个数,便是b的逆元。

现在又来了一个问题,逆元怎么求?

 

那么我们可以引入两个定理:

1.费马小定理

若p是质数,则对于任意整数a,有数论:逆元 数论:逆元.

2.欧拉定理

若正整数a,n互质,则有数论:逆元 数论:逆元,其中数论:逆元为欧拉函数。

欧拉定理与费马小定理证明,大家可以上网去搜索。

不过你若是知道一点:当n为质数时:数论:逆元

那你就可以用欧拉定理证明费马小定理。

 

回到正题,一般求逆元,使用的是费马小定理

若要求a模p意义下的逆元(p为质数),则只用求数论:逆元,用快速幂即可

为什么呢?
这个问题留给读者自己证明。

给个提示:用费马小定理的式子与逆元的式子

自然,逆元还有其他方法,比如杨辉三角,扩展欧几里得,中国剩余定理+扩展欧几里得 等等

杨辉三角的方法其实很水,但时间复杂读不允许n>=1000的数据

程序你们自己打吧,很水的。

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

数论:逆元

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 数论:逆元
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏