|
a, b, nは正の整数で, b > 1 かつ b^n−1 は a の約数であるとする.
a を b進法で表わした場合, 0 でない数字 (文字) が少なくとも n 個あることを証明せよ.
解答
・わたしの…
b進法で、b^n-1は…
111…111 と1がn個並んでる…
aはこの倍数だから…1〜b-1倍なら明らか…
b倍でも…
111…1110・・・1はn個
kb倍…k=1〜b-1 倍も最初に還元され…
k=bはb倍に還元される…
以下同様…
^^
↓
・鍵コメN様からのもの Orz〜
帰納法で示します。f_kをk次のb進数だとします。
k=n-1のときは、すべての桁がb-1でないと、b^n-1で割り切れません。 よって、0でない数字はn個必要となり、題意が成立します。 k=m のときに題意が成り立つと仮定します。 k=m+1のときに、b^n-1で割り切れるとします。 b^(m+1)≡b^(m+1-n) (mod b^n-1)なので、f_m(b)をm次のb進数だとすると、1≦a≦b-1として、 f_{m+1}(b)= a・b^(m+1)+f_m(b) ≡a・b^(m+1-n) + f_m(b) (mod b^n-1)・・・(あ) N(f_m)をm次のb進数における0でない係数の個数だとします。また、f'_m(b)=a・b^(m+1-n) + f_m(b) とします。
(あ)より、N(f_{m+1})=N(f_m) + 1 f_m(b)のb^(m+1-n)の係数とaの和がb-1以下であるならば、(あ)はm次以下のb進数となり、 仮定より、N(f'_m)≧n 。また、N(f'_m)≦N(f_m)+1なので、N(f_{m+1}) ≧ n f_m(b)のb^(m+1-n)の係数とaの和がb以上であるとき、桁が繰り上がりますが、f'_m(b)がm次のb進数になる場合は、 N(f'_m)≦N(f_m)+1となり、帰納法の仮定より、N(f'_m)≧n よって、N(f_{m+1}) ≧ n 繰り上がった結果がm+1次のb進数になる場合は、f_mにおいて、b^(m+1-n)以降のべきの桁が全てb-1になっている必要があるため、N(f_m)≧nとなり、 N(f_{m+1}) > n よって、k=mのときも0でない数字は、少なくともn個必要となります。 以上により、帰納法が成立し、題意が示せました。 *わたしゃ未だ咀嚼できてなかったりします…^^;…Orz〜 |
- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用
コメント（2）
