本帖最后由 作者 于 2008-12-30 10:21:41 编辑 <br /><br /> <p><font face="仿宋_GB2312" size="5"> 楼主不想自己的帖子偏离既定的“简单、巧妙、兴趣”的方向。</font></p>
<p>用Mathematica做了一下，确实第10题在3000之内只解出了1001和2002两个解</p><p>修改了一下，也试出了2003改成2007的时候，这个数是666</p><p>那借花献佛一下吧，把watt的题目改成应景一些的，2009快到了，题目就是</p><p><font size="5"><font face="仿宋_GB2312"><font color="#b34d4d">求最小的自然数 n <br/>使得 n 位数 1111....111 被 2009 整除 <br/></font>答案: <br/>n=？</font></font></p>
<p>第一至第九题除了用程序去解都没什么办法去解的，当然在求解前确定某些情况符合条件会减少程序的计算时间。</p><p>第十题实际上是求10对模2003的次数，初等数论上已经有很成熟的方法了。</p><p>欧拉函数φ(n)：欧拉函数是一个定义在正整数上的函数，φ(n)的值等于以下这些整数0、1、2、…、n-1与n互素的数的个数。</p><p>由定义知，φ(1)=1，φ(2)=1，φ(3)=2，φ(4)=2，……，当p是素数时，φ(p)=p-1。</p><p>欧拉函数的计算方法：设n的标准分解式子是p1^k1·p2^k2·…·pm^km，其中p1、p2、…、pm是互不相等的素数，k1、k2、…、km都是正整数，则φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pm)。</p><p>例如φ(10)=10×(1-1/2)×(1-1/5)=4。</p><p>欧拉定理：设a、m为整数，m>1，(a,m)=1，则a^φ(m)≡1 (mod m)。</p><p>整数的次数：a、m为整数，m>1，(a,m)=1，k是使a^k≡1 (mod m)成立的最小正整数，则k叫做a对模m的次数。</p><p>次数定理：设a对模m的次数为k，n是满足a^n≡1 (mod m)的正整数，则k|n。</p><p>例如<br/>2003是素数，所以问题等价于求10^n≡1 (mod 2003)能被2003整除的最小正整数n，φ(2003)=2002=2×7×11×13，由欧拉定理知10^2002≡1 (mod 2003)，因此所求的正整数就是2002的正因数，只需要尝试有限个就得到所求的n是1001。</p><p>虽然这个方法可行，但因数多时仍需要做很多的验证，需要有更有效的改进方法。</p><p>假设a、n是大于1的正整数，p是素数，则a对模p的次数没有什么好办法去求，只能用上面的方法。<br/>其它情形有下面两个定理：<br/>假设a、n是大于1的正整数，n的标准分解式是p1^k1·p2^k2·…·pt^kt，其中p1、p2、…、pt是互不相等的素数，k1、k2、…、kt都是正整数，a对模pi^ki的次数为mi，则a对模n的次数为m1、m2、…、mt的最小公倍数。<br/>如果a、n是大于1的正整数，p是素数，k是正整数，a对模p^k的次数是m，则a对模p^(k+1)的次数是m或pm。</p><p>例如<br/>2007=3^2×223，问题等价于求10^n≡1 (mod 18063)能被2003整除的最小正整数n。18063=3^4×223。10对模3的次数1；因此10对模9的次数是1或3，经检验得10对模9的次数是1；因此10对模27的次数是1或3，经检验得10对模27的次数是3；因此10对模81的次数是3或9，经检验得10对模81的次数是9。10对模223的次数是222。因此所求的n就是9和222的最小公倍数，即666。</p><p>相信利用上面的方法，你已经知道对qjchen提出的2009的情形怎样计算了。</p>
watt5151发表于2008-12-27 15:53:00static/image/common/back.gif《几何算法》版的特色是作图，非作图题浪费了论坛的资源，下不为例了。楼主还有很多作图题与各位阁下切磋，待第一版的精彩文章‘退居二版’再说。
<p><font face="仿宋_GB2312" size="5">①象人教论坛那样，<font color="#c43c57">不欢迎hejoseph来我的帖子上面摆架子</font>。<br/>②42楼的问题只是小菜一碟。<br/>《几何算法》版的特色是作图，非作图题浪费了论坛的资源，请不要在本帖继续。<br/></font></p>
<p>watt5151不要再发火了，qjchen兄的2009问题用excel算了次。<br/>n=210<br/>111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111=2009×55306675515734749184226536142912449532658591892041369393285769592389801449034898512250428626735246944306177755655107571483878104087163320612797964714341020961230020463469940821857198163818372877606327083679<br/><br/></p>
谁摆架子大家都明白了吧？若还对watt5151不满我根本不会近来回帖子。
都不要生气了，我们论坛风气挺好的，以前的事就放一边吧！
watt5151发表于2008-12-27 10:05:00static/image/common/back.gif⑩ 求最小的自然数 n 使得 n 位数 1111....111 被 2003 整除 答案: n=1001 数据: 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 1
<br/></div><p><font face="仿宋_GB2312" size="5">请hejoseph先生不要点击watt5151的帖子，以免引出矛盾。<br/>请留意37楼的编辑部分。</font></p>
本帖最后由 作者 于 2008-12-29 17:38:56 编辑 <br /><br /> <p>:)，还是继续劝watt小姐和Hejoseph兄别动动气：）<br/><br/>非常感谢 Hejoseph兄 的数论解法，让人大开眼界，我不是很懂数论，不过居然能解决这种大数问题，看来我得下功夫学习一下了。<br/><br/>也非常感谢chenjun_nj兄的精彩excel解答，不愧是excel方面的高高手，居然用这么简洁的方法就解决了大数问题，以后多向您学习。最喜欢这种用函数就解决问题而不是用宏的方法了。<br/><br/>那我下面说说我的解题过程，我是用Mathematica求解的过程如下：<br/><br/>-----------------------<br/>a = 1<br/>For == 0, Print]]<br/>-----------------------<br/>按shift+enter，得到一堆210的倍数。<br/></p><p>To Watt</p><p>------------------------</p><p>算爆机的可能性很小啊，用Mathematica，不到1秒钟，得到的结果如下</p><p>2011（670）、2017（2016）、2027（1013）、2029（2028）、2039（2038）、2053（342）、2063（2062）、2069（2068）、2081（1040）、2083（1041）、2087（298）、2089（1044）、2099（2098）</p><p>这些数字是很有趣的，可以看到许多时候和这个数-1有关系，我来看看是什么规律。</p><p>哦，原来Hejoseph兄的理论已经解决了这个规律了，请允许我再仔细看下数论。</p><p><br/><br/><br/><br/></p>
本帖最后由 作者 于 2008-12-29 21:16:29 编辑 <br /><br /> qjchen问到我上面问题的原理，解释如下：<br/>问题：111…1（n个）组成一个整数能被p整除（p是比3大素数），求n的最小值。<br/>因为111…1（n个）能被p整除，必然999…9（n个）能被p整除；反之9999…9（n个）能被p整除，那么p必定整除9或111…1（n个）。但3与p互素，所以p必定整除111…1（n个）。所以只要求999…9（n个）能被p整除时n的最小值即可。<br/>又9999…9（n个）=10^n-1，问题就变成求n的最小值使p整除10^n-1，亦即10对模p的次数（请看43楼所写的整除的次数的定义）。<br/>φ(p)=p-1（请看43楼所写的欧拉函数的定义），所以n必定整除p-1（请看43楼所写的次数定理）。