一、进制的原理

1.1 介绍进制

在人类社会中，一个整数总是以十进制的阿拉伯数字表示。（据说因为人有十根手指）计算机中，常用进制还有二进制、三进制、八进制、十六进制等。而每个大于一的正整数k都可以有对应的进制！

对于大于一的正整数k，当2≤k≤10时，表示方式一般为阿拉伯数字，11≤k≤36时，一个数位上的数若大于9，则以A~Z表示，其中A表示10，B表示11，以此类推。k≥37时，由于几乎不常用，所以表示方法一般使用者自己说明（什么。

可为何k大于一呢？

一一一正  片  开  始一一一

1.2 乘法原理与饮料问题

进制计数法是用来计数的（废话。十进制中，0~9十个数字，在n个有序数位中出现，可表示出从0到10^n-1这10^n种情况。但为何这10^n种情况总能与10^n个数字一一对应？

思考问题：有6个不同的杯子，编号从1到7（没有4），次序不变。也有3种不同的饮料，分别是果汁、可乐和白水。你可以将一种饮料倒入一个杯子中，但一个杯子里仅能有一种饮料。选择杯子并倒饮料后，不考虑饮料多少，只按种类分情况。

问：有多少种倒饮料的选择？

解：

此时，一个杯子中分无、水、果汁、可乐四种情况 /*也可以不倒饮料*/

由乘法原理，六个杯子，每个都是四种情况，所以共4^6=4096种情况

答：共4096种选择

以0表示不倒饮料，1表示水，2是果汁，3是可乐。将杯子看作6个有序数位，将最后的情况看作四进制的数字，共4096种情况。十进制同理，由乘法原理，得到情况数，再把数与情况一一对应即可。因此，一进制相当于你手中一瓶饮料也没有，再多的数位仅能表示一种情况。而一进制“逢一进一”，可表示的情况仅为0，无法表示更多数，故k>1。但是否会出现重复或多余的情况使之无法对应？

1.3 数表示的数值

在k进制中，如何将数值与情况进行一一对应？这时应比较数值的大小。

早在小学二年级，老师就教过如何比较十进制正整数的大小。先看位数多少（1919810>114514），位数相同再一位位地比较数的大小（514>114）。所以，从1到10^n中所有的情况（包括1与10^n）就可以按相应的大小排列。k进制依然同理。不过，依照k进制的意义（如(1437)k=1*k^3+4*k^2+3k+7），这种比较方式是怎样得来的？

已知：k进制下a、b的形式分别为m位数、n位数，m>n

求证：a>b

（a,b,k,m,n∈N*，k>1）

证明：

设a在k进制下表示出的m位数的最高位上的数为p

∴p≥1，a≥p*k^(m-1)≥k^(m-1)

∵b在k进制下表示出的n位数的每一位上的数均小于等于(k-1)

∴b小于等于k进制下每一位上的数均等于(k-1)的n位数，即

∴b<k^n

∵m>n，m,n∈N*，m-1≥n

∴a≥k^(m-1)≥k^n>b，a>b

Q.E.D.

而a、b位数相等时，欲比较大小，则仅需划掉a、b从左往右数所有所在数位相同，且数相同的数位，直到出现不同时，再比较大小。

已知：k进制下a、b的形式为m位数，a、b最高位分别为p、q，p>q

求证：a>b

（a,b,k,m,p,q∈N*，k>1，q<p<k）

证明：

∵由此题与上一题，a≥p*k^(m-1)，b<(q+1)*k^(m-1)，p≥q+1

∴a≥p*k^(m-1)≥(q+1)*k^(m-1)>b，a>b

Q.E.D.

就酱证明了k进制下每种表示方法都代表相应的数值，不同的数代表不同数值，并将每种表示方法与每个数值一一对应，且能规律地比较大小，保证了1.2中的4096种不同情况（甚至更多种）对应的4096个不同数字表示的4096个不同数值能够一一对应。 /*同理，这种方法对全实数比较大小都是可行的*/ （整篇都是沸话（确信

二、进制对正整数取余的影响

2.1 经典定理

众所周知，小学二年级数学老师都教过：

若：n mod 9=p，且n的各数位上的数总和为s

则：(n-s)/9∈N，s除以9的余数必为p

（n,s∈N*，p∈N）

先举一个一个一个栗子例子：

1+1+4+5+1+4=16，16/9=1······7，114514/9=12723······7（臭死力

证明也很简单：

此时，∃k∈N*使10^(k-1)≤n<10^k /*这里说明n是一个k位数*/

设n的10^(x-1)位 /*即从右往左数的第x个数位*/ 上的数为nx（1≤x≤k，x∈N*），则

而对于∀k1∈N*，必有

∴对于∀q∈{x|1≤x≤k，x∈N*}，都有[nq*10^(q-1)-nq]/9∈N

∴(n-s)/9∈N，s≡n(mod 9)，s与n分别除以9后余数同为p

Q.E.D.

同理，可用相同的方式证明s≡n(mod 3)，m与n除以3后余数相同依然成立。

一一一正  片  开  始一一一

2.2 定理在不同进制下的拓展

任何数位终将绳之以法！用“绳子”把数位“绑”在一起，两位两位地算，对11、33、99成立，三位三位地算，对111、333、999也成立！而三位对37成立，五位对41成立，六位对7、11、13都成立！原因如下：

若：n mod m=p，且n以k进制表示时各数位上的数总和为s

则：当(k-1)/m∈N*时，s除以m的余数必为p

（k,m,n∈N*，k>1，p∈N）

例如：(1437)9=1087，除以8余7，除以4余3，1+4+3+7=15，除以8余7，除以4余3

证明思路同上：

此时，∃k1∈N*使k^(k1-1)≤n<k^k1

设k进制下，n的k^(x-1)位 /*即从右往左数的第x个数位*/ 上的数为nx（1≤x≤k1，x∈N*），则

设k2=(k-1)/m，则对于∀k3∈N*，必有

∴对于∀q∈{x|1≤x≤k1，x∈N*}，都有[nq*k^(q-1)-nq]/m∈N

∴(n-s)/m∈N，s≡n(mod m)，s与n分别除以m后余数同为p

Q.E.D.

/*式子的目的是证明k进制下某一数位上的数后面有再多的0，这个“后面只有一堆0的数”减去“数的本体”都必然是(k-1)的整数倍（如十进制中20000-2=2*1111*9，9=10-1）*/

这就是十进制运算下三位对37成立，五位对41成立，六位对7、11、13都成立的原因了！37*27=999，41*2439=99999，7*11*13*27*37=999999，也就是说，十进制表示时，把n位绑在一起，实际上就是在将以10进制表示的数看作以10^n进制表示，把n个数位看作一个更大的数位，再进行运算！（由费马小定理，k进制下，当(n+1)为质数，k/(n+1)∉Z时，n位n位地计算，两个总和除以(n+1)的余数依然相等，且与循环小数的循环节有一定联系。若将1/7、1/13等化为循环小数，其循环节长度会与进制有关吗？欲知后事如何，且听下回分解）

三、进制对循环小数的影响

3.1 分数与循环小数的转化

√2是一个无理数，化为小数是无限不循环小数，即不存在两个整数p、q使p/q=√2。那么，如何证明无理数一定等价于无限不循环小数呢？仅需证明“实数x为有理数”等价于“实数x为循环小数或有限小数或整数”。

k进制下，整数不必多说，n位小数p仅需化为p*k^n/k^n。对于循环小数q，设[q]为不超过q的最大整数，{q}=q-[q]，仅需证明{q}∈Q。{q}循环节长度为t，t∈N*，则{q}为纯循环小数时，{q}*(k^t-1)∈Z /*小数点右移t位后小数部分不变*/ ，而k、[q]∈N*，q=[q]+{q}*(k^t-1)/(k^t-1)，q∈Q。若{q}为混循环小数，小数点后第m位开始循环，m∈Z，m>1，则证明{q}*k^(m-1)∈Q /*将小数部分化为纯循环小数*/ 后，将{q}*k^(m-1)除以整数k^(m-1)便可证{q}∈Q，又因为q=[q]+{q}，所以q∈Q。故任意进制下，循环小数、有限小数与整数均为有理数。

一一一正  片  开  始一一一

而k进制下，一个大于1的正整数n的倒数化成分数是1/n，化成小数不是循环小数就是有限小数。举栗子：十进制中，1/2=0.5=(0.1)2，1/3=0.33…=(0.0101…)2，1/6=0.166…=(0.2)12 /*这里直接化到最简，不考虑1=0.99…这类问题*/ 。在此，如何证明一个有理数在任意进制下必能化为循环小数或有限小数或整数？所化小数的形式是否又与k有关？先定义一个新概念：循环列。

{m,k}循环列：

写作P{m,k}，m,k∈Z，m≥2，k≥2，k与m互质，是有穷数列，首项p1=k mod m，第n项（n>1）pn=(pn-1k) mod m，当且仅当n=p时，pn满足∃q∈N*且1≤q≤n使pq=(pn+1k) mod n

例如：P{7,2}={2,4,1}，P{7,9}={2,4,1}，P{5,8}={3,4,2,1}

/*实际上这是k进制中将1/m化为循环小数的竖式下的余数*/

接下来是它的一些性质：

pn=(pn-1k) mod m=pn-1(k mod a)=k^n mod m（由余数乘法定理易证）

P{m,k}的项数t{m,k}≤(m-1)（由定义，此数列中任意两项互不相同，而由k与m互质得此数列的每项仅有m-1种可能）

P{m,k}末项为1（由k与m互质，对∀a,b∈Z使a mod m≠b mod m，必有ak mod m≠bk mod m，由定义知数列末项的k倍除以m的余数必为数列首项，故末项必为1） /*它循环的特点正能体现走马灯数的原理*/

已知：p∈Z，q∈N*

求证：∀k∈Z且k>1，有p/q在k进制下必可化为整数或有限小数或循环小数

证明：

设m=p mod q，则m∈N

当m=0时，p/q∈Z

当m>0，∃n∈N*使k^n mod q=0时，k^n/q∈Z，p/q=p*(k^n/q)/k^n /*就是左移整数p*(k^n/q)的小数点n位*/ ，此时p/q可化为有限小数

当m>0，∀n∈N*使k^n mod q>0，k与q互质时，

    设1/q小数点后第x位上的数为qx，2≤a≤t{q,k}且a∈Z，P{q,k}上第a项为pa，

    则q1*q+p1=k，qa*q+pa=kp(a-1)

    ∵P{q,k}末项为1

    ∴q(t{q,k}+1)=q1，1/q在k进制为纯循环小数，循环节长度为t{q,k}

    ∴m/q在k进制为纯循环小数 /*把每个循环节里的数乘m都不会进位，因为m/q<1*/

    ∴由m=p mod q，得(p-m)/q∈Z，此时p/q=(p-m)/q+m/q，p/q为纯循环小数

当m>0，∀n∈N*使k^n mod q>0，k与q不互质时，

    ∴此时q必为合数，可令q=n1*n2，其中n1,n2∈N*，∃n∈N*使k^n mod n1=0，k与n2互质

    ∴同理得1/n2在k进制为纯循环小数，k^n/n1∈Z，(k^n/n1)/n2为纯循环小数

    ∴k^n/q为纯循环小数，1/q为混循环小数 /*左移k^n/q的小数点n位*/ ，p/q为循环小数

∴综上，p/q在任意进制下必可化为整数或有限小数或循环小数

Q.E.D.

现已证明“实数x为有理数”等价于“实数x为循环小数或有限小数或整数”，同时还得到了一个结论：当m,k∈N*，k≥2，m≥2时，若∃n∈N*使k^n mod m=0，则k进制下，1/m为有限小数，若∀n∈N*使k^n mod m>0，则k进制下，当k与m互质时，1/m为纯循环小数，当k与m不互质时，设(k,m)=n1，1/m为混循环小数，且不循环数位的位数等于n1分解质因数后，指数最高的一项的指数 /*例如16200=2^3*3^4*5^2，其指数最高项的指数就是4*/ ，并非只和2、5有关。

3.2 费马小定理、循环节长度与走马灯数

不难发现，m为质数时，t{m,k}≤(m-1)，且必为(m-1)的因数，可以通过费马小定理证明，且根据P{m,k}的定义易得，此时1/m的循环节长度等于t{m,k}。故当m为质数，且k/m∉Z时，k进制下的1/m必被化为纯循环小数，且循环节长度必为(k-1)的因数，例如1/7=(0.032412032412…)5=(0.001001)2…。

众所周知，142857事一个一个走马灯数，但它从乘1到乘6能刚好转一圈的这条性质，仅在十进制下成立，因为lg(142857*7+1)=6。同理，2232也可以从1乘到6也可以转一圈，但需化为五进制，得到2232=(32412)5。这里提下1/13的循环节，其长度有六位，是12的一半，76923也是走马灯数之一，而1也可以当走马灯数，仅需从1乘到6，再转化为2进制，接下来对比1/7到6/7的二进制形态，会发现它们具有相似的特征。

本质上，若n为质数，且k不是n的整数倍，则1/n在k进制的循环节就一定是k进制的走马灯数，关键是选对进制。由P{n,k}的定义可轻易证明这一点。当t{n,k}=n-1时，由费马小定理，对∀a∈N*且1≤a≤n-1，都∃b∈N*且1≤b≤n-1，使k^b≡a(mod n)。所以将a/n化为循环小数的竖式中，出现的余数种类不变，只有次序在改变 /*还得是最左边一个跳到最右边那种*/ ，进而引发所得循环节的“走马灯”。同理，t{n,k}<n-1时，走马灯现象的产生也是由于余数次序的改变，只因余数种类改变导致“走马灯”种类不同 /*由费马小定理，t{n,k}必为(n-1)的真因子，而走马灯种数为(n-1)/t{n,k}*/ ，但循环节长度依然不变。

在n不是质数，且k进制下，1/n为纯循环小数 /*此时k进制下，n所有质因数的倒数必为纯循环小数*/ 时，1/n的循环节长度又是多少？此时仅需将n分解质因数，再根据余数乘法定理，便可证得其循环节长度为k进制下，n所有质因数倒数的循环节长度的最小公倍数。由P{n,k}的共性，即使n不是质数，也有一定走马灯的性质 /*如1/30=(0.01430143…)7，7/30=(0.14301430…)7，此后每乘7，小数部分就循环一次*/ 。

四、进制中的创新（纯整活）

4.1 坤进制

“巅峰产生虚伪的拥护，黄昏见证虔诚的信徒。”数学界有一练习时长两年半的常数为坤，1坤=2.5。可以把篮球和鸡有理数与整数联系在一起，再根据进制的定义，造出“坤进制”。

在这个新进制中，1还是1，2还是2，而3呢？结果大约是：(10.1011100001101……)坤≈3……

不过，像坤进制，甚至所有大于1的非整数进制，有一个共同的性质：若两个正有理数a,b表示为坤进制后小数点右侧部分为0，左侧部分分别为(m+1)位数与m位数（m∈N*），却不一定说明a>b。接下来是对这个现象的证明。

已知：k进制下a,b小数点右侧为0，左侧分别为(m+1)位数与m位数

求证：∃a,b∈Q，∃m∈N*，使a<b

（a,b,k∈Q，k∉N*，m∈N*，a>0，b>0，k>1）

例如：坤进制中，(100)坤=6.25，(22)坤=7

证明：

设[x]为不超过x的最大整数，则a与b在k进制下每一数位中的数必然小于等于[k]

可令a=k^m，并将a表示为1后连续m个0的形式

可令b=[k](k^m-1)/(k-1)，并将b表示为连续m个[k]的形式

∵k∉N*，k>1

∴[k]/(k-1)>1

∵k^m/(k^m-1)=1/(1-1/k^m)>1，k>1，x∈N*时易得函数f(x)=1/(1-1/k^x)单调递减

∴可得

∴k>1，x∈N*时，f(x)=k^x/(k^x-1)单调递减且收敛于1

∴∃m∈N*，使1<k^m/(k^m-1)<[k]/(k-1)

∴∃m∈N*，使k^m<[k](k^m-1)/(k-1)，此时a<b

Q.E.D.

这就是小数进制难以作常用进制的原因之一，有些整数难以写出来……甚至连比较大小都很麻烦……实在是难以捉摸（个人水平就到这了……）……不过，厉不厉害你鸡坤哥！

4.2 函数进制与数位的命名

一般地，一个k进制数每个数位均为逢k进一，因此能够使k进制下表示为1后连续n个0的整数代表的值为k^n。接下来可以思考：如果不同的数位本应“逢k进一”，所逢的“k”却不一定相同，那么这种计数方法会有怎样的特点呢？

先回忆1.2中的饮料问题。若加一些限制，例如2、5、7号（没错还是没有4杯子不能倒入可乐，又有多少种倒饮料的方法？解决方法就是搁积吧乘法原理，共(4³)*(3³)=1728种。化作数字看待，可以看作一个六位数，且从左往右数，奇数位逢四进一，偶数位逢三进一，能在这种新的进制中表示出1728种不同的数值。为此，可定义一个新概念——函数进制。

函数进制：

f(x)进制中，f(x)定义域为Z，值域为M，M满足M⊆N*，而且

/*说白了就是不能让满足f(x)>1的x值有限*/

其中x<0时，f(x)表示小数点后第|x|位逢f(x)进1，x≥0时，f(x)表示小数点前第(x+1)位逢f(x)进1

例如：2^|x|进制中，1=(10)2^|x|，2=(100)2^|x|，4=(200)2^|x|，0.5=(0.1)2^|x|，1/3=(0.0255A…)2^|x|  /*我们仍未知道1/3在2^|x|进制下是否为循环小数*/

在这几个例子中，数的最末位一直是0，这是因为2^0=1，所以个位上只能填0，要是填1，就会被进到从右往左数的第二位，这个数位，我们依然将其称之为——“个位”。原因很明显，一个数位的名称，取决于在这个数位填1而其他数位均为0时，这个数表示的大小。 /*默认小数点左侧所有数位中离小数点最近的数位为个位*/

所以，f(x)进制中，为防混淆，称默认的个位为初个位。以位于初个位左侧且与之相邻的数位开始，从右往左，第n个个位称为左n个位，并可以通过同样方式命名右n个位。

(2310)2^|x|的值是？此时定义新概念：位峰与位价。若f(x)进制中某数位逢f(x0)进一，则此数位位峰为f(x0)。默认个位的位价为1。f(x)进制中，小数点前第n位（n>1）与小数点后第m位的位价分别等于

特别地，若f(x)=C， /*表示常函数*/ 则f(x)进制中，小数点前第n位（n>1）与小数点后第m位的位价分别为C^(n-1)与C^(-m)。此时，我们便可以位价命名数位，例如2^|x|进制中，(2310)2^|x|的2在8位，3在2位，1在左1个位，2在初个位，将数位上的数分别乘数位的位价，可得(2310)2^|x|=23，此时它意味着2*8+3*2+1*1=2*10+3*1。 /*可通过这种方式命名位价相同的非个位数位，如“左m十位”“右n六分位等”，但不必担心一个数会有多种表示方法，因为无论造成位价相同的那个数位的位价是多少，其位峰必为1，数位上的数字必为0*/

4.3 函数进制中大小的比较与运算的特征

若规定f(x)进制中每一数位的位峰均为整数，则两个f(x)进制的正整数依然能用1.3中的经典比大小方式，根据位数与数位上的数进行比较。对于f(x)进制下的k位整数m，k∈N*，能够轻易得到f(x)进制下，m大于或等于1后连续(k-1)个0所表数值，m小于等于所有数位上的数均为其位峰减一的k位数所表数值，且1后连续k个0的(k+1)位整数减1必等于所有数位上的数均为其位峰减一的k位数。通过这些理论，便可通过数位的多少与数位上数的大小比较两个f(x)进制的整数。同理，f(x)进制小数的大小也可用相同方法比较。

C进制 /*常函数*/ 下，把x乘C，相当于右移小数点一位，除以C则是左移一位，但这种简便运算方式仅对常函数进制有用。乘C本质上是“将所有数位上的数翻C倍，若达到位峰再进位”，而对C进制，可理解为“将所有数位的位价翻C倍再调整小数点”。因此，仅当数位的位峰为C时，这个数位上的数才满足C倍的自己进到下一位上的数依然是自己。但f(x)进制中，只要f(x)不是常函数，这种简单移动小数点的方式就不行，因为必有数位的位峰不是C。

韩信带净化，任何数位终将绳之以法！（梅开二度）依然是用“绳子”把数位“绑起来”，再把被绑在一起的多个数位看作一个整体，位峰为其中所有数位的位峰之积，若是个位，则位价为1，反之，则根据公式定义。而几个小的数位上的数字的大小、排序决定“大数位”上的“数”，也就是这个数值。若f(x)是周期为T的函数，T∈N*，便可T位T位地绑在一起，方便进行运算。

数学对数的思想与认识似乎被几何“骨”化了，只看本质，忘记表面……

（若引用此图片作为封面属侵权，请通知作者本人）