题目

求初等数论证明：
对于任何一个大于1的整数,其转换为二进制后的位数一定小于等于其分解质因数后各质因数转换为二进制后位数之和.
例：
（4）10 =（100）2 ——3位
4=2*2
（2）10 = （10）2 ——2位
2+2=4（位）
3位

提问时间：2021-02-26

答案

只需要证明任意2个二进制数相乘后位数小于等于原来2个二进制数之和
然后对因式分解后因数个数归纳即可
设原来2个二进制数a,b分别为i,j位i,j>=1
c=a*b,只需要证明c最多只有i+j位
这两个二进制数可表示为a=1?...?(i-1 个?,?表示1或者0）b=1?.?（j-1个?）
c=ab<10.0(i个0）*1000...0(j个0）=1000...000（i+j个0）因为1000...000是最小的i+j+1位数
所以c最多只有i+j位