求证:任意给定一个正整数n,一定可以将它乘以适当的整数,使得乘积是完全由0和7组成的数。 5
展开全部
法一:只有0和7组成的数除以7,就能变为只有0和1组成的数,题就变成
任意给定一个正整数n,一定可以将它乘以适当的整数,使得乘积是完全由0和1组成的数。
法二:可以先证明,任意一个正整数n,一定可以乘以一个适当的数,使得乘积仅仅由0和1两个数字组成。
证明:
(1)如果n是一个没有5的因子的奇数,那么n与10互质
设其欧拉函数值为f
那么由欧拉定理10^f = 1 (mod n)
那么构造一个整数x = (10^f)^n+(10^f)^(n-1)+...+10^f
那么x = 1 + 1 + 1 + ... + 1 = 0 (mod n)
所以x能被n整除,并且x的所有数字仅仅由0和1构成
(2)如果n是含有5的k次幂的奇数,那么设m = n/5^k是一个不含有5的因子的奇数,由(1)可以知道存在一个y使得y是m的倍数,并且y仅仅由0和1构成。
那么显然只要将y扩大10^k被,则10^k*y能被n整除,并且也仅仅由0和1构成。
(3)如果n是一个偶数,设含有2的k次幂,那么m=n/2^k是一个奇数,由上面可知,存在一个y能被m整除,而10^k*y能被n整除,并且只含有数字0和1。
综合上面的讨论知道,对于任意一个n,可以乘以一个适当的整数,使得乘积仅仅有数字0和数字1组成。
而将这个整数乘以7,则得到的数仅仅有0和7组成。
评论(3) | 4 0
2012-08-08 18:41tangram007 | 十二级
设n*x满足要求
显然n最后的0不影响分析
设n是偶数=2^r*Q,Q是奇数,(Q,10)=1,此时x必须是5^r倍数,只需要证明Q满足n的要求
设n是5倍数=5^r*Q,(Q,10)=1,此时x必须是2^r倍数,只需要证明Q满足n的要求。
因此只需要证明n与10互素时满足要求, 以下证明过程中,设(n,10)=1,n个位是1,3,7,9之一:
设最小的a1使n*a1=S1的最后一位是7,S1去掉个位,再去掉个位,直至个位不是0也不是7. 所得的数是T1,如果T1=0,分析结束,否则下一步;
设最小的a2使n*a2的个位+T1=S2,S2最后一位是0或者7,S2去掉个位,再去掉个位,直至个位不是0也不是7. 所得的数是T2,如果T2=0,分析结束,否则重复本步步骤;
分析:n的个位是1,3,7,9之一,a1,a2...取值只有1~9, S*必小于10n。T*在S*去掉至少一位,所以T*不可能超过n、S*的位数,T*取值只有限个,且不会重复,因此最终T*出现0或者满足要求的结果。
任意给定一个正整数n,一定可以将它乘以适当的整数,使得乘积是完全由0和1组成的数。
法二:可以先证明,任意一个正整数n,一定可以乘以一个适当的数,使得乘积仅仅由0和1两个数字组成。
证明:
(1)如果n是一个没有5的因子的奇数,那么n与10互质
设其欧拉函数值为f
那么由欧拉定理10^f = 1 (mod n)
那么构造一个整数x = (10^f)^n+(10^f)^(n-1)+...+10^f
那么x = 1 + 1 + 1 + ... + 1 = 0 (mod n)
所以x能被n整除,并且x的所有数字仅仅由0和1构成
(2)如果n是含有5的k次幂的奇数,那么设m = n/5^k是一个不含有5的因子的奇数,由(1)可以知道存在一个y使得y是m的倍数,并且y仅仅由0和1构成。
那么显然只要将y扩大10^k被,则10^k*y能被n整除,并且也仅仅由0和1构成。
(3)如果n是一个偶数,设含有2的k次幂,那么m=n/2^k是一个奇数,由上面可知,存在一个y能被m整除,而10^k*y能被n整除,并且只含有数字0和1。
综合上面的讨论知道,对于任意一个n,可以乘以一个适当的整数,使得乘积仅仅有数字0和数字1组成。
而将这个整数乘以7,则得到的数仅仅有0和7组成。
评论(3) | 4 0
2012-08-08 18:41tangram007 | 十二级
设n*x满足要求
显然n最后的0不影响分析
设n是偶数=2^r*Q,Q是奇数,(Q,10)=1,此时x必须是5^r倍数,只需要证明Q满足n的要求
设n是5倍数=5^r*Q,(Q,10)=1,此时x必须是2^r倍数,只需要证明Q满足n的要求。
因此只需要证明n与10互素时满足要求, 以下证明过程中,设(n,10)=1,n个位是1,3,7,9之一:
设最小的a1使n*a1=S1的最后一位是7,S1去掉个位,再去掉个位,直至个位不是0也不是7. 所得的数是T1,如果T1=0,分析结束,否则下一步;
设最小的a2使n*a2的个位+T1=S2,S2最后一位是0或者7,S2去掉个位,再去掉个位,直至个位不是0也不是7. 所得的数是T2,如果T2=0,分析结束,否则重复本步步骤;
分析:n的个位是1,3,7,9之一,a1,a2...取值只有1~9, S*必小于10n。T*在S*去掉至少一位,所以T*不可能超过n、S*的位数,T*取值只有限个,且不会重复,因此最终T*出现0或者满足要求的结果。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
广告 您可能关注的内容 |