首页 > Math > 循环节

循环节

2010年6月1日 发表评论 阅读评论

记得以前我之前写过一篇分数循环节相关的文章，今天扩展一下：讨论下分数的循环解和指数mod p的循环节

考虑a/m在p进制下的输出（gcd(a,m)=1）和f(n)的循环节.首先说一下前者，因为前者的循环可以由后者直接得到！两者是同步的！当然有一种方式能使你很快意识到这一点

给出以下描述，如果t是使gcd(p^{t-1},m)最大的最小正整数,那么t就是循环起始的位置。简单的说，从t开始，\forall{n}\in{N^*},n\geqslant{t},g=gcd(p^{t-1},m)都不再变化(这个g后面会用到)。

显然当n小于t时gcd(f(n),m)和n大于等于t时的gcd(f(n),m)不同,所以n小于t时的f(n)不可能和后面的n大于等于t时的f(n)的任何一个相等，t之前的n就不会出现在循环内！当然，这还不能证明t就在循环内

当然由欧拉定理，我们可以马上得到，当gcd(p,m)=1时，循环节存在（欧拉函数的值必为循环节的倍数），且必然是从n=1开始的

然后注意到以下事实：

于是f(n)=g\cdot (\frac {a \cdot p^{n-1}}{g}\;\; mod \;\frac{m}{g}) \;,n \geqslant t此时gcd(p^{n-1} , \frac{m}{g})=1，这和gcd(p,m)=1的情况其实是同构的.

令a= \frac{a \cdot p^{t-1}}{g},m= \frac{m}{g},n=n-t，你就得到了和初始的式子一样的一个新式，用上面的欧拉定理你可以证明这次的这个是循环的，因为gcd(p,m)=1了，最后，别忘了这个是从第t位开始的（因为有变换n=n-t），而且结果需要乘以g（因为之前把这个公约数给提出来了）。

这个循环可以一一映射到分数的循环节，如果你把那个小学就学过了的竖式想得够彻底的话，这一切都是显然的

分类: Math 标签:
  1. www.zgh.gov.cn
    2010年6月22日10:15 | #1
    回复 | 引用

    写的不错，嘿嘿.博主的主题我挺喜欢，不知何时我也有这技术去仿一个。嘿嘿

  2. Earthson
    2010年6月23日00:26 | #2
    回复 | 引用

    貌似网上很多人用的这个主题，对比了很多，这个确实不错^^
    有时间我也打算自己做一个

  1. 本文目前尚无任何 trackbacks 和 pingbacks.