分数的循环节

令 $r\perp s$ 且 $0<r<s$ ,对于分数

$r s = 0. c 1 c 2 c 3 . . .$ $\frac{r}{s}=0.c_1c_2c_3...$

的 $b$ 进位制形式。有时候会出现循环情况。即：

存在一个 $n,k$ 有：

$c i + k = c i, 其中： i > n, 0 < c i < b$ $c_{i+k}=c_i\ \ ,其中：i>n\ ,\ 0<c_i<b$

那么何时会出现循环。何时又不会呢？

显然：

$α = r s = c 1 b 1 + c 2 b 2 + c 3 b 3 . . . . . .$ $\alpha= \frac{r}{s}=\frac{c_1}{b^1}+\frac{c_2}{b^2}+\frac{c_3}{b^3}......$

如果 $\alpha$ 不是循环的,那么必然存在一个数字 $n$ 有：

$α b n = c 1 c 2 c 3 . . c n$ $\alpha b^n=c_1c_2c_3..c_n$

显然： $s\mid b^n$

这也就是说。每一个整除 $s$ 的素因子也整出 $b$ .

那么符合上述条件的。最小的 $n$ 必然是最小的。使得 $s\mid b^n$ 的 $n$

即：当整除 $s$ 的每一个素数都整除 $b$ 时；

则： $\alpha$ 的 $b$ 进制展开。小数点后面的长度为 $n$ ，其中： $n$ 为最小的使得 $s\mid b^n$ 的数。

下面证明 $n$ 是其长度。

如果 $\alpha$ 的展开长度为 $n+l$ .那么有：

$α b n = \sum i = 1 n c i b n - i + \sum i = 1 l c n + i b i$ $\alpha b^n=\sum_{i=1}^nc_ib^{n-i}+\sum_{i=1}^{l}\frac{c_{n+i}}{b^{i}}$

因为 $s\mid b^n$ ,所以 $\alpha b^n$ 为整数。矛盾。得证。

如果 $\alpha$ 是循环的。

记： $s=cd$ 且 $d\perp b$ ， $c$ 的每一个素因子也是 $b$ 的素因子。

这也就是说， $c$ 是满足 $c$ 的每一个素因子都是 $b$ 的且是最大的

令 $n$ 为： $c\mid b^n$ 最小的 $n$

令 $hc=b^n$

$b n \times r s = h r d$ $b^n\times\frac{r}{s}=\frac{hr}{d}$

令

$A + e d = h r d$ $A+\frac{e}{d}=\frac{hr}{d}$

显然 $e\perp d$ ,这是因为： $e=hr\ mod\ d$ 且 $r\perp d$ 且 $b\perp d$

显然 $d=1$ 时。 $\alpha$ 不循环。

当 $d>1$ 时。 $e d$ $\frac e d$ 必然循环。因为不存在整数 $v$ 使得 $d\mid b^v$

现在计算循环节长度。

因为：

$A + e d = b n \sum i \geq 1 c i b i = \sum i \geq 1 c i b n - i + b n \sum i > n c i b i$ $A+\frac{e}{d}=b^n\sum_{i\geq 1}\frac{c_i}{b^i}\\=\sum_{i\geq1}c_ib^{n-i}+b^n\sum_{i>n}\frac{c_i}{b^i}$

因为

$b n \sum i > n c i b i < 1$ $b^n\sum_{i>n}\frac{c_i}{b^i}<1$

所以：

$e d = b n \sum i > n c i b i$ $\frac{e}{d}=b^n\sum_{i>n}\frac{c_i}{b^i}$

令： $v=ord_{d}b$ ,即 $v$ 为 $b$ 模 $d$ 意义的阶。( $d\perp b$ )

则：

$b v = t d + 1$ $b^v=td+1$

则：

$b v e d = ( t d + 1 ) e d = t e + e d = b n + v \sum i > n c i b i = \sum i = n + 1 n + v c i b n + v - i + b n + v \sum i > n + v c i b i = \sum i = n + 1 n + v c i b n + v - i + b n \sum i > n c i + v b i$ $b^v\frac{e}{d}=\frac{(td+1)e}{d}=te+\frac{e}{d}\\=b^{n+v}\sum_{i>n}\frac{c_i}{b^i}=\sum_{i=n+1}^{n+v}c_ib^{n+v-i}+b^{n+v}\sum_{i>n+v}\frac{c_i}{b^i}\\=\sum_{i=n+1}^{n+v}c_ib^{n+v-i}+b^n\sum_{i>n}\frac{c_{i+v}}{b^{i}}$

所以： $b n \sum i > n c i b i = b n \sum i > n c i + v b i$ $b^n\sum_{i>n}\frac{c_i}{b^i}=b^n\sum_{i>n}\frac{c_{i+v}}{b^i}$

所以： $c i = c i + v$ $c_i=c_{i+v}$

现在证明： $n$ 是自小预循环（证明了这一点自然而然就证明了v为最小循环节）

假设，存在更小的预循环 $m$ ,且此时最小循环节为 $k$ .则：

$α = c 1 b 1 + c 2 b 2 + . . + c m b m + \sum j \geq 0 1 b j k (c m + 1 b m + 1 + . . . + c m + k b m + k)$ $\alpha=\frac{c_1}{b^1}+\frac{c_2}{b^2}+..+\frac{c_m}{b^m}+\sum_{j\geq0}\frac{1}{b^{jk}}\Big(\frac{c_{m+1}}{b^{m+1}}+...+\frac{c_{m+k}}{b^{m+k}}\Big)$

$\sum j \geq 0 1 b j k = \sum j \geq 0 (- 1 b k) j (- 1 j) = 1 1 - 1 b k = b k b k - 1$ $\sum_{j\geq0}\frac{1}{b^{jk}}=\sum_{j\geq0}\Big(\frac{-1}{b^{k}}\Big)^j\binom{-1}{j}\\=\frac{1}{1-\frac{1}{b^k}}=\frac{b^{k}}{b^k-1}$

$α = c 1 b 1 + c 2 b 2 + . . + c m b m + b k b k - 1 (c m + 1 b m + 1 + . . . + c m + k b m + k) = c 1 b m - 1 + c 2 b m - 2 + . . . c m b 0 + c m + 1 b k - 1 + c m + 2 b k - 2 + . . . + c m + k b 0 b m ( b k - 1 ) = r c d$ $\alpha=\frac{c_1}{b^1}+\frac{c_2}{b^2}+..+\frac{c_m}{b^m}+\frac{b^{k}}{b^k-1}\Big(\frac{c_{m+1}}{b^{m+1}}+...+\frac{c_{m+k}}{b^{m+k}}\Big)\\=\frac{c_1b^{m-1}+c_2b^{m-2}+...c_mb^0+c_{m+1}b^{k-1}+c_{m+2}b^{k-2}+...+c_{m+k}b^0}{b^m(b^{k}-1)}\\=\frac{r}{cd}$

因为 $d\perp b$ 。所以 $c\mid b^m$ ,这于 $n$ 的定义矛盾。

所以此时 $\alpha$ 的循环节为 $ord_{d}b$ ,预循环节为 $n$ .

更多精彩内容

分数的循环节

令 r⊥s r\perp s且 0<r<s 0<r<s,对于分数

rs=0.c1c2c3... \frac{r}{s}=0.c_1c_2c_3...

的 b b进位制形式。有时候会出现循环情况。即：

存在一个 n,k n,k有：

ci+k=ci ,其中：i>n , 0<ci<b c_{i+k}=c_i\ \ ,其中：i>n\ ,\ 0<c_i<b

那么何时会出现循环。何时又不会呢？

显然：

α=rs=c1b1+c2b2+c3b3...... \alpha= \frac{r}{s}=\frac{c_1}{b^1}+\frac{c_2}{b^2}+\frac{c_3}{b^3}......

如果 α \alpha不是循环的,那么必然存在一个数字 n n有：

αbn=c1c2c3..cn \alpha b^n=c_1c_2c_3..c_n

显然： s∣bn s\mid b^n

这也就是说。每一个整除 s s的素因子也整出 b b.

那么符合上述条件的。最小的 n n必然是最小的。使得 s∣bn s\mid b^n的 n n

即：当整除 s s的每一个素数都整除 b b时；

则： α \alpha的 b b进制展开。小数点后面的长度为 n n，其中： n n为最小的使得 s∣bn s\mid b^n的数。

下面证明 n n是其长度。

如果 α \alpha的展开长度为 n+l n+l.那么有：

αbn=∑i=1ncibn−i+∑i=1lcn+ibi \alpha b^n=\sum_{i=1}^nc_ib^{n-i}+\sum_{i=1}^{l}\frac{c_{n+i}}{b^{i}}

因为 s∣bn s\mid b^n,所以 αbn \alpha b^n为整数。矛盾。得证。

如果 α \alpha是循环的。

记： s=cd s=cd 且 d⊥b d\perp b， c c的每一个素因子也是 b b的素因子。

这也就是说， c c是满足 c c的每一个素因子都是 b b的且是最大的

令 n n为： c∣bn c\mid b^n最小的 n n

令 hc=bn hc=b^n

bn×rs=hrd b^n\times\frac{r}{s}=\frac{hr}{d}

令

A+ed=hrd A+\frac{e}{d}=\frac{hr}{d}

显然 e⊥d e\perp d,这是因为： e=hr mod d e=hr\ mod\ d且 r⊥d r\perp d且 b⊥d b\perp d

显然 d=1 d=1时。 α \alpha不循环。

当 d>1 d>1时。 ed \frac e d必然循环。因为不存在整数 v v使得 d∣bv d\mid b^v

现在计算循环节长度。

因为：

A+ed=bn∑i≥1cibi=∑i≥1cibn−i+bn∑i>ncibi A+\frac{e}{d}=b^n\sum_{i\geq 1}\frac{c_i}{b^i}\\=\sum_{i\geq1}c_ib^{n-i}+b^n\sum_{i>n}\frac{c_i}{b^i}

因为

bn∑i>ncibi<1 b^n\sum_{i>n}\frac{c_i}{b^i}<1

所以：

ed=bn∑i>ncibi \frac{e}{d}=b^n\sum_{i>n}\frac{c_i}{b^i}

令： v=orddb v=ord_{d}b,即 v v为 b b模 d d意义的阶。( d⊥b d\perp b)

则：

bv=td+1 b^v=td+1

则：

所以： bn∑i>ncibi=bn∑i>nci+vbi b^n\sum_{i>n}\frac{c_i}{b^i}=b^n\sum_{i>n}\frac{c_{i+v}}{b^i}

所以： ci=ci+v c_i=c_{i+v}

现在证明： n n是自小预循环（证明了这一点自然而然就证明了v为最小循环节）

假设，存在更小的预循环 m m,且此时最小循环节为 k k.则：

α=c1b1+c2b2+..+cmbm+∑j≥01bjk(cm+1bm+1+...+cm+kbm+k) \alpha=\frac{c_1}{b^1}+\frac{c_2}{b^2}+..+\frac{c_m}{b^m}+\sum_{j\geq0}\frac{1}{b^{jk}}\Big(\frac{c_{m+1}}{b^{m+1}}+...+\frac{c_{m+k}}{b^{m+k}}\Big)

∑j≥01bjk=∑j≥0(−1bk)j(−1j)=11−1bk=bkbk−1 \sum_{j\geq0}\frac{1}{b^{jk}}=\sum_{j\geq0}\Big(\frac{-1}{b^{k}}\Big)^j\binom{-1}{j}\\=\frac{1}{1-\frac{1}{b^k}}=\frac{b^{k}}{b^k-1}

因为 d⊥b d\perp b。所以 c∣bm c\mid b^m,这于 n n的定义矛盾。

所以此时 α \alpha的循环节为 orddb ord_{d}b,预循环节为 n n.

令 $r\perp s$ 且 $0<r<s$ ,对于分数

$r s = 0. c 1 c 2 c 3 . . .$ $\frac{r}{s}=0.c_1c_2c_3...$

的 $b$ 进位制形式。有时候会出现循环情况。即：

存在一个 $n,k$ 有：

$c i + k = c i, 其中： i > n, 0 < c i < b$ $c_{i+k}=c_i\ \ ,其中：i>n\ ,\ 0<c_i<b$

$α = r s = c 1 b 1 + c 2 b 2 + c 3 b 3 . . . . . .$ $\alpha= \frac{r}{s}=\frac{c_1}{b^1}+\frac{c_2}{b^2}+\frac{c_3}{b^3}......$

如果 $\alpha$ 不是循环的,那么必然存在一个数字 $n$ 有：

$α b n = c 1 c 2 c 3 . . c n$ $\alpha b^n=c_1c_2c_3..c_n$

显然： $s\mid b^n$

这也就是说。每一个整除 $s$ 的素因子也整出 $b$ .

那么符合上述条件的。最小的 $n$ 必然是最小的。使得 $s\mid b^n$ 的 $n$

即：当整除 $s$ 的每一个素数都整除 $b$ 时；

则： $\alpha$ 的 $b$ 进制展开。小数点后面的长度为 $n$ ，其中： $n$ 为最小的使得 $s\mid b^n$ 的数。

下面证明 $n$ 是其长度。

如果 $\alpha$ 的展开长度为 $n+l$ .那么有：

$α b n = \sum i = 1 n c i b n - i + \sum i = 1 l c n + i b i$ $\alpha b^n=\sum_{i=1}^nc_ib^{n-i}+\sum_{i=1}^{l}\frac{c_{n+i}}{b^{i}}$

因为 $s\mid b^n$ ,所以 $\alpha b^n$ 为整数。矛盾。得证。

如果 $\alpha$ 是循环的。

记： $s=cd$ 且 $d\perp b$ ， $c$ 的每一个素因子也是 $b$ 的素因子。

这也就是说， $c$ 是满足 $c$ 的每一个素因子都是 $b$ 的且是最大的

令 $n$ 为： $c\mid b^n$ 最小的 $n$

令 $hc=b^n$

$b n \times r s = h r d$ $b^n\times\frac{r}{s}=\frac{hr}{d}$

$A + e d = h r d$ $A+\frac{e}{d}=\frac{hr}{d}$

显然 $e\perp d$ ,这是因为： $e=hr\ mod\ d$ 且 $r\perp d$ 且 $b\perp d$

显然 $d=1$ 时。 $\alpha$ 不循环。

当 $d>1$ 时。 $e d$ $\frac e d$ 必然循环。因为不存在整数 $v$ 使得 $d\mid b^v$

$A + e d = b n \sum i \geq 1 c i b i = \sum i \geq 1 c i b n - i + b n \sum i > n c i b i$ $A+\frac{e}{d}=b^n\sum_{i\geq 1}\frac{c_i}{b^i}\\=\sum_{i\geq1}c_ib^{n-i}+b^n\sum_{i>n}\frac{c_i}{b^i}$

$b n \sum i > n c i b i < 1$ $b^n\sum_{i>n}\frac{c_i}{b^i}<1$

$e d = b n \sum i > n c i b i$ $\frac{e}{d}=b^n\sum_{i>n}\frac{c_i}{b^i}$

令： $v=ord_{d}b$ ,即 $v$ 为 $b$ 模 $d$ 意义的阶。( $d\perp b$ )

$b v = t d + 1$ $b^v=td+1$

所以： $b n \sum i > n c i b i = b n \sum i > n c i + v b i$ $b^n\sum_{i>n}\frac{c_i}{b^i}=b^n\sum_{i>n}\frac{c_{i+v}}{b^i}$

所以： $c i = c i + v$ $c_i=c_{i+v}$

现在证明： $n$ 是自小预循环（证明了这一点自然而然就证明了v为最小循环节）

假设，存在更小的预循环 $m$ ,且此时最小循环节为 $k$ .则：

$α = c 1 b 1 + c 2 b 2 + . . + c m b m + \sum j \geq 0 1 b j k (c m + 1 b m + 1 + . . . + c m + k b m + k)$ $\alpha=\frac{c_1}{b^1}+\frac{c_2}{b^2}+..+\frac{c_m}{b^m}+\sum_{j\geq0}\frac{1}{b^{jk}}\Big(\frac{c_{m+1}}{b^{m+1}}+...+\frac{c_{m+k}}{b^{m+k}}\Big)$

$\sum j \geq 0 1 b j k = \sum j \geq 0 (- 1 b k) j (- 1 j) = 1 1 - 1 b k = b k b k - 1$ $\sum_{j\geq0}\frac{1}{b^{jk}}=\sum_{j\geq0}\Big(\frac{-1}{b^{k}}\Big)^j\binom{-1}{j}\\=\frac{1}{1-\frac{1}{b^k}}=\frac{b^{k}}{b^k-1}$

因为 $d\perp b$ 。所以 $c\mid b^m$ ,这于 $n$ 的定义矛盾。

所以此时 $\alpha$ 的循环节为 $ord_{d}b$ ,预循环节为 $n$ .