問39
任意の正の整数は，を0か1として， の形に，一意的に表されることを証明せよ．
正の整数は2のべき乗の和で一意的に表せる．
マグロウヒル大学演習シリーズ 微積分(上)の問題39の別解を載せる．
2のべき乗の和で表せられること．
Section titled “2のべき乗の和で表せられること．”正の整数が(2のべき乗の和)の形で表されることを， 正の整数による帰納法により示す．
のとき，において，として表せられる．
のとき，において，として表せられる．
のとき，において，として，と表せられる．
のとき，2のべき乗の和として表せられると仮定する．のときを考える． を2で割った余りを，商をとすると，．
なので，仮定よりは2のべき乗の和の形で表せられる．よって，は2のべき乗の和の形で表せられる． つまり，は2のべき乗の和の形で表せられる．
以上により，帰納法で正の整数が2のべき乗の和の形で表せられることを示した．
一意的に表せられること．
Section titled “一意的に表せられること．”正の整数を以下の2通りに表せられるとする．
を2で割った余りは(1)，(2)で等しいので，．を2で割った商をとすると， このを2で割った余りは(1)，(2)で等しいので，．以降，同様にすると， である．したがって，(1)，(2)は等しい， すなわちは一意的に2のべき乗の和で表せる．