sbs 寫到:2×5=10
3×37=111
4×25=100
.
.
.
證:一個任意自然數a,均可找到a的某倍數,其各位數字皆為0,1所組成
本題可用Euler定理(Euler's theorem,
http://en.wikipedia.org/wiki/Euler%27s_theorem)來處理. Euler 定理是說,對互質的兩數(a,n), 可以找到M, 使得
mod(a^M, n) = 1
mod(x,y) 是 x/y 的餘數.
不過在應用此定理前,我們要先處理對任意數a, 其2與5的質因數. 因為我們知道
1. 任何5的倍數,其個位數不是5,就是0
2. 任何偶數的倍數,還是偶數
所以, 如果a有2或5的質因數,若要符合本題的條件,則必須個位數是0, 也就是說乘積是10的倍數。假設質因數分解有如下的形式:
a = (2^m)(5^n) * b, 其中 (b, 10) 是互質的兩數
則可以先乘以 k = (2^n)(5^m),
a * k = 10^(m+n) b
(注意:此處理並非唯一,例如a = 2*3*5 = 30, 我們其實不必再乘k=10, 就可以繼續下一步驟)
接下來,我們只要專注 b 的處理即可。注意現在(b,10)互質,根據Euler's thorem, 我們可以找到M, 使得
mod(10^M,b) =1,
而且因為互質的關係,對任意正整數i, mod((10^M)^i,b) = 1.
令y = 10^M, 現在考慮一級數 S
S = 10^M + 10^2M + 10^M + ... + 10^(bM) = y + y^2 + ... + y^b
則每項除以b的餘數皆是1, 共有b項,因此S可以被b 整除。而S正好符合題目的要求,因為每一項y^c, 都代表 S 的第cM位數!!!
要注意的是,上述 S並非唯一解。