Question

求证：任意给定一个正整数n，一定可以将它乘以适当的整数，使得乘积是完全由0和7组成的数。

Answer 1

　　法一：只有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或者满足要求的结果。

Answer 2

因为任意一个正整数n乘以M个适当的整数后,其乘积一定可以完全由0和7的数组成.
这M个适当的整数相乘为一个数,则可以为
任意一个正整数n，一定可以将它乘以适当的整数，使得乘积是完全由0和7组成的数。