全一数整除性

只包含数字1的数称为全一数，记$R(k)$为长度为k的全一数，例如$R(6)=111111$。 若n是满足$\gcd(n,10)=1$的整数，那么总存在k使得$R(k)$能被n整除，记$A(n)$是这些k中最小的一个。例如，$A(7)=6$，$A(41)=5$。 使得$A(n)$第一次超过十的n是17，使得$A(n)$第一次超过一百万的n是多少？

本题难度:

解答

将n写作 $$n=\gcd(9,n)m,$$ 并令k为最小的、满足 $$10^k\equiv 1 \pmod m,$$ 的数，则k就是10在模m乘法群中的阶，因此k能整除欧拉totient函数$\varphi(m)$。 注意到$9R(k)=10^k-1$， 因而若$\gcd(9,n)=1$， 则显然$A(n)=k$。 否则若$\gcd(9,n)>1$，则有两种情况： 若$\gcd(9,n)$能整除k，则由于k是$R(k)$的各位数字之和且$\gcd(9,n)$是3或9，$R(k)$也将能被$\gcd(9,n)$整除，从而$A(n)$也仍等于k。 若$\gcd(9,n)$不能整除k，则利用如下定理 定理：当且仅当$\gcd(p,q)=1$时有$\gcd(R(p),R(q))=1$。 可知$A(n)=tk$，其中t是最小的能令d整除tk的数，即 $$t=\begin{cases}3 & 若d=3，或d=9且k模9余3, \\ 9 & 其它.\end{cases}$$ 要解决本题，还需要一些启发式的手段： 在$(10^6-1)/9$和$(10^6-1)/3$附近搜索素数作为m，这是因为若m是素数，则$\varphi(m)=m-1$，且其乘法群是循环群，较有可能使得$k=m-1$，也较易验证k是否等于$m-1$。 比111111大的最小素数是111119，$\varphi(111119)=111118$模9余4，而$111119\times 9=1000071$。 比333333大的最小素数是333337， 不过$\varphi(333337)=333336$能被$3$整除，从而需要被排除。 比333333大的第二个素数是333341，$\varphi(333341)=333340$不能被3整除，且$333341\times 3=1000023 < 1000071$，此外，用例如wolfram alpha容易验证$k=333340$，因此$n=333341\times 3=1000023$就是所需的结果。 本题无需编程。 注：本题涉及的模m乘法群相关知识一般涵盖在本科水平的代数数论或抽象代数课程中。