Aggressive Style 5

読者です 読者をやめる 読者になる 読者になる

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

今日の問題(6):頭の体操にぴったりの整数問題(07京都高校生数学コンテストより)

今日もTwitter「数学問題bot(@mathematics_bot)」さんより、以下俺の数学のど自慢につき合って下さい。整数の問題につき解答の論証に不備がある場合は、是非是非ご連絡を。

問題


2007^1,2007^2,…,2007^2007のうち一の位が7となる数は全部でいくつあるか。(07京都高校生数学コンテスト)




















解答

まず二項定理より(2000+7)^n = nC0 * (2000)^n + nC1 * 7 * (2000)^n-1 +……+nCn * 7^nより7^n以外の全ての項は一の位以外の自然数として計算できる。このことからa_n = 7^n、その一の位をb_nとおく。

さてa_1=7,a_2=49,a_3=343,a_4=2401,a_5=16807よりb_1=7,b_2=9,b_3=3,b_4=1,b_5=7。この事からb_nは周期4で繰り返す事が分かる。以下kを自然数としてn=(4k+1)のときb_n=7となる事を、数学的帰納法により証明する。

証明


(i)n=1のとき、a_1=7よりa_1≡7=b_1 (mod 10)より確かに成立する。

(ii)n=(4k+1)のとき、a_(4k+1) ≡7=b_(4k+1) (mod 10)と仮定すると、



a_(4k+2) ≡7 * 7^k ≡ 7 * 7 ≡ 9 = b_(4k+2) (mod 10)

a_(4k+3) ≡7 * 7^k+1 ≡ 7 * 9 ≡ 3 = b_(4k+3) (mod 10)

a_(4k+4) ≡7 * 7^k+2 ≡ 7 * 3 ≡ 1 = b_(4k+4) (mod 10)

a_(4k+5) ≡7 * 7^k+3 ≡ 7 * 1 ≡ 7 = b_(4k+1) (mod 10)

よりn=4k+5=4(k+1)+1のときでも確かに成立する。以上(i)(ii)よりa_(4k+1) = 7が成立する。

以上よりb_nは周期4で繰り返すので、4k+1 < 2007 ∴k<501.5より501(個)(答)

感想

しらみつぶしに解を探そうと思ってC言語(http://ideone.com/qOkCBI)を走らせたら、7^nは指数関数なので桁あふれの処理が上手く行かなくてこまりましたね。Excelでだと上手く行ったんですが。後「ある自然数の累乗の一の位を求めさせる」問題も多く、この他「3^225の1の位を求めよ(yahoo知恵袋)」などもあったりですね。恐らく整数論の文献を漁ってみると、本問の一般的な性質が書かれていそうな点も面白いですね。

過去記事