Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. 算法
  3. 正文

扩展欧拉定理

2018年07月28日 1315点热度 0人点赞 0条评论

内容纲要

欧拉定理 $$a^{\phi(n)} \equiv 1 \pmod n,(a,n)=1$$
进而有 $$a^b \equiv a^{b \bmod \phi(n)} \pmod n,(a,n)=1$$
那么对于a和n不互质 我们有扩展欧拉定理
$$a^b\equiv a^{b\bmod \phi(n)+\phi(n)} \pmod n,(a,n)\ne 1 \text{且} b\ge \phi(n)$$
注意 $$b<\phi(n)$$的时候是不成立的 比如$$2^2\bmod 8 \ne 2^{2+4}\bmod 8$$

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2018年07月29日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
hustoj Apache php C++ JavaScript Java GitHub C
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 15,313
  • 5,553
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?