壊
壊れた扉さん (8ewhcx4n)2022/8/3 11:59 (No.493729)削除これおかしくないですか。
問題
aを正の整数とする。このとき、任意の正の整数k(k>1)に対してaは
a=rnk^n+rn-1k^(n-1)+・・・+r1k+r0
0<rn<k,0≦rn-1<k,・・・,0≦r1<k,0≦r0<k
という形に一意的に表されることを証明せよ。aをこのような形に表すことをaのk進法表示という。
証明
(1)表されること:aについての帰納法で示す。a=1のとき、1=1でr0=1とすればよい。
a>1として、a-1まで成り立つと仮定する。aを超えないkの累乗のうち、最大のものをk^nとする。k^n≦a<k^(n+1)よりk^(n-1)≦a/k<k^n ゆえに、k^(n-1)≦[a/k]<k^n ここで、[a/k]<aであるから帰納法の仮定より、
[a/k]=rnk^(n-1)+rn-1k^(n-2)+・・・+r2k+r1
0<rn<k,0≦rn-1<k,・・・,0≦r2<k,0≦r1<k
と表される。さらに、練習問題9(4)よりaはa=[a/k]+r0(0≦r0<k)と表されるから、この式に上式を代入すると次が得られる。
a=k(rnk^(n-1)+rn-1k^(n-2)+・・・+r2k+r1)+r0
=rnk^n+rn-1k^(n-1)+・・・+r2k^2+r1k+r0
(2)一意的であること:a=1のとき、表現が一意的であることは容易にわかる。
a>1として、a-1まで正しいと仮定する。このとき、
rnk^n+rn-1k^(n-1)+・・・+r2k^2+r1k+r0=0 ⇒ rn=rn-1=・・・=r0=0を示せば十分である。仮定の式を変形すると、
rn+rn-1k^(n-1)+・・・+r2k^2+r1k=-r0
ゆえに、r0≡0(modk)ここで、0≦r0<kであるからr0=0 したがって、
rnk^(n-1)+rn-1k^(n-2)+・・・+r2k+r1=0
帰納法の仮定より、rn=rn-1=・・・=r1=0
演習問題9(4)
a,b∈Z,b>0,a=[a/b]b+(a-[a/b]b)
(引用終わり)
因みに、(2)だけです。(検索はしていません。)
おまけ