From: Richard Guy [mailto:rkg@cpsc.ucalgary.ca] Subject: Re: n|[(2^n)-3] ; Ron Graham ... Date: Thursday, June 10, 1999 8:49 PM To: NMBRTHRY@LISTSERV.NODAK.EDU There was some email about this recently, from a different enquirer, I think. F10 (p.250 of 2nd edition) of UPINT [Unsolved Problems in Number Theory, by Guy:ed.] states that the Lehmers have shown that the smallest solution of 2^n = 3 mod n is n=470063497=19*47*5263229. Graham had asked the Lehmers to look for a solution. In a sense they were lucky, as they planned to go only to half a billion. At the time there were those who thought that there might not be a solution. I don't know of another, and would be interested to learn if one is found. It may be that this is the only place that the result is published. R. ============================================================================== From: thomas.womack@merton.oxford.ac.uk (Tom Womack) Subject: Re: n|[(2^n)-3] ; Ron Graham ... Date: 11 Jun 99 16:16:27 GMT Newsgroups: sci.math.numberthy Keywords: small solutions to 2^n = s mod n Having nothing better to do with my CPU time, I've carried Lehmer's search a little wider - for each s between 1 and 256, I've enumerated the 10 smallest solutions less than 2*10^9 to 2^n \equiv s \pmod n. The results are attached to this message (set tabs to 11 characters to get the columns to line up right) There was a misprint in the original article; the smallest n with n|2^n-3 is 4700063497 rather than 470063497, though the factorisation given was correct. Presumably there's a proof that $2^n \equiv 1 \pmod n$ is impossible, and I've certainly not seen a solution to that. Otherwise, for $n<2*10^9$, I've found solutions for $2^n \equiv q \pmod n$ except for $q \in \{1, 3, 33, 69, 141, 185, 231\}$. The minimum for 2^n \equiv 3^2 \pmod n is n=2228071, and for 2^n \equiv 3^3 \pmod n is 174934013, though higher powers of 3 are reached for much smaller n. There is presumably something lurking behind the facts 2^{25} \equiv 7 \pmod {25}, 2^{2^{25} - 7} \equiv 7 \pmod {2^{25}-7} 2^{18} \equiv 10 \pmod {18}, 2^{2^{18} - 10} \equiv 10 \pmod {2^{18}-10} 2^{91} \equiv 37 \pmod {91}, 2^{2^{91} - 37} \equiv 37 \pmod {2^{91}-37} though the pattern doesn't hold for arbitrary s. Tom [Note: reformated for compactness and clarity; I cannot guarantee no errors were introduced in the process -- djr] 0, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 1 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 3 4, 6, 10, 12, 14, 22, 26, 30, 34, 38, 46 5, 19147 6, 10669, 6611474 7, 25, 1727, 3830879, 33554425 8, 9, 15, 21, 33, 39, 51, 57, 63, 69, 87 9, 2228071, 16888457, 352978207, 1737848873 10, 18, 16666, 262134 11, 262279, 143823239, 382114303, 1223853491 12, 3763, 125714, 167716, 1803962, 2895548, 4031785, 36226466 13, 95, 4834519, 156203641 14, 1010, 61610, 469730, 2037190, 3820821, 9227438, 21728810, 24372562 15, 481, 44669, 1237231339, 1546675117 16, 20, 24, 28, 40, 44, 48, 52, 60, 68, 76 17, 45, 99, 53559, 1143357, 2027985, 36806085, 1773607905 18, 35, 77, 98, 686, 1715, 5957, 18995, 26075, 43921, 49901 19, 2873, 10081, 3345113, 420048673, 449349533 20, 2951, 926753239, 960640071, 1367105963 21, 3175999, 54895651 22, 42, 13746, 1048434, 319754822, 350849483 23, 555, 80481, 41546509, 967319517 24, 50, 232, 81028, 35622023, 125531078, 161524561 25, 95921, 24960497 26, 27, 2714, 17861, 24099, 336326, 364634, 26153222, 67108851, 67716217, 249689933 27, 174934013 28, 36, 54, 108, 1356, 2041, 14562, 24084, 38286, 48492, 3494412 29, 777, 56679, 274197, 2359749, 2804637, 4657821 30, 49, 238, 57526, 73843, 143702, 876169, 6588043, 7930534, 12971534, 14561758 31, 140039, 404167811, 1767944407 32, 56, 65, 85, 145, 165, 185, 205, 221, 224, 265 33 34, 110, 330, 1410, 3210, 9570, 19410, 126390, 150281, 299454, 4743530 35, 477, 671, 41817, 111771, 683147, 893541, 901077, 3261731, 29265401, 175933791 36, 697, 1738, 2060, 10180, 21338, 500089, 552838, 9142057, 13222948, 25883182 37, 91, 14364571, 61924805, 1222572623 38, 578, 5882, 86407, 7098418, 28702677, 101511658, 241304631, 1692548594 39, 623, 62771, 8176423, 1054773269 40, 156, 312, 16692, 99996, 1290552, 3319212, 4754856, 8719464, 18537061, 51767236 41, 2453, 35457, 584349, 57084101 42, 540923, 86133422 43, 55, 275, 935, 7871, 31597775 44, 70, 117, 1204, 3010, 34281, 57993, 113890, 275716, 2556716, 4667908 45, 345119 46, 287, 38586, 202842, 262098, 476567, 796523, 1417361, 15775487, 28789163, 249572574 47, 1131, 12585, 143321, 21086871, 24741253, 115078479, 248556333, 994200485 48, 104, 572, 4324, 8684, 8878, 12428, 65488, 524282, 1322672, 16062332 49, 943, 1075439 50, 147, 1311, 4047, 4389, 7791, 21399, 1643561, 1989403, 2543203, 3233171 51, 21967 52, 4044, 46506, 112636, 255012, 7863277, 8119513, 26362177, 279393612 53, 135, 153, 15255, 17557, 32249, 167355, 298215, 664031, 2688835, 5293215 54, 970, 4069, 14782, 108058, 2089874, 3531133, 3871642, 11486074, 39563002, 69263626 55, 46979 56, 220, 440, 1742, 47660, 49060, 250406, 570680, 1478840, 42843656, 204288440 57, 125, 925, 1991, 2378239, 128115025 58, 59378, 169978, 2508978, 3858733, 18656197, 59838019, 971506018 59, 3811, 10279, 35243, 236919, 549677, 11633491, 17572963, 193069749, 273813811 60, 119, 841, 25546, 30001, 79543, 109508, 480452 61, 23329, 62689 62, 345, 598, 1185, 101545, 129922, 196534, 4643722, 6403765, 11748297, 75872987 63, 155, 9607, 1018303 64, 66, 72, 78, 84, 90, 96, 102, 114, 126, 138 65, 1064959, 1112340129 66, 3007, 189247, 804779, 1388014, 11832917 67, 245, 665, 22505, 4312637, 4931279, 17002765, 26068931, 44322787, 100893853, 150322861 68, 75, 375, 1635, 4521, 5575, 12975, 23764, 40875, 100875, 313475 69 70, 1990362, 17993382, 33478901, 44328514, 378654109 71, 19719, 699027, 2223121, 4304727, 36336687, 98719037, 690212817 72, 184, 209, 2485, 28546, 69361, 70861, 129485, 679714, 716753, 1512151 73, 834976783 74, 190, 350, 1353, 37150, 151550, 379810, 525333, 1332590, 46970067, 71864043 75, 4029547, 13547021, 1200557377 76, 100, 300, 804, 1369, 4379, 4660, 74908, 75100, 136700, 145380 77, 1207, 80480417, 102282447 78, 115, 70682, 69107959, 166155082, 287044817, 307407998, 312176815, 676861873 79, 931, 4081, 8113, 140371, 153301, 243281, 1855913, 808742011 80, 81, 88, 169, 999, 8397, 65456, 919162, 5767058, 89080178, 171259467 81, 329, 27562303 82, 162, 414, 594, 2438, 3618, 3798, 178902, 189342, 291461, 2579021 83, 429, 76089, 7684989, 55133013, 66602913, 68556189, 193336869, 263920053, 384902197, 1076243493 84, 470, 56330, 10785230, 42368236, 327003076, 718164116, 1701333412 85, 143, 3308903 86, 406, 3934, 27202, 40399, 5890089, 14821582, 17989977, 395292562, 1922033342 87, 18607, 71665, 94001 88, 812, 1358, 1652, 2004, 4498, 8376, 48072, 60034, 513166, 719432 89, 423, 317551, 1185243, 12427689, 17392959, 227234169, 322020891 90, 6631, 18601, 39121, 429602, 228693421 91, 5422229 92, 105, 104853, 933747, 2282734, 4674532, 13897745, 22874565, 83314689, 96289577, 176534185 93, 175, 595, 3115, 3859, 402019, 10833283, 246862241, 1038678277, 1176882815 94, 310, 930, 229090, 8973478, 34636830 95, 4991, 197941, 4044459, 26029239, 100413687, 244820827, 1824164178 96, 160, 5536, 6544, 13708, 26291, 49520, 127774, 131060, 187360, 209761 97, 2076287, 21094385 98, 207, 495, 923, 1537, 14495, 29535, 67535, 103179, 161523, 203395 99, 202201409 100, 322, 444, 522, 826, 828, 1334, 1476, 4518, 5004, 11454 101, 50721, 116997, 128171, 5842003, 608575973, 672444343 102, 19145, 30778, 32978, 489598, 1992446, 41384243, 1524433862 103, 355, 17999 104, 152, 230, 1474, 95570, 233524, 272968, 331041, 3584481, 6732969, 29372456 105, 319, 1679, 8249, 134479, 3592307, 1645906253 106, 714, 1938, 2074, 37298, 52993, 66234, 310422, 42574782, 225644538, 921103698 107, 225, 285, 2865, 6225, 86811, 143583, 147003, 246213, 1597825, 3724583 108, 16733, 25843, 132626, 158926, 1370924, 11735947, 21081644, 100744271, 120328157, 310895756 109, 8683, 12679, 29729, 161903, 1787429 110, 867, 5837, 169643, 3591267, 4117431, 4655523, 14374839, 205310366, 562473686, 1044845062 111, 1917403, 178733903, 1433762599 112, 121, 464, 752, 996, 4632, 20112, 43464, 70984, 391848, 20144568 113, 2097039, 59708271, 64563143, 899738259, 1492719333 114, 130, 910, 2002, 16766, 37726, 46270, 246610, 156691090, 1389938290 115, 4819, 162073, 3295829 116, 140, 361, 539, 759, 980, 11649, 19061, 149780, 170269, 762881 117, 40477, 1990445, 8388491 118, 215, 2123, 3775, 20275, 35453, 108974, 151061, 262026, 1239575, 3059243 119, 5829, 607613, 1977747, 40067849, 481309523, 832877189 120, 136, 1768, 1924, 29896, 102737, 158819, 269656, 319174, 146139944, 150444424 121, 2737, 11327, 4026161, 6234911, 36959953, 169645057, 507261929, 593008279 122, 741, 13053, 169689, 110262945, 999008205, 1262244009, 1408244183 123, 1001, 2093, 104897, 5323561, 5512433 124, 150, 250, 750, 3972, 19750, 43318, 59550, 171138, 179492, 181950 125, 387, 29991, 57441, 106431, 1488387, 2256081, 3868839, 6862627, 100097693, 146775639 126, 2168638, 185675926, 676933373, 1073741761 127, 1805, 4400267, 27304763, 215462489 128, 133, 196, 217, 255, 259, 301, 427, 448, 469, 511 129, 4997, 110363, 3926509, 565443709 130, 602, 726, 22327, 23542, 33895878, 61141637, 161662886, 256721774 131, 4979787, 86113239, 1353732353 132, 325, 1325, 2278, 130516, 564293, 3762265, 41017213, 196422862, 1395279461 133, 7717397, 1092026695 134, 189, 231, 357, 890, 1869, 2669, 3213, 4238, 6069, 11781 135, 1073, 4665853, 365511517 136, 180, 216, 360, 540, 689, 696, 792, 1080, 3132, 4532 137, 2327, 3741, 26553, 47085, 73365, 108489, 390345, 23447041, 39598485, 63617683 138, 43135634, 1503400315 139, 144943, 264067 140, 442, 583, 1534, 3298, 9554, 10114, 138074, 918034, 1182619, 1369006 141 142, 385, 805, 5359, 15864654, 133590678 143, 369, 435, 3175, 3555, 30479, 204549, 2664841, 84752289, 136944735, 203317475 144, 770, 976, 1072, 2030, 2072, 7526, 19388, 19544, 34399, 94070 145, 2225759 146, 39778637 147, 1261877, 221471405, 1552375945 148, 294, 484, 564, 588, 924, 3234, 4452, 10164, 11374, 12054 149, 2129701, 13426789, 50610219, 105075897 150, 342563, 13216358, 21439486, 103470419 151, 161, 5389, 5977, 10793, 284101, 113659327 152, 884, 1972, 2265, 23896, 250172, 717292, 1017932, 2610476, 3325268, 5160242 153, 14795 154, 290, 738, 1278, 2190, 5658, 17958, 31098, 93223, 181590, 2698590 155, 289, 1281, 7097, 24393, 34377, 51153, 90457, 433041, 468537, 17654721 156, 380, 620, 1780, 2279, 8234, 99820, 4848572, 5538814, 50773660, 166957940 157, 159025 158, 266, 854, 6842, 66043, 187414, 17120435, 18840362, 29132309, 144735554, 246185151 159, 756737, 1991657 160, 492, 649, 1312, 2656, 3632, 420704, 619592, 730448, 839472, 1398098 161, 187, 297, 407, 459, 1053, 1947, 3267, 14157, 15147, 22627 162, 253, 6862, 9557, 9899, 14089, 68563, 1073693, 3071209, 5300377, 5798585 163, 655, 2573, 164317, 304001, 62593615, 1738153591 164, 430, 17511, 23908, 49191, 50271, 237471, 282532, 1694452, 2583236, 15067923 165, 6439, 24587, 69523, 1303799, 33955187, 310441019, 341669993 166, 58957, 67834, 645119, 11136634, 22003742, 38330958 167, 3201, 143781, 163005, 751605, 47701785, 79342643, 181220465, 299798385, 842976979 168, 418, 32248, 243622, 344731, 1693355, 2833975, 61557241, 191940715, 218260318, 765859468 169, 86070137 170, 171, 26727, 153274, 2670303, 9330274, 21629277, 35633722, 36975531, 38275953, 215170017 171, 2424703, 4030279, 7290239, 222995369 172, 342, 684, 737, 1308, 2702, 3492, 6894, 28868, 48587, 228054 173, 235, 615, 795, 11647, 12095, 1671503, 7351303, 50257281, 928204013 174, 850, 18373, 120850, 39246094 175, 467429821 176, 200, 304, 400, 688, 1659, 2171, 4300, 11120, 36808, 52420 177, 13279, 754791437, 1403280161 178, 1491046, 6729738, 14390106, 22364821, 1815361915 179, 333, 391, 4607, 17799, 36166191, 300780171 180, 6751, 16564, 63724, 96031, 226484, 664364, 1940318, 21793559, 67100764, 604263364 181, 321187367 182, 625, 41425, 49125, 81465, 7596825, 92979665, 121956734, 264890125, 424096125 183, 755, 55115, 73235, 281615, 591133, 30107135 184, 1956, 2291, 2563, 4170, 5064, 79512, 124189, 703597, 1315110, 1931190 185 186, 203, 22127, 61013498, 125401693 187, 876445, 25907437, 192933683 188, 377, 2715, 5373, 33723, 50535, 215557, 245709, 35791391, 36649395 189, 10948709 190, 198, 378, 966, 1302, 4158, 13482, 72954, 130878, 226517, 429102 191, 9541, 1588069, 7159879, 14447083, 116528293 192, 704, 1184, 11168, 16336, 18145, 44278, 54464, 63788, 127724, 166304 193, 247, 875, 13927, 27023, 1884037, 2228395, 2384875, 2548175, 3087875, 20219875 194, 830, 11639, 14062, 16999, 136154, 213667, 121355933, 142541457, 711136991 195, 5959 196, 780, 1716, 2020, 2486, 3460, 6438, 10097, 13596, 17940, 27660 197, 441, 705, 2205, 3465, 6657, 7245, 8085, 23499, 101805, 124803 198, 415, 72415, 96835, 113302, 2090431, 201017695, 1001959474 199, 8299, 439247 200, 2211, 2686, 4769, 32878, 36777, 91172, 109256, 156651, 187397, 328987 201, 4453 202, 242, 611, 4422, 10974, 34122, 48642, 670078, 1103741, 2121114, 88585318 203, 238407, 2043357, 63078951, 128496495 204, 410, 817, 5263, 2810788, 3637030, 49494373, 107282468, 111161290, 229814899 205, 1067, 550853, 1216139, 149724059 206, 25317, 171891, 870466, 36149553, 172835933, 285746761, 955722802, 996399801 207, 1681, 5725, 146525, 21136325, 110062285, 312540925, 1357241081 208, 306, 1926, 14004, 21776, 52938, 108973, 2796168, 25127208, 44164188, 72944968 209, 555589371 210, 1702, 8362, 83688734 211, 26054947 212, 4354, 29365, 1135985, 1564948, 65289274, 222754179, 394239433, 468775761, 1432051763 213, 5017703, 5722055, 87781163 214, 4110, 4970, 22190, 34790, 51857, 57491, 7837530, 19328330, 27503273, 37035210 215, 1089, 423379, 2886057, 9448041, 134217513, 192182859, 375270921 216, 15560, 444361, 524180, 814474, 3091544, 143335574, 853519144 217, 38275817, 48006533 218, 286, 775, 3255, 16275, 23062, 36586, 269855, 361275, 1020675, 1048467 219, 871, 188659, 261073, 66927841, 983478781, 1822722811 220, 228, 29308, 293924, 520494, 1895228, 2993874, 4981884, 7346244, 14850588, 25717684 221, 249767, 673935567, 1633850619 222, 693482, 9440702, 22577686, 151768847, 1556925001 223, 955, 7969, 11567, 32929, 98692009 224, 352, 2512, 6850, 22828, 67288, 3608096, 4556812, 8819851, 45445816, 68299352 225, 133290503, 200517047, 353277601 226, 22099, 37702, 184126, 261918, 6203826, 12036703, 44366266, 120871882 227, 6677, 162705, 950241, 8260265, 36144173, 45069279, 472207143 228, 455, 8078, 20374, 246881, 1147835, 5575634, 26762414, 50828015, 529946207 229, 2224331, 75467267 230, 41191, 1803806, 2274847, 514192018, 1196985722 231 232, 276, 888, 2587, 6216, 34922, 58164, 64776, 1886178, 2663556, 3222365 233, 279, 335, 3615, 3735, 13761, 67239, 101395, 313071, 778671, 6439741 234, 790, 39833, 83030, 173230, 967475906 235, 749, 68516213, 1621138253 236, 460, 860, 1060, 1682, 3243, 418421, 430418, 676748, 6967204, 7291780 237, 47765, 180605, 5717605, 9929585, 73611079, 1345161733 238, 515, 5917, 21527, 2297537, 7456514, 8641326, 13119713, 53776841, 103038486, 107719889 239, 273, 363, 3549, 33033, 46137, 161301, 248781, 599781, 942513, 10206713 240, 616, 848, 28441, 37009, 868516, 38291756, 67108804, 216968026, 378754942, 489092296 241, 215070011 242, 243, 351, 405, 2085, 2727, 2765, 3159, 3471, 3483, 3807 243, 1055, 114095, 172175, 6566135, 20168975, 31401577, 737001575, 936632275 244, 270, 324, 451, 486, 810, 972, 1284, 1746, 1786, 2430 245, 11479, 11319999, 41601841, 93169677 246, 210395261, 263857606 247, 167671, 246148151 248, 1210249, 5089233, 11120955, 13091992, 64936099, 82292348, 94804421, 207615227, 350206828 249, 2827, 215137, 188903377, 303285857 250, 84379, 130462, 466426, 511066, 4701379, 8155691, 23084722, 28680089, 59347909, 111909101 251, 261, 358009, 1541151, 17904231, 329330361, 1110836829 252, 7849, 27158, 50902, 939362, 22727102, 50155789, 107150402, 131706662, 1814567527 253, 493 254, 2530, 3190, 5513, 17710, 22582, 60803, 86570, 107543, 491890, 511610 255, 529, 9495461 ============================================================================== From: elkies@abel.math.harvard.edu (Noam Elkies) Subject: n|2^n-1 (Re: n|2^n-3) Date: 11 Jun 99 22:03:28 GMT Newsgroups: sci.math.numberthy > Presumably there's a proof that $2^n \equiv 1 \pmod n$ is impossible, It's not hard. Let p be the smallest prime factor of n. Then n must be divisible by the multiplicative order of 2 mod n, which is a factor of p-1. This is impossible. NDE ============================================================================== From: dean@math.ucdavis.edu (Dean Hickerson) Subject: Re: n|[(2^n)-3] ; Ron Graham ... Date: 11 Jun 99 22:03:31 GMT Newsgroups: sci.math.numberthy Tom Womack (thomas.womack@merton.oxford.ac.uk) wrote: > Having nothing better to do with my CPU time, I've carried Lehmer's search a > little wider - for each s between 1 and 256, I've enumerated the 10 smallest > solutions less than 2*10^9 to 2^n \equiv s \pmod n. The results are attached > to this message (set tabs to 11 characters to get the columns to line up > right) (It appears that what's listed are the smallest solutions n>2 of the equation 2^n mod n = s, not the congruence 2^n == s (mod n). For example, for s=5 the congruence also has the solution n=3.) > Otherwise, for $n<2*10^9$, I've found solutions for $2^n \equiv q \pmod n$ > except for $q \in \{1, 3, 33, 69, 141, 185, 231\}$. Last year I found solutions for 33 and 141; I don't know if they're minimal: 2^n mod n n Prime factorization of n --------- ------------------ ------------------------ 33 319020450922208555 5 13 4908006937264747 141 250836050261 59 4251458479 I found these by looking for solutions of the form n = rp, where r is a small odd number and p is a prime not dividing r. (If q is even, we could also allow even values of r, but I haven't tried that.) For such a solution, the condition that 2^n == q (mod n) is equivalent to 2^(rp) == q (mod r) and p | 2^r - q. We can rule out those values of r for which q is not a power of 2^r (mod r). For the remaining values, the first congruence is equivalent to one of the form p == a (mod m) for some a, where m is the multiplicative order of 2^r (mod r). If gcd(a,m) is composite, then this congruence can't be satisfied by a prime p. If gcd(a,m) is prime, then p must equal gcd(a,m). Otherwise, if gcd(a,m) = 1, we factor 2^r - q and check for prime divisors == a (mod m). My search used Mathematica's factorization routine. Someone with a better factorization program could probably fill in some more values. Dean Hickerson dean@math.ucdavis.edu ============================================================================== From: joecr@microsoft.com (Joe Crump) Subject: Re: 2^n mod n = e Date: 11 Jun 99 22:03:34 GMT Newsgroups: sci.math.numberthy The online integer encyclopedia contains several sequences of 2^n mod n. http://www.research.att.com/~njas/sequences/index.html In particular, the info Richard Guy pointed out is in: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An um=036236 ---------------------------------------------------------------------------- -------------------- ID Number: A036236 Sequence: 3,4700063497,6,19147,10669,25,9,2228071,18,262279,3763,95,1010,481,20, 45,35,2873,2951,3175999,42,555,50,95921,27,174934013,36,777,49,140039, 56 Name: a(n) = least k with 2^k mod k = n (inverse of A015910). Comments: No n exists with 2^n mod n = 1. a(3) first computed by Lehmers. References R. K. Guy, Unsolved Problems in Number Theory, Section F10. See also: Cf. A015910, A036237. Keywords: hard,nonn,nice Offset: 2 Author(s): David Wilson (wilson@ctron.com) Extension: a(33) <= 319020450922208555, per Dean Hickerson ---------------------------------------------------------------------------- -------------------- I've added a few in the past, such as 2^n mod n = 7, 11, 15. But, they don't go very far (just ran a brute-force app for a few hours)... http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An um=033981 http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An um=033982 http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An um=033983 Are there any decent algorithms, or helpful tricks for finding solutions 'n' to 2^n mod n = e, where 'e' very small, say e <= 31? Or have these numbers already been computed and collected somewhere? Thanks! - Joe -----Original Message----- [quoted at top of document --djr] ============================================================================== From: Peter-Lawrence.Montgomery@cwi.nl Subject: New solution to 2^n == 3 (mod n) Date: 24 Jun 99 14:45:57 GMT Newsgroups: sci.math.numberthy According to problem F10 in Richard Guy's `Unsolved Problems in Number Theory', the only known solution to the congruence 2^n == 3 (mod n) with n > 1 is n = 19 * 47 * 5263229. The 65-digit number n2 below is another solution. It was found on June 23, 1999 at CWI, Amsterdam. This n2 was found by guessing that the solution would have the from n = r * q, where r = 485 and q is prime. In order that 485 divide 2^n - 3 we require n == 19 (mod 48). In order that q divide 2^n - 3 we require q divide 2^r - 3. The factorization of 2^485 - 3 was achieved by the number field sieve algorithm. It took one CPU-month, spread over three calendar-days, using SGI and SPARC workstations at CWI. One prime factor, called p63 below, is in the desired congruence class (mod 48) and gives the new solution. Ostensibly there are phi(48) = 16 potential congruence classes for primes modulo 48, but we know that 6 is a quadratic residue modulo any factor of 2^485 - 3. Hence any prime factor of 2^485 - 3 will be congruent to 1, 5, 19, or 23 modulo 24, giving only eight possibilities modulo 48. This made r = 485 especially worthy of investigation. I have tried to factor 2^r - 3 for several other r, primarily by the elliptic curve method, without finding another solution to the congruence. I thank Paul Leyland (Microsoft Research) and Paul Zimmermann (Inria) for assisting in these factorizations. Peter Montgomery pmontgom@cwi.nl Microsoft Research and CWI ############## Maple code below n1 := 19 * 47 * 5263229; 2 &^ n1 mod n1; # 3 p63 := 130166407115741105132742556824466265630151260716462422214638983; n2 := 5 * 97 * p63; 2 &^ n2 mod n2; # 3 p63 mod 48; n2 mod 48; evalf(n2); p68 := 22341942494294113473321292753921092454785291734670955227136157571499; (2^485 - 3)/(53 * 53 * 2285189 * 5351237 * p63 * p68); # 1 isprime(p63); isprime(p68); ;quit;