[高中]倍數證明

[高中]倍數證明

sbs 於 星期四 十月 03, 2013 3:57 pm


2×5=10
3×37=111
4×25=100
.
.
.
證:一個任意自然數a,均可找到a的某倍數,其各位數字皆為0,1所組成

sbs
初學者
初學者
 
文章: 9
註冊時間: 2013-10-03

Re: [高中]倍數證明

lskuo 於 星期四 十月 10, 2013 9:08 am


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並非唯一解。

lskuo
專 家
專 家
 
文章: 218
註冊時間: 2010-11-10

[高中]謝函

sbs 於 星期四 十月 10, 2013 10:30 am


感謝 lskuo大的詳細且耐心解題!!

sbs
初學者
初學者
 
文章: 9
註冊時間: 2013-10-03






高中數學問題