1/n 与 n-1 位循环节

发表于 分类于

142857

近期刷到了一个视频，说 142857 这串数字如何的神秘，与古埃及有如何如何的关系。由于它分别乘以 1~6 都还是这串数，所以叫什么走马灯数，如何如何。抛开神秘学话题，这就是简单的 1/7 循环节：

1/7 Circle

不过『走马灯数』这个概念还是有点意思的。它最显著的特征是循环节长度 = n-1，同时附带的性质是当乘以 $1, 2, 3, \cdots, n-1$ 时，循环节顺序和长度不变，只是起始位置换了一下。因此写了段程序简单搜索一下还有没有其它的 n 也有这个特征。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const loop = (n) => {
    let a = 1
    let pool = new Set()
    
    while (true) {  
        let digi = (a / n) | 0
        a = a % n * 10 
        if (a == 0) { return "" }   // 除尽没有循环节
        if (pool.has(a)) {          // 当余数作为被除数曾出现过，新的循环节开始。
            let loop = [...pool]
            let index = loop.findIndex(i => i == ele)
            let str = loop.slice(index).map(e => e % 10).join('')
            return str
        } else {
            pool.add(ele)
        }
    }
}

let start = 7
while (start < 1000) {
    let str = loop(start)
    if (str.length == start - 1) { console.log(start, str) }
    start++
}

结果出人意料地多：

1/n 循环节
1/7 142857
1/17 0588235294117647
1/19 052631578947368421
1/23 0434782608695652173913
1/29 0344827586206896551724137931
1/47 0212765957446808510638297872340425531914893617
1/59 0169491525423728813559322033898305084745762711864406779661
1/61 016393442622950819672131147540983606557377049180327868852459
1/97 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567
1/109 009174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211
1/113 0088495575221238938053097345132743362831858407079646017699115044247787610619469026548672566371681415929203539823
1/131 0076335877862595419847328244274809160305343511450381679389312977099236641221374045801526717557251908396946564885496183206106870229
1/149 0067114093959731543624161073825503355704697986577181208053691275167785234899328859060402684563758389261744966442953020134228187919463087248322147651
1/167 0059880239520958083832335329341317365269461077844311377245508982035928143712574850299401197604790419161676646706586826347305389221556886227544910179640718562874251497
1/179 0055865921787709497206703910614525139664804469273743016759776536312849162011173184357541899441340782122905027932960893854748603351955307262569832402234636871508379888268156424581
1/181 005524861878453038674033149171270718232044198895027624309392265193370165745856353591160220994475138121546961325966850828729281767955801104972375690607734806629834254143646408839779
1/193 005181347150259067357512953367875647668393782383419689119170984455958549222797927461139896373056994818652849740932642487046632124352331606217616580310880829015544041450777202072538860103626943
1/223 004484304932735426008968609865470852017937219730941704035874439461883408071748878923766816143497757847533632286995515695067264573991031390134529147982062780269058295964125560538116591928251121076233183856502242152466367713
1/229 004366812227074235807860262008733624454148471615720524017467248908296943231441048034934497816593886462882096069868995633187772925764192139737991266375545851528384279475982532751091703056768558951965065502183406113537117903930131
1/233 0042918454935622317596566523605150214592274678111587982832618025751072961373390557939914163090128755364806866952789699570815450643776824034334763948497854077253218884120171673819742489270386266094420600858369098712446351931330472103
1/257 0038910505836575875486381322957198443579766536964980544747081712062256809338521400778210116731517509727626459143968871595330739299610894941634241245136186770428015564202334630350194552529182879377431906614785992217898832684824902723735408560311284046692607
1/263 0038022813688212927756653992395437262357414448669201520912547528517110266159695817490494296577946768060836501901140684410646387832699619771863117870722433460076045627376425855513307984790874524714828897338403041825095057034220532319391634980988593155893536121673
1/269 0037174721189591078066914498141263940520446096654275092936802973977695167286245353159851301115241635687732342007434944237918215613382899628252788104089219330855018587360594795539033457249070631970260223048327137546468401486988847583643122676579925650557620817843866171
1/313 003194888178913738019169329073482428115015974440894568690095846645367412140575079872204472843450479233226837060702875399361022364217252396166134185303514376996805111821086261980830670926517571884984025559105431309904153354632587859424920127795527156549520766773162939297124600638977635782747603833865814696485623
1/337 002967359050445103857566765578635014836795252225519287833827893175074183976261127596439169139465875370919881305637982195845697329376854599406528189910979228486646884272997032640949554896142433234421364985163204747774480712166172106824925816023738872403560830860534124629080118694362017804154302670623145400593471810089020771513353115727
1/367 002724795640326975476839237057220708446866485013623978201634877384196185286103542234332425068119891008174386920980926430517711171662125340599455040871934604904632152588555858310626702997275204359673024523160762942779291553133514986376021798365122615803814713896457765667574931880108991825613079019073569482288828337874659400544959128065395095367847411444141689373297
1/379 002638522427440633245382585751978891820580474934036939313984168865435356200527704485488126649076517150395778364116094986807387862796833773087071240105540897097625329815303430079155672823218997361477572559366754617414248021108179419525065963060686015831134564643799472295514511873350923482849604221635883905013192612137203166226912928759894459102902374670184696569920844327176781
1/383 0026109660574412532637075718015665796344647519582245430809399477806788511749347258485639686684073107049608355091383812010443864229765013054830287206266318537859007832898172323759791122715404699738903394255874673629242819843342036553524804177545691906005221932114882506527415143603133159268929503916449086161879895561357702349869451697127937336814621409921671018276762402088772845953
1/389 0025706940874035989717223650385604113110539845758354755784061696658097686375321336760925449871465295629820051413881748071979434447300771208226221079691516709511568123393316195372750642673521850899742930591259640102827763496143958868894601542416452442159383033419023136246786632390745501285347043701799485861182519280205655526992287917737789203084832904884318766066838046272493573264781491
1/419 0023866348448687350835322195704057279236276849642004773269689737470167064439140811455847255369928400954653937947494033412887828162291169451073985680190930787589498806682577565632458233890214797136038186157517899761336515513126491646778042959427207637231503579952267303102625298329355608591885441527446300715990453460620525059665871121718377088305489260143198090692124105011933174224343675417661097852028639618138424821
1/433 002309468822170900692840646651270207852193995381062355658198614318706697459584295612009237875288683602771362586605080831408775981524249422632794457274826789838337182448036951501154734411085450346420323325635103926096997690531177829099307159353348729792147806004618937644341801385681293302540415704387990762124711316397228637413394919168591224018475750577367205542725173210161662817551963048498845265588914549653579676674364896073903
1/461 0021691973969631236442516268980477223427331887201735357917570498915401301518438177874186550976138828633405639913232104121475054229934924078091106290672451193058568329718004338394793926247288503253796095444685466377440347071583514099783080260303687635574837310195227765726681127982646420824295010845986984815618221258134490238611713665943600867678958785249457700650759219088937093275488069414316702819956616052060737527114967462039045553145336225596529284164859
1/487 002053388090349075975359342915811088295687885010266940451745379876796714579055441478439425051334702258726899383983572895277207392197125256673511293634496919917864476386036960985626283367556468172484599589322381930184804928131416837782340862422997946611909650924024640657084188911704312114989733059548254620123203285420944558521560574948665297741273100616016427104722792607802874743326488706365503080082135523613963039014373716632443531827515400410677618069815195071868583162217659137577
1/491 0020366598778004073319755600814663951120162932790224032586558044806517311608961303462321792260692464358452138492871690427698574338085539714867617107942973523421588594704684317718940936863543788187372708757637474541751527494908350305498981670061099796334012219959266802443991853360488798370672097759674134419551934826883910386965376782077393075356415478615071283095723014256619144602851323828920570264765784114052953156822810590631364562118126272912423625254582484725050916496945010183299389
1/499 002004008016032064128256513026052104208416833667334669338677354709418837675350701402805611222444889779559118236472945891783567134268537074148296593186372745490981963927855711422845691382765531062124248496993987975951903807615230460921843687374749498997995991983967935871743486973947895791583166332665330661322645290581162324649298597194388777555110220440881763527054108216432865731462925851703406813627254509018036072144288577154308617234468937875751503006012024048096192384769539078156312625250501

简化代码并扩大计算量搜索后，得到 100 万以内的走马灯数分布：

1
2
3
4
5
6
7
8
const n_devide_len = (n) => {
    let a = 1, pool = new Set()
    while (true) {
        a = a % n * 10
        if (a == 0) { return 0 }
        if (pool.has(a)) { return pool.size } else { pool.add(a) }
    }
}

100 万以内的走马灯数分布

有点意思。

研究原因

对于任意由 1/n 形成的循环小数，$\frac{1}{n} = 0.\overline{******}$，设循环节部分为 r，其长度为 l，都可以写成一个无穷级数之和：

$$\frac{1}{n} = \frac{r}{10^l}+\frac{r}{10^{2l}}+\cdots+\frac{r}{10^{kl}} +\cdots = \sum_{k=1}^\infty\frac{r}{10^{kl}}$$

对这个无穷等比数列重新求和，$S=1/n$，$10^l * S-S = r$，得到 $S = \frac{r}{10^l-1} = \frac{1}{n}$，所以 $n=\frac{10^l - 1}{r}$ ，或者写成 $r=\frac{\overbrace{999\cdots999}^l}{n}$，根据前面的推导过程，这里的 r 一定是整数。这个方法同时也是将循环小数化为分数的标准方法。

  • 当 $n = 7, l = 6$ 时，也就得到了 $142857 = \frac{\overbrace{999999}^6}{7}$，所以 $1/7 = 0.\overline{142857}$

  • 当 $n = 3, l = 2$ 时，得到 $r = \frac{99}{3} = 33$，所以 $1/3 = 0.\overline{33}$，逻辑上其实也是对的，只是一般来说小数循环时只考虑最小周期，所以正确的写法应该是 $1/3 = 0.\overline{3}$。

  • 当 $n = 11, l= 10$ 时，得到 $r = \frac{9999999999}{11} = 0909090909$，要注意这是循环节的计算因此首位的 0 不能去掉，所以 $1/11 = 0.\overline{0909090909}$，正写为 $1/11=0.\overline{09}$

对于 $1/6 = 0.1\overline{6}$ 这类存在非循环小数部分的，可以通过乘 10 等操作，把非循环部分移到整数上并抛弃，即化为 $10/6 \rightarrow 4/6 = 2/3 = 0.\overline{6}$，考察 $0.\overline{6}$ 即可。

同余

在上述 $n=3, n=11$ 两个例子中，虽然得到了逻辑上可行的循环节，但不符合通常的习惯，所以在结果上进行了缩减，变为符合习惯的最小循环节。

  • $10^k-1$ 本身就是 3 的倍数，所以循环节永远只有一位。

  • 11 因其自身的特殊性质，11 = 10 + 1，天然地符合 10 为底的级数的结构，如果一个数字各位数值相同，那么奇数位数字对 11 都是同余的，偶数位也是。所以 $10^k-1 (mod\ 11)$ 只有两个结果 9 和 0。并且在两者间不断跳转。

可见，循环节长度即是最早出现同余时的 k 值，若要 1/n 的循环节长度为 n-1，需要 $10^k (mod\ n)$ 在 $k = 1, \cdots, n-1$ 时都不同余。

进制

从上可见，循环小数与进制密切相关。例如在 8 进制中，9（在 8 进制中也写为 11）的性质将和 10 进制中的 11 相似，也会出现奇位同余偶位同余的情况。所以 $1/11_{(8)} = 0.\overline{07}_{(8)}$，形式上完全一致。

而 $1/7_{(8)}$ 则变为了 $0.\overline{1}_{(8)}$，因为 $8^k-1_{(8)} = {\overbrace{77\dots7}^{k}}_{(8)}$ 各位恒为 7，也就不存在什么神秘数字循环了。

由于和进制本身高度相关，因此某个 1/n 是否有 n-1 位循环节，取决于它和进制 $R^k - 1$ 之间的相除结果，这个关系不知道数论中是否已有结论。

推论

  • 由于 n-1 位循环节一定存在，只是未必最短。而在 n- 1 基础上的缩减不会破坏原有模式，因此最小循环节长度一定是 n-1 的因数。

  • 只有当 n 为素数时，才有可能出现 n-1 位循环节。由于余数需要遍历 1 到 n-1 的所有数。若 n = pq，余数会在 q-1 与 p-1 的共同作用下循环，但 p-1 与 q-1 至少含有公因素 2，不可能产生所有 {0, p-1} 与 {0, q-1} 之间的全部两两组合。

  • 一切循环节在若干次乘 10 排除不循环部分，整理为 $0.\overline{******}$ 形式后，都可以用 $a * 1/n$ 来表示。

  • 如果 n 为素数，而其循环节长度 $l$ 不为 $n-1$，则必有互相不能抵达的 $\frac{n-1}{l}$ 套循环，进入哪套循环取决于分子 $a$ 的值。因为素数没有因数，$a/n (a=1, 2,\dots, n-1)$ 必然有 n-1 个不同余数。实例如 $1/3=0.\overline{3}$ 和 $2/3=0.\overline{6}$。

  • 如果 n 为素数，则 1/n 的循环节必然形如 $0.\overline{******}$，从小数点后就开始，即使起始是若干个 0 也是循环节的一部分。

  • 如果 n 是若干个不同素数乘积，则循环节长度是这些素数对应的循环节长度的最小公倍数。如果 n 是素数 p 的 k 次方，则循环节长度是 $l * p^{k-1}$，但如果 $p=3$，则为 $l * p^{k-2}$。以上两者可以结合。$p=3$ 的特例在于 $p^2=9$ 仍然小于 10，没有触发进退位，即当 p^k 仍小于对应进制单位时，不往上叠加循环节长度。在 8 进制下就是正常的 $l*p^{k-1}$ 了。

  • 不存在比 n-1 更长的循环节。

  • 不同进制下的走马灯数具体是不一样的，例如 7 在 10 进制下是走马灯数，但在 8 进制下则不是。2 在一切奇数进制下都是走马灯数，因为只需要循环节长度为 1 但不除尽即可。

  • 除 2 以外，走马灯数的循环节长必度是偶数，将循环节的两段拆分后相加，一定是 $999\cdots$。例如 $1/7 = 0.\overline{142857}$，则 $142 + 857 = 999$。上述结论在其它进制下也成立，例如 8 进制下为 $777\cdots_{(8)}$。

    证明：设一个循环小数 $\frac{1}{p}$ 的循环节两段分别为 $\overline{r_1r_2}$，则其既可以表达为

    \begin{align*} \frac{1}{p} = \frac{r_1r_2}{10^{2n}} + \frac{r_1r_2}{10^{4n}} + \cdots + \frac{r_1r_2}{10^{kn}}+\cdots = \frac{r_1r_2}{10^{2n}-1} &&(1) \end{align*}

    也可以表示为：

    \begin{align*} \frac{1}{p} =\frac{r_1}{10^n} + \frac{r_2r_1}{10^{3n}} + \cdots + \frac{r_2r_1}{10^{(k+1)n}}+\cdots &&(2) \end{align*}

    $(2)$ 式乘以 $10^n$ 再加 $(1)$ 式，得到：

    \begin{align*} \frac{(10^n+1)}{p} = r_1 + \frac{(r_1+r_2)(10^n+1)}{10^{2n}-1} = r_1 +\frac{r_1+r_2}{10^n-1} &&(3) \end{align*}

    再将 $(1)$ 式分子分母同除 $10^n+1$ 得到：

    \begin{align*}
    &&\frac{1}{p} = \frac{r_1r_2}{10^{2n}-1} = \frac{r_1r_2/(10^n+1)}{(10^{2n}-1)(10^n+1)} = \frac{\frac{r_1r_2}{10^n+1}}{10^n-1} &&(4) \\
    \Rightarrow &&\frac{r_1r_2 * p}{10^n+1} = 10^n-1 &&(5)
    \end{align*}

    $r_1r_2 / (10^n+1)$ 不可能为整数，否则 $(4)$ 直接可以化简：

    \begin{align*} \frac{1}{p} = \frac{\frac{r_1r_2}{10^n+1}}{10^n-1} = \frac{r_x}{10^n-1} &&(6) \end{align*}

    循环节直接可以减少一半，这与之前的假设不符。因此在 $(5)$ 式中，$p$ 与 $(10^n+1)$ 必然存在公因数。而 p 为素数，则 $(10^n+1)$ 为 $p$ 的倍数。即 $(3)$ 式中 $\frac{(10^n+1)}{p}$ 为整数。

    因此，$r_1 + \frac{r_1+r_2}{10^n-1}$ 为整数。$r_1$ 本来就是提出来的整数部分，而 $\frac{r_1+r_2}{10^n-1}$ 是由两个小数部分加和得到，要求其为整数只可能是 1。所以 $r_1+r_2 = 10^n-1 = 999\cdots$

    得证。其它进制只需要将 10 底替换为对应进制即可。

计算程序

走马灯数搜索程序在得到以上结论后可以提升一些效率：

  • 使用 欧拉筛法，只在素数堆里进行验证。
  • 如果循环节小于 n-1，由于推论 1，则其至多 $\frac{n-1}{2}$，因此当计算到第 $\frac{n+1}{2}$ 项时，便可得出结论而不必计算后半段。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function searchCarousel(n) {

    let primes = [];
    let eularboard = new Array(n + 1).fill(true);
    let carousels = []

    const isCarousel = (p, radix = 10) => {
        let a = 1, pool = new Set(), end = (p + 1) / 2
        while (pool.size < end) {
            a = a % p * radix
            if (a == 0) { return false }
            if (pool.has(a)) { return false } else { pool.add(a) }
        }
        return true
    }

    for (let i = 2; i <= n; i++) {
        if (eularboard[i]) {
            primes.push(i);
            if (isCarousel(i)) { carousels.push(i) }
        }
        for (let j = 0; j < primes.length; j++) {
            if (i * primes[j] > n) break;           // 上限判断
            eularboard[i * primes[j]] = false;
            if (i % primes[j] === 0) break;         // 跳过本轮后续筛选
        }
    }

    return carousels
}

console.log(searchCarousel(1000))
// [7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233,  257, 263,
// 269, 313, 337, 367, 379, 383, 389, 419,  433, 461, 487, 491, 499, 503, 509, 541, 571, 577,  593, 619,
// 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983]

其它进制

根据前文继续厘清思路，在其它进制下：

  • 循环节长度的度量和进制数无关，表述形式不改变数值大小，在 10 进制下若为 16，在 8 进制下就写为 20，但都指的是同一个值。
  • 但循环节的生成和进制有关，在当前位下不满足该进制条件下的整除，产生余数，就会退到下一位。
  • 在其它进制下，$r = \frac{R^{n-1}-1}{n}$ 仍然成立，这是循环小数定义公式的变形。
  • 仍然只需要在素数表中搜索走马灯数，因为 r 需要由 $\frac{k}{n},k=1,2,\dots,n-1$ 来确保循环长度上限。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 计算各进制下的走马灯数 */
function searchCarousel(n) {
    let primes = [];
    let eularboard = new Array(n + 1).fill(true);
    for (let i = 2; i <= n; i++) {
        if (eularboard[i]) { primes.push(i) }
        for (let j = 0; j < primes.length; j++) {
            if (i * primes[j] > n) break;           // 上限判断
            eularboard[i * primes[j]] = false;
            if (i % primes[j] === 0) break;         // 跳过本轮后续筛选
        }
    }

    const isCarousel = (p, radix = 10) => {
        if (p === 2 && radix % 2 !== 0) return true // 2 在奇数进制下必然是 1 位循环
        let a = 1, pool = new Set(), end = (p + 1) / 2
        while (pool.size < end) {
            a = a % p * radix
            if (a == 0) { return false }
            if (pool.has(a)) { return false } else { pool.add(a) }
        }
        return true
    }

    for (thisRadix = 2; thisRadix < 100; thisRadix++) {
        let carousels = []
        for (let i = 0; i < primes.length; i++) {
            if (isCarousel(primes[i], thisRadix)) { carousels.push(primes[i]) }
        }
        console.log(thisRadix, carousels.length)
    }
}
searchCarousel(10000)

搜索在各不同进制下， 10000 以内的走马灯数的数量，结果如下：

进制 走马灯数数量 进制 走马灯数数量 进制 走马灯数数量 进制 走马灯数数量 进制 走马灯数数量
21 447 41 460 61 457 81 1
2 470 22 472 42 476 62 482 82 455
3 477 23 459 43 490 63 457 83 453
4 0 24 461 44 460 64 0 84 466
5 493 25 1 45 483 65 477 85 468
6 470 26 455 46 445 66 469 86 464
7 466 27 278 47 477 67 471 87 478
8 277 28 451 48 468 68 459 88 454
9 1 29 465 49 1 69 461 89 470
10 467 30 488 50 471 70 473 90 478
11 444 31 469 51 471 71 471 91 453
12 459 32 372 52 460 72 470 92 464
13 458 33 474 53 470 73 465 93 446
14 459 34 473 54 471 74 447 94 485
15 454 35 461 55 486 75 471 95 462
16 0 36 0 56 461 76 467 96 464
17 451 37 466 57 451 77 449 97 471
18 472 38 466 58 478 78 451 98 459
19 473 39 489 59 465 79 466 99 476
20 487 40 458 60 455 80 490 100 0

这里最有特点的是当进制为偶数的完全平方时，没有走马灯数，当进制为奇数的完全平方时，只有唯一一个走马灯数 2，循环节长度为 1。

特殊进制 $R=s^2$

无论在哪种进制下，循环节公式 $r = \frac{R^{n-1}-1}{n}$ 都仍然是成立的。其中 $R$ 为指定的进制数，$n$ 为测试数字， $r$ 为对应的循环节。根据前文所述，在一些情况下循环节会缩减。即当 r 的数字序列内部出现重复时，需要用更短的循环节代替。前文 $\frac{1}{11} = 0.\overline{0909090909} = 0.\overline{09}$ 便是例子。

而当 $R$ 为完全平方数 $s^2$ 时，将循环节公式展开为；

$$ r_{(R)} = \frac{(s^2)^{n-1}-1}{n} = \frac{(s^{n-1}+1)(s^{n-1}-1)}{n} = (s^{n-1}+1) \cdot \frac{s^{n-1}-1}{n}$$

因为 $s$ 是整数，注意到 $\frac{s^{n-1}-1}{n}$ 实际上是在 $s$ 进制下的 $\frac{1}{n}$ 的循环节表达式 $r_{s(s)}$，必定是有整数解的，并且在 $s$ 进制下的长度至多为 $n-1$ 。

现在将 $r_{s}$ 的数值从 $s$ 进制转到 $R$ 进制。因为$R=s^2$，$R$ 进制下一位数值可以容纳 $s$ 进制下两位。其长度在转换后正好一半 $\frac{n-1}{2}$，n 为素数。则：

$$r_{(R)} =(s^{n-1} + 1) * r_{s(s)} \overset{s\rightarrow R}{=\!=\!=} (R^{\frac{n-1}{2}} + 1) * r_{s(R)}$$

除 2 以外的 n 都是素数，所以 $\frac{n-1}{2}$ 是整数，$(R^{\frac{n-1}{2}} + 1)$ 是形如 $\overbrace{100\cdots01}^{(n+1)/2}$ 的整数，长度上正好使 $r_{s(R)}$ 重复两遍，而不会有叠加进位。

因此当进制 $R$ 为完全平方数时，任意 $n$ 的 $r_{(R)} = \frac{R^{n-1}-1}{n}$ 数字序列至少会内部重复一次，所以长度一定小于 $n-1$，也就不存在跑马灯数。

推论：当进制 $R=s^{(2^n)}$ 时，对应的最长循环节为 $\frac{n-1}{2^n}$ 向上取整。

费马小定律

在前文中数次使用 $r=(R^{n-1}-1)/n$，并且认定它是整数，是因为该式是从循环节的级数表示法计算出来的，而循环节本身一定是 n-1 位的整数，所以认为是整数。这个推论是单薄的，不能证明任意 $(R^{n-1}-1)/n$ 一定是整数。但其实关于这一点的正向证明早就在三百多年前就被书空白写不下学家完成了：

$(R^{n-1}-1)/n$ 为整数，其实本身就是 费马小定理 的一部分，即：

  • 假如 $a$ 是整数，$p$ 是素数，那么 $a^p \equiv a (mod\ p)$
  • 如果 $a$ 不是 $p$ 的倍数，则 $a^{p-1} \equiv 1 (mod\ p)$，这其实就是我们用的循环节公式。
  • 如果 $a$ 是 $p$ 的倍数，则 $a^{p-1} \equiv 0 (mod\ p)$，这时就除尽不构成循环节了。

我们之前提到，进制的转换会影响循环节数字序列的变化，但不影响素数、整除等基于数本身的性质，因此这里的 R 在整除判定上反而和进制本身没什么关系，就是一个单纯的幂底数。