循环小数与费马小定理
17/05/29 22:30:51 | Snakes
背景
题目出自之前亮灯问题、杨辉三角与Sierpinski三角形提及的生日题中的第三、四、五题。
题目
第三题 证明:对于任意非(2, 5)倍数正整数(n)且满足(n>1),均存在正整数(k, i)满足(kn=10^i-1)。
第四题 证明:在(k)进制下((k>1)),任何形如(a/b)((a, b)均为正整数)的数均为有限小数或无限循环小数。
第五题 证明:在上一问条件下,若(b)与(k)互质则(a/b)为无限循环小数,若(a)的质因子为(k)的质因子的子集则(a/b)为有限小数。
答案
既然是证明题,那么就没有标准答案。以下提供一种可行的思路并且再探讨另一个问题:(k)进制下(b/a)若循环,那么它的循环节长度(len)是多少?
接下来,我们将要分节讨论了。
无限循环小数
在(k)进制下,若有数(x)满足其为(0<x<1)的纯循环小数(即其循环节从小数点后第(1)位开始|思考:若为混循环小数或大于(1)的纯循环小数,有什么办法将其转化求解呢?)且其循环节长度为(len),循环节中数字为(y),则我们可得(xcdot k^{len}-x=y)。(xcdot k^{len})相当于将第一个循环节移动到小数点左侧,与(x)相减就得到循环节中的数字(y)。整理可得(y/(k^{len}-1)=x)。
所以,我们可得结论:数(x=a/b)为无限循环小数的条件为存在整数(len, i)满足(bi=k^{len}-1)。这个式子中,(k)取(10)的情形即第三题的提问。
思考题答案:若为大于(1)的纯循环小数,可表示成一个整数与一个(0)与(1)之间纯循环小数的和,因为整数一定能表示成任意整数作分母的分数形式,对小数部分讨论之后将整数部分加上去即可。对于混循环小数,可以乘以(k)的次幂,将小数点移动到循环节前,按照大于(1)的纯循环小数处理,最后乘以(k)的次幂的倒数即可。
费马小定理
对于质数(p),与(p)互质的整数(a),有下式成立:
这是接下来将要用到的定理。如何证明?
引理(1):对于整数(a, b, c)与正整数(p),若(c, p)互质,(acequiv bc pmod p),则有(aequiv b pmod p)。
证明:
移项得:
因为(c, p)互质,所以有:
引理(2):对于整数(p)满足(p>1),与(p)互质的整数(b)以及模(p)的完全剩余系(a_1, a_2, .. ,a_m),有(ba_1, ba_2, .. ,ba_m)构成模(p)的完全剩余系。
证明:
若其不构成模(p)的完全剩余系,则有(ba_iequiv ba_j pmod p)成立,由引理(1)得,有(a_i equiv a_j pmod p)成立,与条件不符,因此(ba_iequiv ba_j pmod p)不成立,则(ba_1, ba_2, .. ,ba_m)构成模(p)的完全剩余系。
费马小定理:
构造模(p)下的完全剩余系({0, 1, 2, .. , p-1}),由引理(2)得({0, a , 2a, .. , (p-1)a})也为模(p)下的完全剩余系。可得(1 imes 2 imes .. imes (p-1)equiv a imes 2a imes .. imes (p-1)a pmod p)成立。则有((p-1)!equiv a^{p-1}(p-1)! pmod p)成立。因为(p)为质数,所以((p-1)!)与(p)互质,根据引理(1)得(1equiv a^{p-1}pmod p)成立。
两者之间的关系
之前提及,数(x=a/b)为无限循环小数的条件为存在整数(len, i)满足(bi=k^{len}-1)。而费马小定理则告诉我们,对于质数(p),与(p)互质的整数(a),有(a^{p-1}equiv 1 pmod p)。当(b)为质数,(a=k)时显然有(k^{b-1}-1equiv 0 pmod b),也就是说,存在整数(len, i)满足条件。
但是当(b)不为质数但与(k)互质时怎么办?不妨将(b)分解质因数,令(b=p_1^{q_1} imes p_2^{q_2} imes .. imes p_n^{q_n})(此处翻车),根据欧拉定理(在(b, p)互质下有(p^{varphi(b)}equiv 1pmod b)),则分别有(k^{varphi(p_i^{q_i})} equiv 1 pmod {p_i^{q_i}})成立,其中(1leq i leq n)。可知有(k^{c(p_i-1)p_i^{q_i-1}} equiv 1 pmod {p_i^{q_i-1}})成立。别忘了欧拉函数是积性函数,所以有下式成立:
即:
并且由于积性函数,我们有:
所以大多数情况下((b)与(k)互质)时循环节长度最小值(len)能被(varphi(b))整除。
而对于(b)与(k)不互质的情况,我们要分类讨论。若(b)的质因数为(k)的质因数的子集,那么(a/b)乘以(k)的次幂一定可以得到一个整数,则(a/b)为有限小数。若不为子集,则我们将(a/b)乘以(k)的次幂,消除交集部分质因数的影响,转为(b)与(k)互质的情况继续讨论。这其实与之前思考题的解决方法一致。通过分类讨论,我们可以解决第四题与第五题。
所以,将(k=10)代入,我们可以证得第三题(对于任意非(2, 5)倍数正整数(n)且满足(n>1),均存在正整数(k, i)满足(kn=10^i-1)。)成立。
结论
在(k)进制下,形如(a/b)((a, b)均为整数)的分数(最简形式),若(b)与(k)互质,则(a/b)为纯循环小数。若(b)质因数与(k)质因数有交集且(b)质因数不为(k)质因数子集,则(a/b)为混循环小数。否则若(b)质因数为(k)质因数的子集,(a/b)为有限小数。
当(a/b)为循环小数时,在大多数情况下其循环节长度(len=frac{varphi(b)}{gcd[ varphi(p_1^{q_1}),varphi(p_2^{q_2}), .. , varphi(p_n^{q_n})]})。不难发现有(lenleq (b-1))且当(b)为质数时(len)取到(b-1)。