一个数由许多个1和0组成,它能被223整除.最小的是多少?请在今天给与答案.

Question

一个数由许多个1和0组成,它能被223整除.最小的是多少?
请在今天给与答案.

Answer 1

223是素数,由费尔玛定理可知10^222=1(mod223),10^222-1=0(mod223),即
999...9=0(mod223),由于9与223互素,可知111...1=0(mod223),111...1(222个1组成)能被223整除.
下面证明111...1(222个1)是能被223整除的最小数,首先证明,能被223整除的最小数一定是全由1组成,否则假设一个由n个1,m个零构成的数111...1100...00能被223整除,由111...1100...00=111...11*10^m,且10^m与223互素,故111...11也能被223整除,这与111...1100...00是最小数矛盾.
另一方面,如果111...1(n个1)能被223整除,则999...9(n个9)也能被223整除,则10^n=1(mod223),由于10是223的原根,则必有n≥222,这就证明了111...1(222个1)是能被223整除的最小数.