Quod Erat Demonstrandum

2009/01/19

數尾零

Filed under: mathematics — johnmayhk @ 11:09 上午
Tags: , ,

2009-01-16 學校旅行日,有同學問:找出最大正整數 y 使

\frac{20090116!}{10^y}

是整數,我匆匆答:只要知道 20090116! 有多少個因子 5 便可。

同學不滿我的答案, 且兩天忙,唯到現在才詳解。(是,我知道這是一道很淺的習題,用不著「詳談」,但授課員習慣口水多,高手見諒。)

要找 y 的最大值,相當於找出 20090116! 有多少個「尾零」(zeros at the end)。比如考慮 1230000 這個數,當 y = 1,2,3,4,以下數值都是整數:\frac{1230000}{10^y}. 亦即是,本例中,y 的最大值是 4,即是 1230000 的尾零數目。

易知,比方說,1997 \times 10^{100} 有 100 個尾零。所以 1997 \times 2^{100} \times 5^{100} 也有 100 個尾零。假如整數表成 q \times 5^{100},其中 q 中沒有因子 5,但卻有起碼 100 個因子 2(即存在因子 2^{100}),那麼 q \times 5^{100} 就有 100 個尾零。

總結,若某整數,其因子 2 的數目不少於因子 5 的數目,即該整數的尾零數目,即是因子 5 的數目。

20090116! = 2*3*4*…*20090116

不難「感覺」上述數字的因子 2 數目多於因子 5 的數目(證明從略),那麼只要算數因子 5 的數目,就知道上述數字有多少個尾零。

先給你答案,上述數字,其因子 5 共有

[\frac{20090116}{5}] + [\frac{20090116}{5^2}] + [\frac{20090116}{5^3}] + … 個。

(其中符號 [x] 代表不大於 x 的最大整數,舉例 [3] = 3, [3.1] = 3, [3.9] = 3, [-2.9] = -3 等等。)

為何?讓我以簡單例子入手:數算 254! 有多少個因子 5。

254! = 2*3*4*…*254

讓我列出當中涉及因子 5 的項:

1 \times 5, 2 \times 5, 3 \times 5, 4 \times 5, \dots 50 \times 5

上述各項的第二個數字是 5,共有 50 項。(如何計出 50 呢?就是 [\frac{254}{5}] = 50)

那麼,254! 起碼有 50 個因子 5。我說起碼,因為上述數列,當中有一些項,不止一個因子 5,比如,10 \times 5 = 2 \times 5^2 便有 2 個因子 5 了。不打緊,現在才數算涉及因子 5^2 的項,即

1 \times 5^2, 2 \times 5^2, 3 \times 5^2, 4 \times 5^2, \dots 10 \times 5^2

共 10 項。(如何計出 10 呢?就是 [\frac{254}{5^2}] = 10)

那麼,254! 起碼有 50 + 10 = 60 個因子 5。但這還不夠,還有涉及 3 個因子 5 的項,即

1 \times 5^3, 2 \times 5^3

共 2 項。(如何計出 2 呢?就是 [\frac{254}{5^3}] = 2)

好了,5^4, 5^5, \dots 已不是 254 的因子,於是,254! 的因子 5 共有

[\frac{254}{5}] + [\frac{254}{5^2}] + [\frac{254}{5^3}] = 62 個,也就是說

254! 共有 62 個尾零。

依樣畫葫蘆,20090116! 共有

[\frac{20090116}{5}] + [\frac{20090116}{5^2}] + [\frac{20090116}{5^3}] + … = 5022524 個尾零,即原題目最大的 y 值等於 5022524。(幫我檢查一下吧。)

習題

已知 20090116! = 2^kq,其中 k 是正整數,q 是奇數,求 k 值。

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: