This site is supported by donations to The OEIS Foundation.
Strong pseudoprimes
From OeisWiki
(Redirected from Strong pseudoprime)
A strong pseudoprime is an Euler pseudoprime with a special property. An odd composite number (where is odd) is a strong pseudoprime to a base if
or
The first condition is stronger.
Contents
Strong pseudoprimes and Euler pseudoprimes
Every strong pseudoprime is also an Euler pseudoprime. But not every Euler pseudoprime is a strong pseudoprime. The reason is because is a multiple of , so for a strong pseudoprime we have
In the most cases is or . But in some cases is , or , in these cases overlapping the definition of Euler pseudoprime and the definition of strong pseudoprimes.
Properties
- Every strong pseudoprime is odd, because every Euler pseudoprime is odd.
- If a strong pseudoprime is pseudoprime to a base in , than is pseudoprime to a base in and vice versa.
- There exist Carmichael numbers that are also strong pseudoprimes.
Sequences
A181782 Odd composite numbers that are strong pseudoprimes to some base .
- {25, 49, 65, 85, 91, 121, 125, 133, 145, 169, 175, 185, 205, 217, 221, 231, 247, 259, 265, 289, 301, 305, 325, 341, 343, 361, 365, 377, 385, 403, 425, 427, 435, 445, 451, 469, 475, ...}
Table of strong pseudoprimes between 15 and 1505
Case 1a | |
Case 2a | |
Case 1b | |
Case 2b |
25 | 3 | 7, 18 | ||
49 | 3 | 18, 30 | 19, 31 | |
65 | 1 | 8, 18, 47, 57 | ||
85 | 21 | 13, 38, 47, 72 | ||
91 | 45 | 9, 16, 22, 29, 53, 74, 79, 81 | 10, 12, 17, 38, 62, 69, 75, 82 | |
121 | 15 | 3, 9, 27, 81 | 40, 94, 112, 118 | |
125 | 31 | 57, 68 | ||
133 | 33 | 11, 30, 39, 58, 64, 102, 106, 121 | 12, 27, 31, 69, 75, 94, 103, 122 | |
145 | 9 | 12, 17, 128, 133 | ||
169 | 21 | 22, 146 | 23, 147 | 19, 70, 80, 89, 99, 150 |
175 | 87 | 51, 151 | 24, 124 | |
185 | 23 | 43, 68, 117, 142 | ||
205 | 51 | 32, 73, 132, 173 | ||
217 | 27 | 25, 32, 36, 67, 149, 156, 191, 211 | 6, 26, 61, 68, 150, 181, 185, 192 | |
221 | 55 | 21, 47, 174, 200 | ||
231 | 115 | 64, 148, 169, 190 | 41, 62, 83, 167 | |
247 | 123 | 68, 87, 144, 159, 172, 178, 191, 235 | 12, 56, 69, 75, 88, 103, 160, 179 | |
259 | 129 | 100, 121, 137, 149, 158, 186, 211, 232 | 27, 48, 73, 101, 110, 122, 138, 159 | |
265 | 33 | 23, 83, 182, 242 | ||
289 | 9 | 38, 251, 110, 134, 155, 179, 40, 65, 75, 131, 158, 214, 224, 249 | ||
301 | 75 | 36, 44, 79, 92, 130, 135, 165, 221 | 80, 136, 166, 171, 209, 222, 257, 265 | |
305 | 19 | 72, 133, 172, 233 | ||
325 | 81 | 126, 276 | 49, 199 | |
341 | 85 | 4, 16, 47, 64, 70, 78, 97, 125, 126, 157, 159, 163, 188, 190, 202, 218, 221, 225, 256, 280, 287, 295, 311, 312 | 29, 30, 46, 54, 61, 85, 116, 120, 123, 139, 151, 153, 178, 182, 184, 215, 216, 244, 263, 271, 277, 294, 325, 337 | |
343 | 171 | 18, 324 | 19, 325 | |
361 | 45 | 28, 54, 62, 68, 99, 234, 245, 292 | 69, 116, 127, 262, 293, 299, 307, 333 | |
365 | 91 | |||
377 | 47 | 70, 99, 278, 307 | ||
385 | 3 | 221, 331 | 54, 164 | |
403 | 201 | 87, 94, 118, 191, 211, 222, 315, 373 | 30, 88, 181, 192, 212, 285, 309, 316 | |
425 | 53 | 132, 157, 268, 293 | ||
427 | 213 | 74, 123, 135, 169, 184, 291, 352, 379 | 48, 75, 136, 243, 258, 292, 304, 353 | |
435 | 217 | 16, 136, 181, 226, 256, 286 | 149, 179, 209, 254, 299, 419 | |
451 | 225 | 16, 37, 42, 59, 79, 92, 100, 119, 124, 133, 141, 174, 180, 201, 221, 223, 247, 256, 262, 324, 344, 346, 379, 411 | 40, 72, 105, 107, 127, 189, 195, 204, 228, 230, 250, 271, 277, 310, 318, 327, 332, 351, 359, 373, 392, 409, 414, 435 | |
469 | 117 | 29, 37, 135, 163, 305, 372, 403, 431 | 38, 66, 97, 164, 306, 334, 432, 440 | |
475 | 237 | 26, 201 | 274, 449 | |
481 | 15 | 100, 211, 248, 269, 334, 380, 417, 445 | 36, 64, 101, 147, 212, 233, 270, 381 | 6, 8, 31, 45, 60, 80, 97, 119, 125, 154, 162, 171, 177, 193, 214, 216, 228, 236, 245, 253, 265, 267, 288, 304, 310, 319, 327, 356, 362, 384, 401, 421, 436, 450, 473, 475 |
485 | 121 | 22, 172, 313, 463 | ||
493 | 123 | 157, 191, 302, 336 | ||
505 | 63 | 192, 212, 293, 313 | ||
511 | 255 | 8, 64, 74, 81, 137, 336, 373, 429 | 82, 138, 145, 374, 430, 437, 447, 503 | |
529 | 33 | 118, 170, 177, 255, 266, 334, 399, 466, 487, 501 | 28, 42, 63, 130, 195, 263, 274, 352, 359, 411 | |
533 | 133 | 73, 255, 278, 460 | ||
545 | 17 | 33, 142, 403, 512 | ||
553 | 69 | 23, 102, 134, 260, 317, 396, 450, 529 | 24, 103, 157, 236, 293, 419, 451, 530 | |
559 | 279 | 79, 87, 92, 165, 178, 302, 380, 393 | 166, 179, 257, 381, 394, 467, 472, 480 | |
561 | 35 | 103, 256, 460, 511 | 50, 101, 305, 458 | |
565 | 141 | 98, 128, 437, 467 | ||
589 | 147 | 87, 125, 191, 273, 311, 315, 501, 552 | 37, 88, 274, 278, 316, 398, 464, 502 | |
595 | 297 | 86, 256 | 339, 509 | |
625 | 39 | 182, 443 | ||
629 | 157 | 191, 302, 327, 438 | ||
637 | 159 | 79, 165, 263, 295, 373, 393, 471, 508 | 129, 166, 244, 264, 342, 374, 472, 558 | |
645 | 161 | 16, 121, 226, 256, 391, 451 | 194, 254, 389, 419, 524, 629 | |
651 | 325 | 64, 190, 295, 442 | 209, 356, 461, 587 | |
671 | 335 | 9, 20, 34, 58, 70, 81, 119, 180, 182, 203, 245, 278, 302, 306, 339, 367, 375, 386, 400, 485, 489, 522, 619, 630 | 41, 52, 149, 182, 186, 271, 285, 296, 304, 332, 365, 369, 393, 426, 468, 479, 491, 552, 590, 601, 613, 637, 651, 662 | |
679 | 339 | 158, 326, 352, 389, 449, 520, 583, 617 | 62, 96, 159, 230, 290, 327, 353, 521 | |
685 | 171 | 37, 237, 448, 648 | ||
689 | 43 | 83, 242, 447, 606 | ||
697 | 87 | 132, 319, 378, 565 | ||
703 | 351 | 7, 9, 16, 26, 44, 47, 49, 63, 81, 83, 100, 112, 118, 120, 121, 123, 137, 144, 149, 157, 158, 182, 194, 195, 197, 201, 218, 229, 232, 234, 248, 256, 271, 275, 292, 305, 308, 329, 330, 334, 340, 343, 349, 359, 366, 367, 377. 386, 396, 403, 404, 408, 416, 419, 423, 441, 453, 454, 460, 482, 491, 514, 519, 530, 552, 556, 562, 567, 571, 581, 593, 625, 636, 638, 655, 662, 663, 676, 682 | 3, 21, 27, 40, 41, 48, 65, 67, 78, 110, 122, 132, 136, 141, 147, 151, 173, 184, 189, 212, 221, 243, 249, 250, 262, 280, 284, 287, 295, 299, 300, 307, 317, 326, 336, 337, 344, 354, 360, 363, 369, 373, 374, 395, 398, 411, 428, 432, 447, 455, 469, 471, 474, 485, 502, 506, 508, 509, 521, 545, 546, 554, 559, 566, 580, 582, 583, 585, 591, 603, 620, 622, 640, 654, 656, 659, 677, 687, 694, 696 | |
715 | 357 | 276, 386 | 329, 439 | |
721 | 45 | 46, 149, 207, 310, 365, 561, 571, 674 | 47, 150, 160, 356, 411, 514, 572, 675 | |
725 | 181 | 157, 307, 418, 568 | ||
745 | 93 | 193, 342, 403, 552 | ||
763 | 381 | 172, 219, 263, 281, 372, 499, 590, 655 | 108, 173, 264, 391, 482, 500, 544, 591 | |
775 | 387 | 501, 676 | 99, 274 | |
781 | 195 | 5, 25, 125, 147, 196, 199, 214, 218, 267, 289, 309, 356, 412, 427, 498, 522, 551, 554, 573, 625, 664, 696, 735, 764 | 17, 46, 85, 117, 156, 208, 227, 230, 259, 283, 354, 369, 425, 472, 492, 514, 563, 567, 582, 585, 634, 656, 756, 776 | |
785 | 49 | 28, 342, 443, 757 | ||
793 | 99 | 74, 196, 230, 352, 367, 562, 672, 718 | 75, 121, 231, 426, 441, 563, 597, 719 | 11, 21, 32, 50, 72, 93, 111, 151, 154, 162, 215, 223, 255, 265, 284, 294, 345, 395, 398, 448, 499, 509, 528, 538, 570, 578, 631, 639, 642, 682, 700, 721, 743, 761, 772, 782 |
805 | 201 | 116, 576 | 229, 689 | |
817 | 51 | 49, 87, 178, 216, 552, 638, 767, 780 | 37, 50, 179, 265, 601, 639, 730, 768 | |
841 | 105 | 190, 571, 574, 605, 645, 778 | 63, 196, 236, 267, 270, 651 | 14, 41, 60, 137, 221, 374, 416, 425, 467, 620, 704, 781, 800, 827 |
845 | 211 | 268, 408, 437, 577 | ||
847 | 423 | 485, 606 | 241, 362 | |
861 | 215 | 379, 631, 652, 715 | 146, 209, 230, 482 | |
865 | 27 | 93, 253, 612, 772 | ||
871 | 435 | 29, 68, 230, 269, 573, 640, 833, 841 | 30, 38, 231, 298, 602, 641, 803, 842 | |
889 | 111 | 107, 128, 361, 382, 400, 527, 781, 869 | 20, 108, 362, 489, 507, 528, 761, 782 | |
891 | 445 | 82, 163, 487, 730 | 161, 404, 728, 809 | |
901 | 225 | 30, 242, 659, 871 | ||
905 | 113 | 162, 343, 562, 743 | ||
925 | 231 | 26, 676 | 249, 899 | |
931 | 465 | 30, 197, 324, 410, 520, 638, 704, 900 | 31, 227, 293, 411, 521, 607, 734, 901 | |
949 | 237 | 74, 81, 300, 373, 575, 731, 794, 867 | 82, 155, 218, 374, 576, 649, 868, 875 | 24, 46, 70, 76, 97, 119, 122, 149, 216, 265, 268, 319, 362, 392, 411, 414, 435, 462, 487, 514, 535, 538, 557, 587, 630, 681, 684, 733, 800, 827, 830, 852, 873, 879, 903, 925 |
961 | 15 | 235, 338, 374, 388, 439, 448, 521, 531, 547, 628, 732, 816, 844, 846 | 115, 117, 145, 229, 333, 414, 430, 440, 513, 522, 573, 587, 623, 726 | |
965 | 241 | 112, 467, 498, 853 | ||
973 | 243 | 235, 459, 513, 557, 652, 737, 835, 876 | 97, 138, 236, 321, 416, 460, 514, 738 | |
985 | 123 | 183, 408, 577, 802 | ||
1001 | 125 | 92, 456, 729, 911 | 90, 272, 545, 909 | |
1015 | 507 | 291, 436 | 579, 724 | |
1025 | 1 | 32, 132, 893, 993 | ||
1027 | 513 | 55, 159, 339, 497, 529, 633, 924, 971 | 56, 103, 394, 498, 530, 688, 868, 972 | |
1035 | 517 | 271, 361, 496, 541, 676, 721, 811, 901, 946, 991 | 44, 89, 134, 224, 314, 359, 494, 539, 674, 764 | |
1037 | 259 | 72, 438, 599, 965 | ||
1045 | 261 | 111, 386, 441, 606, 771, 826, 881, 936 | 109, 164, 219, 274, 439, 604, 659, 934 | |
1057 | 33 | 32, 183, 303, 485, 571, 722, 907, 1024 | 33, 150, 335, 486, 572, 754, 874, 1025 | |
1065 | 133 | 91, 316, 616, 676, 811, 826 | 239, 254, 389, 449, 749, 974 | |
1073 | 67 | 191, 260, 302, 771, 813, 882 | ||
1075 | 537 | 251, 651 | 424, 824 | |
1099 | 549 | 144, 158, 169, 326, 772, 786, 954 | 13, 145, 313, 327, 773, 930, 941, 955 | |
1105 | 69 | 256, 341 | 764, 849 | 47, 72, 98, 123, 132, 242, 268, 293, 327, 353, 463, 548, 557, 642, 752, 778, 812, 837, 863, 973, 982, 1007, 1033, 1058 |
1111 | 555 | 36, 102, 137, 185, 188, 196, 203, 289, 339, 390, 405, 488, 499, 592, 642, 708, 892, 895, 903, 993, 1004, 1046, 1094, 1105 | 6, 17, 65, 107, 118, 208, 216, 219, 403, 469, 519, 612, 623, 706, 721, 772, 822, 908, 915, 923, 926, 974, 1009, 1075 | |
1141 | 285 | 58, 221, 267, 547, 653, 816, 919, 1082 | 59, 222, 325, 488, 594, 874, 920, 1083 | |
1145 | 143 | 107, 122, 1023, 1038 | ||
1147 | 573 | 63, 149, 211, 408, 470, 528, 676, 935 | 212, 471, 619, 677, 739, 936, 998, 1084 | |
1221 | 305 | 223, 334, 445, 889 | 332, 776, 887, 998 | |
1225 | 153 | 226, 851 | 374, 999 | |
1241 | 155 | 319, 557, 684, 922 | ||
1261 | 315 | 35, 61, 326, 352, 874, 971 | 36, 62, 290, 387, 909, 935, 1200, 1226 | |
1273 | 159 | 68, 96, 163, 305, 372, 805, 900, 1109 | 164, 373, 468, 901, 968, 1110, 1177, 1205 | |
1281 | 5 | 253, 400, 1156, 1240 | 41, 125, 881, 1028 | |
1309 | 327 | 375, 562 | 747, 934 | |
1313 | 41 | 515, 616, 697, 798 | ||
1333 | 333 | 36, 87, 466, 552, 780, 904, 1210, 1296 | 37, 123, 429, 553, 781, 867, 1246, 1297 | |
1345 | 21 | 82, 187, 1158, 1263 | ||
1369 | 171 | 581, 678, 737, 787, 932, 1015, 1045, 1069 | 300, 324, 354, 437, 582, 632, 691, 788 | 18, 76, 117, 348, 356, 424, 473, 476, 494, 875, 893, 896, 945, 1013, 1021, 1252, 1293, 1351 |
1385 | 173 | 217, 337, 1048, 1168 | ||
1393 | 87 | 92, 106, 200, 291, 305, 996, 1087, 1101 | 292, 306, 397, 1088, 1102, 1193, 1287, 1301 | |
1417 | 177 | 172, 263, 328, 1153, 1244, 1262, 1309, 1353 | 64, 108, 155, 173, 264, 1089, 1154, 1245 | 8. 33, 41, 76, 150, 177, 210, 226, 294, 319, 395, 444, 512, 553, 578, 613, 687, 695, 722, 730, 804, 839, 864, 905, 973, 1022, 1098, 1123, 1191, 1207, 1240, 1267, 1341, 1376, 1384, 1409 |
1441 | 45 | 53, 58, 89, 192, 320, 323, 394, 454, 482, 577, 708, 713, 716, 839, 918, 1006, 1049, 1101, 1109, 1137, 1180, 1237, 1268. 1368 | 73, 173, 204, 261, 304, 332, 340, 392, 435, 523, 602, 725, 728, 733, 864, 959, 987, 1047, 1118, 1121, 1249, 1352, 1383, 1388 | |
1445 | 361 | 38, 327, 1118, 1407 | ||
1465 | 183 | 138, 448, 1017, 1327 | ||
1469 | 367 | 437, 580, 889, 1032 | ||
1477 | 369 | 212, 225, 407, 436, 681, 634, 858, 1040 | 437, 619, 843, 859, 1041, 1070, 1252, 1265 | |
1501 | 375 | 102, 134, 159, 292, 1208, 1265, 1398, 1445 | 56, 103, 236, 293, 1209, 1342, 1367, 1399 |
See also
- Richard E. Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001, ISBN 0-387-25282-7.
- Paulo Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1996, ISBN 0-387-94457-5.