 Applied Mathematics, 2011, 2, 1359-1363 doi:10.4236/am.2011.211190 Published Online November 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM The Numbers of Thousand Place of Mersenne Primes* Sibao Zhang1, Lihang Zhou2 1Department of Mat hem at i cs, Kashgar Teachers College, Kashgar, China 2Department of Com p ut er Sci ence, Guangdong Technical College of Water Resources and Electric Engineering, Guangzhou, China E-mail: sibao98@sina.com Received April 23, 2011; revised August 27, 2011; accepted September 4, 20 1 1 Abstract Mersenne primes are a special kind of primes, which are an important content in number theory. The study of Mersenne primes becomes one of hot topics of the nowadays science. Searching for Mersenne primes is very challenging in scientific researches. In this paper, the numbers of thousand place of Mersenne primes are studied, and the conclusion is presented by using the Chinese remainder theorem. Keywords: Mersenne Primes, The Chinese Remainder Theorem, The Number of Thousand Place 1. Introduction In 300 BC, ancient Greek mathematician Euclid proved that there are infinitude primes by contradiction, and raised that a small amount of prime numbers could be expressed in numbers of the form , where is a 2 p1p prime. Afterward, many famous mathematicians have re- searched the prime numbers of this special formulation. In 1644, French mathematician M. Mersenne stated in the preface to his Cogitata Physica-Math ematica tha t th e numbers were primes for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and were composite for all other positive integers . Mersenne’s (incorrect) con- jecture fared only slightly better than Regius’, but still got his name attached to these numbers. The formulation of is named as “Mersenne number” and ex- pressed as 2 p 1 1 257p 2 p (so ). If a 21 p p M is a prime number, then it is named as “Mersenne prime”. The Lucas-Lehmer test is a primarily test for Mer- senne numbers: For an odd prime, the Mersenne number is prime if and only if divides p 2 p1 1 1 2 p S(p – 1), where , and S(1) = 4. The test was originally developed by E. Lucas in 1856, and subsequently improved by Lucas in 1878 and D. Lehmer 2 S(1)S( )2pp in the 1930s. The sequence S(p) is computed modulo to save time. The Lucas-Lehmer test is ideal for binary computers because the division of 2 2 p 1 p (in binary) ca n be d o n e by using rot a tion and ad di tion only. In 1992, Chinese mathematician and linguist Ha- izhong Zhou [1] presented the well-known Zhou conjec- ture on the distribution of Mersenne primes in the natural number system: If (n = 0, 1, 2, 3,), 1 2 22 n p 1 2 n 1 then there are 2 n Mersenne primes. At the same time he gave the deduction: If , then there are 1 2 2n p 2 2 nn 2 Mersenne primes. As the increase of exponent , searching for Mer- senne primes is very challenging. Studying Mersenne primes, not only the advanced theory an d practiced skills are needed, but also the arduous calculations are needed to validate whether a Mersenne number is a prime or not [2]. The research of Mersenne primes is very abundant in the contemporary theoretical and practical value. The research of Mersenne primes greatly promotes the de- velopment of mathematics, especially number theory. In addition, many well-known mathematics problems, such as Goldbach conjecture, twin primes, Riemann conjec- ture, etc. are inextricably linked to Mersenne primes. Therefore, the research of Mersenne primes can also speed up the solution to those problems [3]. And the re- search of Mersenne primes can promote distributed computing and programming arts. It not only requires well-designed distributed architecture, but also improves the numerical calculation methods and algorithm design arts. [4] There are only 47 known Mersenne primes [5]. p In [6,7], the last number and the ten place number have been studied, and conclusions have been obtained. In this paper, the numbers of thousand place of Mersenne primes are studied, and the conclusion is presented by using the Chinese remainder theorem. *Project Supported by the Science Foundation of Kashgar Teacher College (No. 112390). Theorem If the exponent p of satisfies  S. B. ZHANG ET AL. 1360 8 11,12,14,18,22,60, 61,63,66,69, 75,103,104(mod12 5); 8 314,27,46,54,61,63, 73,76,80,83,87,115(mod125); 85 3,6,12,41,63,74, 76,84,122,123(mod125); 87 0,10,13,17,20,24, 52,76,89,108,116 pk k pk k pk k pk k , , , , ,123(mod 125) Then, the number of the thousand place of Mersenne primes is 0; If the exponent of p satisfies 8 12,6,34,58,71,90,98, 105,107,117,120,124(mod125); 8 316,17,19,22,25,31, 59,60,82,93,95,99,103(mod125); 8 58,27,42,44,54,57, 61,64,68,96(mod125); 8 719,30,32,36,40,78, 7 9 ,81,84,87,93 pk k pk k pk k pk k , , , , ,121,122(mod 125) Then, the number of the thousand place of Mersenne primes is 1; If the exponent of p satisfies 8 110,11,13,16,19,25, 53,54,76,87,89,93,97(mod125); 8 31,5,8,12,40,64,77, 96,104,111,113,123(mod125); 8 513,24,26,34, 72,73,78,81,87,116(mod125); 8 71,14,33,41,48,50, 60,63,67,70,74,1 pk k pk k pk k pk k , , , , 02(mod125) Then, the number of the thousand place of Mersenne primes is 2; If the exponent of p satisfies 8 1,8,21,40,48,55,59, 67,70,74,77,81,109(mod125); 8 3,7,18,20,24,28,66, 67,69,72,75,81,109,110(mod125); 85, 4,7,11,14,18,46, 83,102,117,119(mod125); 87, 3,4,6,9,12,18, 46,47,69,80,82,86,9 pkk pk k pk k pk k 0(mod125) Then, the number of the thousand place of Mersenne primes is 3; If the exponent of p satisfies 8 ,26,37,39,43,47, 85,86,88,91,94,100(mod125); 8 32,21,29,36,38,48, 51,55,58,62,90,114(mod125); 8 522,23,28,31,37, 66,88,99,101,109(mod125); 8 727,51,64,83,91,98, 100,110,113,117, pk pk k pk k pk k , , , 120,124(mod125) 1 3,4,k Then, the number of the thousand place of Mersenne primes is 4; If the exponent of p satisfies 8 ,7,20,24,27,31, 59,83,96,115,123(mod125); 83,0,6,34 35,57,68,70, 74,78,116,117,119,122(mod125); 8 5,33,52,67,69,79, 82,86,89,93,121(mod125); 8 7,5,7,11,15,53,54, 56,59,62,68,96,9 pk pk k pk k pk k ， 7,119(mod125) 1 5,7,1k Then, the number of the thousand place of Mersenne primes is 5; If the exponent of p satisfies 8 ,38,41,44,50,78, 79,101,112,114,118,122(mod125); 8 315,39,52,71,79,86,88, 98,101,105,108,112(mod125); 8 516,38,49,51,59,97, 98,103,106,112(mod125); 8 78,16,23,25,35,38,42, 45, pk k pk k pk k pk k , , , 49,77,101,114(mod125) 1,35,36 Then, the number of the thousand place of Mersenne primes is 6; If the exponent of p satisfies 81, 9,33,46,65,73,80, 82,92,95,99,102,106(mod125); 8 3,3,41,42,44,47,50, 56,84,85,107,118,120,124(mod125); 8 5,2,17,19,29,32,36, 39,43,71,108(mod125); 8 7,21,22,44,55,57,61, 65,103,104,10 pkk pk k pk k pk k 6,109,112,118(mod125) Then, the number of the thousand place of Mersenne primes is 7; If the exponent of p satisfies Copyright © 2011 SciRes. AM  S. B. ZHANG ET AL.1361 8 1,0,28,29,51,62,64,68, 72,110,111,113,119(mod125); 8 3,4,11,13,23,26,30,33, 37,65,89,102,121(mod125); 8 5,1,9,47,48,53,56, 62,91,113,124(mod125); 8 7,2,26,39,58,66, 73,75,85,88,92 ,95, 99 pkk pk k pk k pk k (mod125) Then, the number of the thousand place of Mersenne primes is 8; If the exponent of p satisfies 8 1,15,23,30,32,42,45, 49,52,56,84,108,121(mod125); 8 3,9,10,32,43,45,49, 53,91,92,94,97,100,106(mod125); 8 5,21,58,77,92,94,104, 107,111,114,118(mod125); 8 7,28,29,31,34,37,43, 71,72,94, pkk pk k pk k pk k 105,107,11 1,115(mod125) Then, the number of the thousand place of Mersenne primes is 9. 2. Preliminaries In order to prove the theorem, we need the following lemma. Lemma (The Chinese Remainder Theorem) Let 12 be pair-wise relatively prime posi- tive integers. Then the system of congruencies ,,, r mm m 11 22 (mod ) (mod ) (mod ) rr am am am has a unique solution modulo [6]. 12 ,,r mmm m 3. Proof of the Theorem Since the exponent p of Mp is a prime, then p = 4k + 1 or p = 4k + 3. When p = 2, 3, 5, . So, p = 8k + 1 or or or . 21100 p 8+pk8+3pk8+5pk7 We have five congruence equations as following, when Mp modulo 16,625 separately. 81 83 3 85 5 877 212562 11(mod16) 21 256211(mod16) 21 256211(mod16) 21 256211(mod16) kk pkk pkk pkk p M M M M (1) 81 212562 1(mod625) kk p M (2) 833 21 25621(mod625) kk p M (3) 85 5 21 25621(mod625) kk p M (4) 877 21 25621(mod625) kk p M 1 125 k k (5) Note that when 256 2561(mod625) 25)0(mod1k , where is a nonnegative integer. Therefore, we have congruence equations as following, when modulo 625 separately, where k 256k i kk (mod125) and 0,1,2, ,124 i k . 256 1 k ,256, 536, 341, 421, 276, 31, 436, 366, 571, 551, 431, 336, 391, 96, 201, 206, 236, 416, 246, 476, 606, 136, 441, 396, 126, 381, 36, 466, 546, 401, 156, 561, 491, 71, 51, 556, 461 , 516, 221, 326, 331, 361, 541, 371, 60 1, 106, 261, 566 , 521, 25 1, 506, 161 , 591, 46 , 526, 281, 6 1, 616, 196, 176, 56, 586, 16, 346, 451, 456, 486, 41, 496, 101, 231, 386, 66, 21, 3 76, 6, 286, 91, 171, 26, 406, 1 86, 116, 321, 301, 181, 86, 141, 471, 576, 581, 611, 166, 621, 226, 356, 511, 191, 146, 501, 131, 411, 216, 296, 151, 531, 311, 241, 4 46, 426, 306 , 211, 266, 596, 76, 81, 11 1, 291, 121, 351, 481, 11, 316, 271(. mod625) (6) Combined congruence Equations (6) and (2), (3), (4), (5) separately , we h ave 81 21 k p M1 , 511, 446, 56, 216, 551, 61, 246, 106, 516, 476, 236, 46, 156, 191, 401, 411, 471, 206, 491, 326, 586, 271, 256 , 166, 251, 136, 71, 306, 466, 176, 311, 496, 356, 141, 101, 486, 296, 406, 441, 26, 36, 96, 456, 116, 576, 211, 521, 506, 416, 501 , 3 86 , 32 1, 556, 91, 426, 561, 121, 606, 3 91, 351, 111 , 546, 31, 66, 276, 286, 34 6, 81, 366, 201, 461, 146, 131, 41, 126, 11, 571, 181, 341, 51, 186, 371, 23 1, 16, 601, 361, 171, 281, 316, 526, 53 6, 596, 331, 616, 451, 86, 396, 381, 291, 376, 261, 196, 431, 591, 301, 436, 621, 481, 266, 226, 611, 421, 531, 566, 151, 161, 221, 581, 241, 76, 336, 21, 6, 541(. mod625) (7) 83 21 k p M7 , 172, 537, 227, 242, 332, 247, 362, 427, 192, 32, 322, 187, 2, 142, 357, 39 7, 12, 202, 92 , 57, 472, 462, 402, 4 2, 382, 547, 28 7, 602, 617 , 82, 622, 11 2, 177, 567, 407, 72, 562, 377, 517, 107, 147, 387, 577, 467, 432, 222, 212, 152 , 417, 132, 297, 37, 352, 367, 457, 372, 487, 552, 317, 157, 447, 312, 127, 267, 482, 522, 137, 327, 217, 182, 597, 587, 527, 167 , 5 07 , 47 , 412, 102, 117, 207, 122, 237, 302, 67, 532, 197, 62, 502, 17, 232, 272, 512, 77, 592, 557, 347, 337 , 27 7, 542, 257 , 422, 162, 477, 492, 582, 497, 612, 52, 442, 282, 572, 437, 252, 392, 607, 22, 262, 452, 342, 307, 97, 87, 27, 292(. mod625) (8) 85 213 k p M1 , 66, 276, 286, 346, 81, 366, 201, 461, 146, 131, 41, 126, 11, 571, 181, 341, 51,186, 371, Copyright © 2011 SciRes. AM  S. B. ZHANG ET AL. 1362 231, 16, 601, 361, 171, 281, 31 6, 526, 536 , 596, 331, 616, 451, 86, 396, 381, 291, 376 , 26 1, 196, 431 , 591, 301, 436, 621, 481, 266, 226, 611, 421, 531, 566, 151, 161, 221, 581, 241, 76, 336, 21, 6, 541, 1,511, 446, 56, 216, 551, 61, 246, 106, 51 6, 476, 236, 46 , 156, 191, 401, 411, 47 1, 206, 491, 326, 586, 271, 256, 166 , 2 51 , 13 6, 71, 306, 466, 176, 311, 496 , 356, 14 1, 101, 486 , 296, 406 , 441, 26, 3 6, 96, 456, 116, 576, 211, 521, 50 6, 416, 501 , 38 6, 321, 556, 91, 426, 561, 121, 606, 391, 351, 111, 546. (mod625) (9) 87 21 127 k p M (mod625) ,267, 482, 522, 137, 327, 217, 182, 597, 587, 527 , 167, 507, 47, 412, 102, 117, 207, 122, 237, 302, 67, 532, 197, 62, 502, 17, 232, 272, 512, 77, 592, 557, 347, 337, 277, 542, 257, 422, 162, 477, 492, 582, 497, 612, 5 2, 442, 282, 57 2, 437, 252 , 392, 607, 2 2, 262, 452, 342, 307, 97, 87, 27, 292, 7, 172, 537, 227, 242, 332, 247, 362, 427, 192, 32, 322, 187, 2, 142, 357, 397, 12, 202, 92, 57, 472, 462, 402, 42, 382, 547, 287, 602, 617, 82, 622 , 112, 177 , 567, 407, 72, 562, 377, 517, 10 7, 147, 387, 577, 467, 432, 222, 212, 152, 417, 132, 297, 37, 352, 367, 457, 372, 487, 552, 317, 157, 447, 312 . (10) Combined congruence Equations (1) and (7), (8), (9), (10) separately, by using the Chinese Remainder Theo- rem, we have conclusions as following. 81 21 k p M od10000 8751, 511, 1071, 4431, 4591, 5551, 1311, 5871, 3231, 7391, 2351, 2111, 671, 2031, 191, 9151, 2911, 5471, 831, 2991, 5951, 3711, 271, 9631, 5791, 2751, 4511, 5071, 8431, 8591, 9551, 5311, 9871, 7231, 1391, 6351, 6111, 4671, 6031, 4191, 3151, 6911, 9471, 4831, 6991, 9951, 7711, 4271, 3631, 9791, 6751, 8511, 9071, 2431, 2591, 3551, 9311, 3871, 1231, 5391, 351, 111, 8671, 31, 8191, 7151, 911, 3471, 8831, 991, 3951, 1711, 8271, 7631, 3791, 751, 2511, 3071, 6431, 6591, 7551, 3311, 7871, 5231, 9391, 4351, 4111, 2671, 4031, 2191, 1151, 4911, 7471, 2831, 4991, 7951, 5711, 2271, 1631, 7791, 4751, 6511, 7071, 431, 591, 1551, 7311, 1871, 9231, 3391, 8351, 8111, 6671, 8031, 6191, 5151, 8911, 1471, 6831, 8991, 1951, 9711, 6271, 5631, 1791( m). (11) 83 21 k p M 5007, 2047, 4287, 7727, 8367, 2207, 5247, 3487, 2927, 9567, 9407, 8447, 2687, 8127, 767, 6607, 1647, 1887, 3327, 1967, 3807, 4847, 1087, 8527, 3167, 1007, 8047, 287, 3727, 4367, 8207, 1247, 9487, 8927, 5567, 5407, 4447, 8687, 4127, 6767, 2607, 7647, 7887, 9327, 7967, 9807, 847, 7087, 4527, 9167, 7007, 4047, 6287, 9727, 367, 4207, 7247, 5487, 4927, 1567, 1407, 447, 4687, 127, 2767, 8607, 3647, 3887, 5327, 3967, 5807, 684 7, 3087, 527, 5727, 3007, 47, 2287, 5727, 6367, 207, 3247, 148 7, 927, 7567 , 7407 , 6447 , 687, 612 7, 8767, 4607, 9647, 9887, 1327, 9967, 1807, 2847, 9087, 6527, 1167, 9007, 6047, 8287, 1727, 2367, 6207, 9247, 7487, 6927, 3567, 3407, 2447, 6687, 2127, 4767, 607, 5647, 5887, 7327, 5967, 7807, 8847, 5087, 2527, 7167( ). mod10000 85 2 k p (12) 1M mod10000 87 2 k p 31, 8191, 7151, 911, 3471 , 8831, 991, 3951, 1711, 8271, 7631, 3791, 751, 2511, 3071, 6431, 6591, 7551, 3311, 7871, 5231, 9391, 4351, 4111, 2671, 4031, 2191, 1151, 4911, 7471, 2831, 4991, 7951, 5711, 2271, 1631, 7791, 4751, 6511, 7071, 431, 591, 1551, 7311, 1871, 9231, 3391, 8351, 8111, 6671, 8031, 6191, 5151, 8911, 1471, 6831, 8991, 1951, 9711, 6271, 5631, 1791, 8751, 511, 1071, 4431, 4591, 5551, 1311, 5871, 3231, 7391, 2911, 2111, 671, 2031, 191, 9151, 2911, 5471, 831, 2991, 5951, 3711, 271, 9631, 5791, 2751, 4511, 5071, 8431, 8591, 9551, 5311, 9871, 7231, 1391, 6351, 6111, 4671, 6031, 4191, 3151, 6911, 9471, 4831, 6991, 9951, 7711, 4271, 3631, 9791, 6751, 8511, 9071, 2431, 2591, 3551, 9311, 3871, 1231, 5391, 351, 111, 8671( ). (13) 1M mod10000 127, 2767, 8607, 3647, 3887, 5327, 3967, 5807, 684 7, 3087, 527, 5167, 3007, 47, 2287, 5727, 6367, 207, 3247, 148 7, 927, 7567 , 7407 , 6447 , 687, 612 7, 8767, 4607, 9647, 9887, 1327, 9967, 1807, 2847, 9087, 6527, 1167, 9007, 6047, 8287, 1727, 2367, 6207, 9247, 7487, 6927, 3567, 3407, 2447, 6687, 2127, 4767, 607, 5647, 5887, 7327, 5967, 7807, 8847, 5087, 2527, 7167, 5007, 2047, 4287, 7727, 8367, 2207, 5247, 3487, 2927, 9567, 9407, 8447, 2687, 8127, 767, 6607, 1647, 1887, 3327, 1967, 3807, 4847, 1087, 8527, 3167, 1007, 8047, 287, 3727, 4367, 8207, 1247, 9487, 8927, 5567, 5407, 4447, 8687, 4127, 6767, 2607, 7647, 7887, 9327, 7967, 9807, 847, 7087, 4527, 9167, 7007, 4047, 6287, 9727, 367, 4207, 7247, 5487, 4927, 1567, 1407, 447, 4687( ). (14) From the congruence Equation s (11)-(14), if 0k , 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120(), then mod12 5 85pk are composites, and then these numbers are not considered. So we can draw the conclusion. That completes the proof. 4. Acknowledgements The authors wish to thank Dr. Alden More for many help- ful discussions and com ments on the m a nuscript . 5. References [1] H. Z. Zhou, “The Distribution of Mersenne Primes,” in Chinese, Acta Scientiarum Naturalium Universitatis Sun- yatseni, Vol. 31, No. 4, 1992, pp. 121-122. Copyright © 2011 SciRes. AM  S. B. ZHANG ET AL. Copyright © 2011 SciRes. AM 1363 [2] S. B. Zhang, X. C. Ma and L. H. Zhou, “Some Notes on the Distribution of Mersenne Primes,” Applied Mathe- matics, Vol. 1, No. 4, 2010, pp. 312-315. doi:10.4236/am.2010.14041 [3] Q. Cheng and L. Feng, “The Research of Mersenne Primes Based on Distributed Computing,” Frontier Sci- ence, Vol. 4, No. 14, 2010, pp. 59-67. [4] S. B. Zhang, “Review of Research on Mersenne Primes,” Science ＆ Technology Review, Vol. 26, No. 18, 2008, pp. 88-92. [5] Q. Chen and P. Zhang, “A Math Treasure: Mersenne Primes,” in Chinese, Encyclopedic Knowledge, Vol. 32, No. 5, 2009, p. 22. [6] S. B. Zhang and A. Yunus, “A Note on Mersenne Num- bers,” in Chinese, Journal of Hebei North University, Vol. 26, No. 2, 2010, pp. 11-12. [7] S. B. Zhang, “The Mantissa of Mersenne Primes,” in Chinese, Journal of Jilin Normal University, Vol. 31, No. 2, 2010, pp. 92-94. [8] K. H. Rosen, “Elementary Number Theory and It’s Ap- plications,” Pearson Education, Inc., Upper Saddle River, 2005.
|
