推 doa2 : 循環節不會超過16，也就是n-1 09/15 12:28
→ rfvbgtsport : 可否告知為什麼是16？要怎麼判別，謝謝 09/15 13:00
→ hwanger : 假設m/n無法除盡 則n不是2^s5^t的樣子 並得 09/15 13:12
→ hwanger : m*10^0, m*10^1,...,m*10^n除n的餘數必須為1,2,..., 09/15 13:15
→ hwanger : n-1 (前面打錯 是m*10^0, m*10^1,...,m*10^{n-1}共 09/15 13:16
→ hwanger : n個) 則由鴿籠原理 必有兩個餘數相同 所以循環了 09/15 13:17
→ hwanger : "則n不是2^s5^t的樣子">>>這句話是多的 冏 09/15 14:02
→ rfvbgtsport : 請問有直接判別，幾個循環節的方法？不用證明 09/16 16:38
推 LPH66 : 所求為 10 對餘 n 的 multiplicative order 09/16 18:04
→ LPH66 : *同餘 n 09/16 18:04
→ LPH66 : 意思是 10^m ≡ 1 (mod n) 的最小整數 m 09/16 18:05
→ LPH66 : 對所有 n 能一致成立的已知事項只有一樓所言 09/16 18:06
→ LPH66 : 它不會超過 n-1, 以及它是 phi(n) (歐拉 phi 函數) 09/16 18:07
→ LPH66 : 的因數 09/16 18:07
→ hwanger : "請問有直接判別...">>>r大是要問演算法嗎 證明可以 09/16 23:40
→ hwanger : 直接當演算法 還是r大是要用什麼具體的性質 09/16 23:40
→ hwanger : 如L大所述(不過我還是用我上面的符號) 這已經牽扯 09/16 23:51
→ hwanger : 到(Z/nZ)*的結構問題 所以r大給個具體想要的條件 才 09/16 23:51
→ hwanger : 能判斷能不能做到 09/16 23:51
推 hwanger : 前述演算法的具體作法: 假設gcd (m,n)=1且m/n無法 09/17 00:44
→ hwanger : 除盡 去算最小的s<t 滿足10^s≡ 10^t (mod n) 則循 09/17 00:44
→ hwanger : 環節為t-s 09/17 00:44
推 LPH66 : 噢對, 我的說法其實少一個條件: 要有 gcd(10,n)=1 09/17 01:42
→ LPH66 : 才能用 10^p≡1 的條件去判斷, 一般仍要用上式 09/17 01:43
→ LPH66 : 10^s≡10^t 才行, 而這是因為當 n 和 10 不互質時 09/17 01:43
→ LPH66 : 在循環節前會有不屬於循環的位數 09/17 01:44
→ LPH66 : 例如 n=12 (1/12 = 0.1666...), 會求得 10^2≡10^3 09/17 01:46
→ hwanger : 或直接沿L大的思路走 一樣假設gcd (m,n)=1且m/n無法 09/17 10:14
→ hwanger : 除盡 並令n=2^s*5^t*p1^k1*...*ph^kh 則去找最小的 09/17 10:16
→ hwanger : 正整數c 滿足10^c≡1 (mod p1^k1*...*ph^kh) 09/17 10:19
→ hwanger : 其中c從φ(p1^k1*...*ph^kh)或φ(n)的因子去試即可 09/17 10:45