费马小定理的应用-n个1组成的整数能被2013整除，n至少为多大？

2017-03-04 | 分类 blog | 标签算法数论 | 浏览

算法

前言

在逛segmentfault论坛时，看到了这样一个提问，于是花了点时间详细的解答了，顺便记录在本文中。

原题链接https://segmentfault.com/q/1010000008553427/a-1020000008559091

思路与大纲

遇到这个问题时，第一个想法就是先用代码进行暴力破解，然后又发现整数整除问题可以用费马小定理进行分析，于是就有了以下回答题纲:

代码解法(JS实现)
数论解法(费马小定理)

代码解法

function getMinDividedNum(n) {
    var sum = 1,
    len = 1;
    while (sum % n) {
        len++;
        sum = (sum % n) * 10 + 1;
    }
    return len;
}

// 测试用例
// 注意，并不是所有数字都能输入，只能是素数或者由素数乘积组成的数
// 这里就相当于直接人为的约定了输入前提了
var num = 2013;
console.log('n:' + num + ',len:' + getMinDividedNum(num));
// 输出:n:2013,len:60

代码详解

以上代码的核心其实就是判断1,11,111等N位数能否被n整除，也就是sum=sum*10+1。但是考虑到最大值边界问题，于是将上述公式换为了 sum= (sum % n)*10+1

之所以能这样转换，是因为: (举例)

譬如判断 111是否能被3整除
可以是 (1*10+1)*10+1
也可以是判断
- 第一步: 1%3=1 (1整除3的余数为1）
- 第二步: 11%3=2 (11整除3的余数为2）
- 第三步: 21%3=0 (符合条件)
换一个思路，假如判断(8+7)是否能被3整除，那么我们只需要现将它们能被3整除的部分去除掉，用余数累加起来判断即可，也就是说只需要判断2+1能否被3整除即可

数论解法

费马小定理简介

首先得知道的是，费马小定理是欧拉定理的一种特殊情况，欧拉定理描述的是关于同余的性质，而费马定理如下:

假如a是整数，p是质数，且a，p互质(两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1

即a^(p-1)%p=1

费马小定理在本题中的应用

关键来了，本题与费马小定理有什么关系呢？

本题中，2013=3*11*61，所以能被2013整除，就需要满足

能被3整除
能被11整除
能被61整除

而前两者很容易就根据下面的条件判断出:

若一个整数的数字和能被3整除，则这个整数能被3整除。
若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。

因此马上就可以将条件转换为:

n得是3的倍数(因为n个1加起来要是3的倍数)
n得是2的倍数(奇位和偶数直接的差为0)
因此n是6的倍数
这个数(n个1)能被61整除

接下来就剩下了一个问题: n个1能被61整除，需要满足什么？接下来费马小定理就派得上用处了。

我们可以得知: 61和10互素。所以套用上述的公式，可以得出: 10^(60)%61=1，即10^(60)=1 (mod 61) 所以:10^(60)-1=0 (mod 61) 而10^60 -1 就是60个9组成的数，也就是说 60个9组成的数能够被61整除。那么自然60个1组成的数能够被61整除(因为61与3无关)。同时60又是6的倍数，因此60个n组成的数能够被2013整除。

继续判断，费马小定理并不保证(p-1)是最小的指数，但是一定是最小指数的倍数。所以继续判断60的约数，60的符合条件的约数(6的倍数)有，6，12，30，60。依次计算6,12,30这三个数，发现都不满足条件，于是得出只有60满足条件。

因此得出了结论: n至少为60时，n个1组成的数能够被2013整除