¿¼Æ§P§Oªk
¤Þ¤l
¦b¡m¯À¼Æ§P§Oªk¡n¤@¤å¤¤¡A¥»ºô¬°¤j®a¤¶²Ð¤F¤@Ó¦¤w¬°¤j®aª¾¾åªº¯À©Ê (Primality) §P§O¤èªk¡A§Y¸Õ°£ªk (Trial Division)¡C¦ý·í§Ú̧@¸Õ°£®É¡AY¯à¤Î¦Â_©w n ¬°¬Y¼Æªº¿¼Æ (Multiple) ¡A·|¤j¤j´î¤Ö§Ú̪ºpºâ®É¶¡¡A¯S§O¬O¦b¤ßºâ®É¡C¬G¥»³¹·|¬°¤j®a¤¶²Ð¤@¨Ç§t±`¥Îªº¦]¤lªº¼Æªº§P§O¤§ªk¡A¥Øªº¥u¬OÅý§ÚÌ¡u¬Û¼Æ¡v®É¤]·|§Ö¤@ÂI¡C
¡@
¤G¤¦¸¤è¼Æ
¸Õ¤@¾ã¼Æ N ¥H¤Q¶i¨îªí¥Ü¬° an10n + an-110n-1 + ...... + a0¡C
¡@
¦]¬° 10 = 2*5¡A©Ò¥H 2k ©Î 5k ¥²¥i¾ã°£ 10k¡C©Ò¥H§PÂ_ N ¬O§_ 2k ©Î 5k ¥un¬Ý¬Ý N ªº³Ì¥½ k ¦ì¼Æ¡A¬O§_ 2k ©Î 5k ªº¿¼Æ«K¥i¡C¯S§O¦a¡AY¤@¼ÆªºÓ¦ì¬° 0, 2, 4, 6, 8 (§Y°¸¼Æ)¡A¨º¼Æ«K¬O 2 ªº¿¼Æ¡FY¤@¼ÆªºÓ¦ì¬° 0 ©Î 5¡A³o¼Æ«K¬O 5 ªº¿¼Æ¡C
¡@
¦p ¡G18 ¬O 2 ªº¿¼Æ¡A¦]¬°Ó¦ì¬O 8¡C 35 ¬O 5 ªº¿¼Æ¡A¦]¬°Ó¦ì¬O 5 ¡C2124 ¬O 8 ªº¿¼Æ¡A¦]¬°³Ì¥½ 3 ¦ì¼Æ 124 = 8*16¡C
¡@
¨ä¹ê¤£³æ¬O¯Â 2 ©Î 5 ªº¦¸¤è¼Æ¡A¦p 10¡B20 µ¥¥u¥]§t 2 ©Î 5 ¯À¦]¤lªº¼Æ¤]¥i¥Î¤Wz§P§Oªk¡C¤£¹L§Ų́úªº k «h¬O 2 ©Î 5 ªº«ü¼Æ¤¤³Ì¤jªº¤@Ó¦Ó¤w¡C
¡@
¤T©M¤E«ç»ò¿ì
¦]¬° 10 = 1 (mod 3) ©Î (mod 9) ¡A©Ò¥H 10k = 1 (mod 3) ©Î (mod 9) ¡A¨º»ò N = an10n + an-110n-1 + ...... + a0 = an + an-1 + ...... + a0 (mod 3) ©Î (mod 9) ¡C§YY N ¬° 3 (©Î 9) ªº¿¼Æ¡A¥un¨ä¼Æ¦rÁ`©M (Sum of Digits) ¤S¬O 3 (©Î 9) ªº¿¼Æ«K¦æ¡C
¡@
¦p¡G 123456789 ¬O 3 ªº¿¼Æ¡A¦]¬°¼Æ¦rÁ`©M 1+2+3+4+5+6+7+8+9 = 45 ¬O 3 ªº¿¼Æ¡C¸Ó¼Æ¥ç¬O 9 ªº¿¼Æ¡A¦]¬°¼Æ¦rÁ`©M¦P¼Ë¬O 9 ªº¿¼Æ¡C¦ý 203450122 «h¤£¬O 3 ©Î 9 ªº¿¼Æ¤F¡A¦]¬°¼Æ¦rÁ`©M 2+0+3+4+5+0+1+2+2 = 19¡A19¤£¬O 3 ©Î 9 ªº¿¼Æ¡C
¡@
¤Q¤@¦³¿ìªk
¦]¬° 10 = -1 (mod 11) ©Ò¥H 10k = -1 (mod 11) ·í k ¬°©_¼Æ®É¡AY k ¬°°¸¼Æ«h¦³ 10k = 1 (mod 11) ¡C©Ò¥H N = an10n + an-110n-1 + ...... + a0 = an(-1)n + an-1(-1)n-1 + ...... + a0¡A§Y§â°¸¼Æ¦ì©M©_¼Æ¦ìªº¼Æ¤À§O¥[°_¨Ó¡A¦A¹î¬Ý¥¦Ìªº®t¬O§_ 11 ªº¿¼Æ¡C
¡@
·íµM§ÚÌ¥ç·|µo²{ 100 = 1 (mod 11) ©Ò¥H§ÚÌ¥ç¥i¥ÎÃþ¦¹ 3 ©Î 9 ªº§P§Oªk¡A§â¼Æ¨â¨â¤@²Õ¡A¥[°_¨Ó¡A¬Ý¬Ý¬O¤£¬O 11 ªº¿¼Æ¡C
¡@
¦p¡G 39237 ¬O 11 ªº¿¼Æ¡A¦]¬° (3+2+7) - (9+3) = 12 - 12 = 0 ³o¥¿¬O 11 ªº¿¼Æ¡A©Îpºâ 03+92+37 = 132 = 11*12¡A§Y±o¦P¼Ëµ²ªG¡F¦Ó 40234 «h¤£¬O 11 ªº¿¼Æ¡A¦]¬° (4+2+4) - (0+3) = 10 - 3 = 7¡C
¡@
¯«¸t»P¤£²»¦P¦æ
¯«¥H¤C¤é§¹¦¨¾ãӤѦa³Ð³yªº¹Lµ{¡A¨ä¤¤¤@¤é¬O¥ð®§ªº¡C¬G°ò·þ®{»{¬°¤C³o¼Æ¦r¬O¯«¸t©Î§¹¬üªº¡C¦ý¬Û¤Ï¦è¤è¶Ç²Î«o»{¬° 13 ¬O¥Nªí¤£²»¡A¸Ô¥i¨£¡m½×ºÉ¤£²»13¡n¡C¦ý½Ö¤£ª¾³o¨â¼Æªº¿¼Æ§P§Oªk³º¬O¬Û¦Pªº¡C
¡@
¦]¬° 1001 = 7 * 11 * 13¡A¦ý¤T¼Æ¦ì¦b 11 ¦Ó¨¥¤£¬O³Ì¤Öªº¡A¦Ó¹ï 7 ©Î 13 ¦Ó¨¥«o¬O¡C¬O¬G 1000 = -1 (mod 7) ©Î (mod 13) ¡C©Ò¥H 10k = -1 (mod 7) ©Î (mod 13)¡A·í k ¬° 6 ªº¿¼Æ¥[ 3 ®É¡F¦ÓY k ¬° 6 ªº¿¼Æ«h¦³ 10k = 1 (mod 7) ©Î (mod 13)¡C©Ò¥H§Ú̳] n ¬° 3 ªº¿¼Æ¡AY¤£¬O«h¥i¨Ï an µ¥¼Æ¬°¹s§@¸É¦ì¡C N = an10n + an-110n-1 + ...... + a0 = (an102 + an-110 + an-2) * 1000 n/3 + ...... + (a2102 + a110 + a0) = (an102 + an-110 + an-2) * (-1) n/3 + ...... + (a2102 + a110 + a0) (mod 7) ©Î (mod 13)¡A§Y N (ÂX¤j¦Ü n ¬°§â 3 ªº¿¼Æ¥H«á)¡A¨C 3 ӼƤ@²Õ¡A°¸¼Æ²Õ©M©_¼Æ²Õªº¼Æ¤À§O¥[°_¨Ó¡A¦A¹î¬Ý¥¦Ìªº®t¬O§_ 7 (©Î 13) ªº¿¼Æ¡C
¡@
¦p¡G 149258361 ¬O 7 ªº¿¼Æ¦ý¤£¬O 13 ªº¿¼Æ¡A¦]¬° (149 + 361) - (258) = 252¡A¦Ó³o 252 ¬O 7 ªº¿¼Æ¦ý¤£¬O 13 ªº¿¼Æ¡C¤S¦p 20304050 «h¤£¬O 7 ªº¿¼Æ¦ý³o·|¬O 13 ªº¿¼Æ¡A¦]¬° (020 + 050) - (304) = -234¡A³o -234 ¤£¬O 7 ªº¿¼Æ«o¬O 13 ªº¿¼Æ¡C
¡@
¥h±¼§À¤Úªº¤èªk
¬Ý¬Ý 19 ªº¿¼Æªº§P§O¤èªk§a¡C
§P§O 46892 ¬O§_ 19 ªº¿¼Æ¡C
¥ý§â 46892 ªº¡u§À¤Ú¡v2 ¬å±¼¡A¦A§â¡u§À¤Ú¡vªº¨â¿¥[¦b¾l¼Æ¤W¡A§Y 4689 + 2 * 2 = 4693¡C
¦A§â 4693 ªº¡u§À¤Ú¡v3 ¬å±¼¡A¦A§â¡u§À¤Ú¡vªº¨â¿¥[¦b¾l¼Æ¤W¡A§Y 469 + 2 * 3 = 475¡C
¦A§â 475 ªº¡u§À¤Ú¡v5 ¬å±¼¡A¦A§â¡u§À¤Ú¡vªº¨â¿¥[¦b¾l¼Æ¤W¡A§Y 47 + 2 * 5 = 57¡C
¦A§â 57 ªº¡u§À¤Ú¡v7 ¬å±¼¡A¦A§â¡u§À¤Ú¡vªº¨â¿¥[¦b¾l¼Æ¤W¡A§Y 5 + 2 * 7 = 19¡C
¾l¤U 19¡A¬G 46892 ¥ç¬O 19 ªº¿¼Æ¡C (46892 = 19 * 2468)
¡@
ì²z¤]«Ü²³æ¡A³]¬Y¼Æ¬° M = 10A + B¡A¨ä¤¤ B ¬°Ó¦ì¼Æ¡C¥h±¼¡u§À¤Ú¡v¡A¦A§â¡u§À¤Ú¡vªº¨â¿¥[¦b¾l¼Æ¤W¡A§Y·s¼Æ¬° N = A + 2B¡C
§Ú̪¾¹D 2M - N = 2(10A + B) - (A + 2B) = 20A + 2B - A - 2B = 19A¡A¬° 19 ªº¿¼Æ¡C§Y¤@¬O M, N ¦P¬° 19 ªº¿¼Æ¡A©Î¬O M, N ¦P¤£¬O 19 ªº¿¼Æ¡C
§ÚÌ«ÂШBÆJ¦Ü³Ì«á¤@Ó¦ì¡A«Kª¾¼Æ M ©M N ¬O«eªÌ©Î¬O«áªÌ¤F¡C
¡@
¨ä¹ê³o¤èªk¥ç¾A¥Î©ó§P§O¤@²³Ó¦ì¬°¡u¤E¡vªº¾ã¼Æªº¿¼Æ¡A¦p 29¡B39¡B49¡B...
§ÚÌ°²³]¥ý±o¥h±¼¡u§À¤Ú¡v¡A¦A§â¡u§À¤Ú¡vªº a ¿¥[¦b¾l¼Æ¤W¡A³]¬Y¼Æ¬° M = 10A + B¡A¨ä¤¤ B ¬°Ó¦ì¼Æ¡A¦Ó·s¼Æ¬° A + aB¡C
¥t aM - N = 29n¡Aa(10A + B) - (A + aB) = 29n¡A10aA + aB - A - aB = 29n¡A(10a - 1)A = 29¡A§Y¨ú a = 3¡C
¬G§ÚÌ¥H±¼¡u§À¤Ú¡v¡A¦A§â¡u§À¤Ú¡vªº 3 ¿¥[¦b¾l¼Æ¤Wªº¤èªk«K¥i´ú¸Õ¬Y¼Æ¬O§_ 29 ªº¿¼Æ¤F¡C
¡@
¦P²z¡A§ÚÌ¥ç¥i¥H¦¹ªk§P§O¤@²³Ó¦ì¬°¡u¤@¡vªº¾ã¼Æªº¿¼Æ¡A¦p 11¡B21¡B31¡B...
¤èªk¥u¬O§â¡u§À¤Ú¡v¥[¦b¾l¼Æ¤W§ï¬°±q¾l¼Æ¤¤´î±¼«K¦¨¡A¦Ü©ó´î±¼¦h¤Ö¿ªº¡u§À¤Ú¡v¡A«hn¬Ý¹ï¶H¬O 21 ªº¿¼ÆÁÙ¬O 51 ªº¿¼Æ¤F¡C
¡@
Á`µ²
¹ï©ó¬Y¤@¦]¤l K ªº¿¼Æªº§P§Oªk¡G
¡@
²Ä¤@¡AK ¬°¤@¥u§t¦³
2 ©Î 5 ªº¦]¤lªº¼Æ¡A«h¹î¬Ý³Ì¥½ k ¼Æ¦ì¬O§_ K ªº¿¼Æ¡A¨ä¤¤ k ¬° 2 ©Î 5 ªº³Ì°ª«ü¼Æ¡C
¡@
²Ä¤G¡A§Y§ä´M¨Ï 10k
= 1 (mod K) ªº³Ì¤pÈ k¡A¦p 3 ªº k = 1 ¡A9 ªº k = 1¡CµM«á§â N ¥H k ¦ì¼Æ¬°¤@²Õ¤À¶}¦A¥[°_¨Ó¡A¹î¬Ýµ²ªG¬O§_¬° K
ªº¿¼Æ¡C¬G¥B¤À¸Ñ 10k -1 ¹ï¦¹Ãþ§P§Oªk¦³§U¡A¦]¦p 999 = 33 * 37¡A§ÚÌ«Kª¾¹Dì¨Ó 37
ªº§P§Oªk¬O¥H¦¹ªk¦ý¬Ý¤T¦ì¼Æ¤@²Õ¡C¦ý§Ú̪¾¹D³o 10k -1 ùÚ¬° 9 ªº¿¼Æ¡A¬G§â¤§°£ 9 ¡A«K±o¤@¨t¦Cªº¯Â¤¸¼Æ (Repunit)¡C§Y¤À¸Ñ¯Â¤¸¼Æ¬O§Ú³o°ÝÃD¦³Ãö¡AÃö©ó¯Â¤¸¼Æªº°ÝÃD¡A¸Ô¥i°Ñ¬Ý¡m¥u¦³¤@ӼƦrªº
¼Æ - ¯Â¤¸¼Æ¡n©Î¤Uªí¡C
k |
(10k-1)/9 |
¯À¦]¤l¤À¸Ñ¦¡ |
k |
(10k-1)/9 |
¯À¦]¤l¤À¸Ñ¦¡ |
1 |
1 |
1 |
2 |
11 |
11 |
3 |
111 |
3*37 |
4 |
1111 |
11*101 |
5 |
11111 |
41*271 |
6 |
111111 |
3*7*11*13*37 |
7 |
1111111 |
239*4649 |
8 |
11111111 |
11*73*101*137 |
9 |
111111111 |
32*37*333667 |
10 |
1111111111 |
11*41*271*9091 |
11 |
11111111111 |
21649*513239 |
12 |
111111111111 |
3*7*11*13*37*101*9901 |
13 |
1111111111111 |
53*79*265371653 |
14 |
11111111111111 |
11*239*4649*909091 |
15 |
111111111111111 |
3*31*37*41*271*2906161 |
16 |
1111111111111111 |
11*17*73*101*137*5882353 |
17 |
11111111111111111 |
2071723*5363222357 |
18 |
111111111111111111 |
32*7*11*13*19*37*52579*333667 |
19 |
1111111111111111111 |
1111111111111111111 |
20 |
11111111111111111111 |
11*41*101*271*3541*9091*27961 |
µù¡G¬õ¦â¼ÆªÌ¡A¬°ªí¤¤ªì²{¤§¯À¼Æ¡C¥¤ß¦Ó¨¥¡A¨S¦³¤°»ò¤H·|¥H¤ßºâ§â¨C 19 Ó¼ÆÂk¤@²Õ¬Û¥[«á¡A¦A¬Ý¬Ý³o¬O¤£¬O 1111111111111111111 ªº¿¼Æ¡C½Ö·|·F³oºØ¨Æ¡H°Q±Ðpºâ¾÷¦n¤F¡C¬G¥H«á¼Æ¦ìªº¯Â¤¸¼Æ¥Î³~¤£¤j¡A¤£¦C¼g¤F¡C
²Ä¤T¡A§Y§ä´M¨Ï 10k
= -1 (mod K) ªº³Ì¤pÈ k¡A¦p 11 ªº k = 1 ¡A7 ªº k = 3¡CµM«á§â N ¥H k ¦ì¼Æ¬°¤@²Õ¤À¶}¦A§â©_¼Æ²Õ©M°¸¼Æ²Õ¤À§O¥[°_¨Ó¡A¦A§â¨â²Õ¬Û´î¡A¹î¬Ýµ²ªG¬O§_¬°
K ªº¿¼Æ¡C¦b¦¹Ãþ§P§Oªk¤¤¡A¤À¸Ñ 10k +1 ·|¦³§U©ó¤F¸Ñ¬Y¤@¼Æ¬O§_¥H k ¼Æ¦ì¬°¤@²Õ¡AY 1001 = 7*11*13¡A§Y
7¡B11¡B13¤]¥i¥Î¦¹ªk¥B¥H¤T¦ì¼Æ¬°¤@²Õ¡A¦ý¹ï 11 ¦Ó¨¥ k = 1 ¤ñ k = 3 §ó¤Ö¡A¬G¥H¤T¦ì¼Æ¬°¤@²Õ¶È¦p 7 ©M 13 ¨â¼Æ¡C¹ï©ó 10k
+1ªº¤À¸Ñ¡A¥i¬Ý¤Uªí¡C
k |
10k +1 |
¤À¸Ñ¦¡ |
k |
10k +1 |
¤À¸Ñ¦¡ |
1 |
11 |
11 |
2 |
101 |
101 |
3 |
1001 |
7*11*13 |
4 |
10001 |
73*137 |
5 |
100001 |
11*9091 |
6 |
1000001 |
101*9091 |
7 |
10000001 |
11*909091 |
8 |
100000001 |
17*5882353 |
9 |
1000000001 |
7*11*13*19*52579 |
10 |
10000000001 |
101*3541*27961 |
11 |
100000000001 |
112*23*4093*8779 |
12 |
1000000000001 |
73*137*99990001 |
13 |
10000000000001 |
11*859*1058313049 |
14 |
100000000000001 |
29*101*281*121499449 |
15 |
1000000000000001 |
7*11*13*211*241*2161*9091 |
16 |
10000000000000001 |
353*449*641*1409*69857 |
17 |
100000000000000001 |
11*103*4013*21993833369 |
18 |
1000000000000000001 |
101*9901*999999000001 |
19 |
10000000000000000001 |
11*909090909090909091 |
20 |
100000000000000000001 |
73*137*1676321*5964848081 |
µù¡G¬õ¦â¼ÆªÌ¡A¬°ªí¤¤ªì²{¤§¯À¼Æ¡C¦Ñ¹ê¦Ó¨¥¡A¨S¦³¤°»ò¤H·|¥H¤ßºâ§â¨C 19 Ó¼ÆÂk¤@²Õ¤À©_°¸²Õ¬Û¥[«á¡A¦A¨D¨ä®t¡A³Ì«áÁÙ±o¬Ý¬Ý³o¬O¤£¬O 909090909090909091 ªº¿¼Æ¡C½Ö·|·F³oºØ¨Æ¡H¤S¬O³o¤@¥y¡A°Q±Ðpºâ¾÷¦n¤F¡C¬G¥H«á¼Æ¦ìªº 10k +1 ¥Î³~¤£¤j¡A¤£¦C¼g¤F¡C
·íµM¦b¤Wz²Ä¤Tªº±¡ªp¡A§ÚÌ¥ç¥i¦Ò¼{ 102k = 1 (mod K)¡A¦Ó¥Î²Ä¤GÓ¤èªkpºâ¡C
¡@
²Ä¥|
¡A§ÚÌ¥ç¥i¹B¥Î¥h±¼¡u§À¤Ú¡vªº¤èªk¨Ó§P§O¬Y¼Æ¬O§_¬°¨º¨ÇӦ쬰 1 ©Î 9 ªº¼Æ¡A¦p
19¡B29¡B31µ¥¼Æªº¿¼Æ¡C¦ý¦¹ªkªº¯ÊÂI¬O§Ú̱o¤@¨B¤@¨B¨Ó·F¡A¹ï©ó¼Æ¦ì¸û¤jªº¼Æ¡A§P§O©¹©¹§ó¥[¶O®É¡C
¡@
³Ì«á¡AY 6 ©Î
21 ³o¨Ç¦X¼Æ¡A§ÚÌ¥i¥H¬Ý¬Ý¬Y¼Æ¬O§_¤w²Å¦X¨ä©Ò¦³¯À¦]¤lªº¿¼Æn¨D¡AY¬O¡A«K¬O¸Ó¦X¼Æªº¿¼Æ¤F¡C¦p 24 ¬O 2 ªº¿¼Æ¡A¤]¬O 3 ªº¿¼Æ¡A©Ò¥H 24
¬O 6 ªº¿¼Æ¡C¦ýYÀˬd¤@¼Æ¬O¤£¬O 12 ªº¿¼Æ¡A§ÚÌ«KnÀˬd¸Ó¼Æ¬O¤£¬O¦P®É¬O 4 ©M 3 ªº¿¼Æ¡A¦Ó¤£¬O³æ¬Ý 2 ©M 3¡C
¡@
°Ñ¦Ò¤åÄm¤Îºô§}¡G
±ä©÷ªF ; ±i¦V´¸ , "¯S®í½è¦]¼Æ§P§Oªk" ¦Û ¼Æ¾Ç§Ö»¼²Ä¤C´Á, ¥x¥_ : ¤T¥Á®Ñ§½
¡@