- 最后登录
- 2025-2-23
- 在线时间
- 1542 小时
- 阅读权限
- 100
- 注册时间
- 2006-9-27
- 积分
- 6864
- 帖子
- 4591
- 精华
- 3
- UID
- 6886
- 性别
- 男
  
- 积分
- 6864
- 帖子
- 4591
- 精华
- 3
- UID
- 6886
- 性别
- 男
|
找了找，原来是这样的。
关于欧拉函数与循环节长度
求1/2008的循环节长度。
我看了版主hejoseph的关于计算1/n的循环节位数的帖子，用欧拉函数算的，可是这题仍然算不出来，请指教!
这是安徽2008年联赛初赛题选择题，选项：30，40，50，60 ，答案是50
2008=23×251，
φ(251)=250，
250的正因数有1、2，5、10、25、50、125、250，x取上述正因数并且满足10x≡1 (mod 251)的最小的x是50，所以1/2008的循环节长度是50。
欧拉函数φ(n)：欧拉函数是一个定义在正整数上的函数，φ(n)的值等于以下这些整数0、1、2、…、n-1与n互素的数的个数。
由定义知，φ(1)=1，φ(2)=1，φ(3)=2，φ(4)=2，……，当p是素数时，φ(p)=p-1。
欧拉函数的计算方法：设n的标准分解式子是p1^k1·p2^k2·…·pm^km，其中p1、p2、…、pm是互不相等的素数，k1、k2、…、km都是正整数，则φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pm)。
例如φ(10)=10×(1-1/2)×(1-1/5)=4。
欧拉定理：设a、m为整数，m>1，(a,m)=1，则a^φ(m)≡1 (mod m)。
整数的次数：a、m为整数，m>1，(a,m)=1，k是使a^k≡1 (mod m)成立的最小正整数，则k叫做a对模m的次数。
次数定理：设a对模m的次数为k，n是满足a^n≡1 (mod m)的正整数，则k|n。
欧拉函数的计算方法、欧拉定理的证明、次数定理的证明可以找初等数论的书，这里就不发上来了。
由欧拉定理可以得到求1/n循环节长度的方法。
举个简单的例子。
例如n=11，则φ(11)=10，根据欧拉定理10^10≡1 (mod 11)，所以循环节长度一定是10的正约数。而10的正约数有1、2、5、10，从小到大逐一检验，得到10^2≡1 (mod 11)，所以1/11的循环节长度就是2。
虽然这个方法可行，但因数多时仍需要做很多的验证，需要有更有效的改进方法。
假设a、n是大于1的正整数，p是素数，则a对模p的次数没有什么好办法去求，只能用上面的方法。
其它情形有下面两个定理：
假设a、n是大于1的正整数，n的标准分解式是p1^k1·p2^k2·…·pt^kt，其中p1、p2、…、pt是互不相等的素数，k1、k2、…、kt都是正整数，a对模pi^ki的次数为mi，则a对模n的次数为m1、m2、…、mt的最小公倍数。
如果a、n是大于1的正整数，p是素数，k是正整数，a对模p^k的次数是m，则a对模p^(k+1)的次数是m或pm。
这两个定理也可以从初等数论里找到证明，我也不发上来了。
再举一个例子
539=7^2×11
10对模7的次数为6，那么10对模7^2的次数或者是6或者是42，经计算验证得10对模7^2的次数是42。
10对模11的次数为2。
所以10对模539的次数为2和42的最小公倍数，即42，所以1/539的循环节长度为42。
[ 本帖最后由 龚永明魔方 于 2011-7-7 09:58 编辑 ] |
|
IP卡
狗仔卡
发表于 2011-6-27 15:37:15
收藏
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
恢复卡
发表于 2011-7-7 10:25:29