User:Karsten Meyer/Squarefree, odd numbers with exactly 2 distinct prime factors

Squarefree, odd numbers with exactly 2 distinct prime factors

Every squarefree odd number $\scriptstyle n=p_{1}*p_{2}\,$ with distinct primes is a fermat pseudoprime to two bases $\scriptstyle a\,$ and $\scriptstyle a'=n-a\,$. It is easy to show that: Take any two distinct primes $\scriptstyle p_{1}\,$ and $\scriptstyle p_{2}\,$. The product is $\scriptstyle n=p_{1}*p_{2}\,$. Now calculate every multiple of $\scriptstyle p_{1}\,$ smaller $\scriptstyle n\,$ and calculate every multiple of $\scriptstyle p_{2}\,$ smaller $\scriptstyle n\,$:

$\scriptstyle p_{1};\,2*p_{1};\,3*p_{1};\,...\,(p_{2}-1)*p_{1}$

$\scriptstyle p_{2};\,2*p_{2};\,3*p_{2};\,...\,(p_{1}-1)*p_{2}$

Example

The distinct prime numbers are $\scriptstyle p_{1}=7\,$ and $\scriptstyle p_{2}=41\,$. $\scriptstyle n=p_{1}*p_{2}=7*41=287\,$. The multiples of $\scriptstyle p_{1}\,$ and $\scriptstyle p_{2}\,$ are:

7 14 21 28 35 42 49 56 63 70 77 84 91 98 105 112 119 126 133 140 147 154 161 168 175 182 189 196 203 210 217 224 ...

41 82 123 164 205 246

82 is a multiple of 41, and 84 is a multiple of 7. So we took 82 and 84 as a pair. The number between 82 and 84 is 83. 83 is coprime to 82 and it is coprime to 84 too. The other pair is 203 and 205. The number between 203 and 205 is 204. 204 is to both, 203 and 205 coprime. The sum of 83 and 204 is 287. That is $\scriptstyle n\,$. If you make the test:

$\scriptstyle 83^{287-1}\equiv 1{\pmod {287}}$

$\scriptstyle 204^{287-1}\equiv 1{\pmod {287}}$

Voila!

Table

15	3*5	4, 11
21	3*7	8, 13
33	3*11	10, 23
35	5*7	6, 29
39	3*13	14, 25
51	3*17	16, 35
55	5*11	21, 34
57	3*19	20, 37
65	5*13	8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57
69	3*23	22, 47
77	7*11	34, 43
85	5*17	4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81
87	3*29	28, 59
91	7*13	3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88
93	3*31	32, 61
95	5*19	39, 56
111	3*37	38, 73
115	5*23	24, 91
119	7*17	50, 69
123	3*41	40, 83
129	3*43	44, 85
133	7*19	8, 11, 12, 18, 20, 26, 27, 30, 31, 37, 39, 45, 46, 50, 58, 64, 65, 68, 69, 75, 83, 87, 88, 94, 96, 102, 103, 106, 107, 113, 115, 121, 122, 125
141	3*47	46, 95
143	11*13	12, 131
145	5*29	12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133
155	5*31	61, 94
159	3*53	52, 107
161	7*23	22, 139
177	3*59	58, 119
183	3*61	62, 121
185	5*37	6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179
187	11*17	67, 120
201	3*67	68, 133
203	7*29	57, 146
205	5*41	9, 32, 42, 73, 81, 83, 91, 114, 122, 124, 132, 163, 173, 196
209	11*19	56, 153
213	3*71	70, 143
215	5*43	44, 171
217	7*31	5, 6, 25, 26, 30, 32, 36, 37, 57, 61, 67, 68, 87, 88, 92, 94, 99, 118, 123, 125, 129, 130, 149, 150, 156, 160, 180, 181, 185, 187, 191, 192, 211, 212
219	3*73	74, 145
221	13*17	18, 21, 38, 47, 64, 86, 103, 118, 135, 157, 174, 183, 200, 203
235	5*47	46, 189
237	3*79	80, 157
247	13*19	12, 27, 30, 49, 56, 64, 68, 69, 75, 77, 87, 88, 94, 103, 107, 113, 121, 126, 134, 140, 144, 153, 159, 160, 170, 172, 178, 179, 183, 191, 198, 217, 220, 235
249	3*83	82, 167
253	11*23	45, 208
259	7*37	10, 11, 26, 27, 36, 38, 47, 48, 64, 73, 75, 85, 100, 101, 110, 121, 122, 137, 138, 149, 158, 159, 174, 184, 186, 195, 211, 212, 221, 223, 232, 233, 248, 249
265	5*53	23, 52, 54, 76, 83, 107, 129, 136, 158, 182, 189, 211, 213, 242
267	3*89	88, 179
287	7*41	83, 204
291	3*97	98, 193
295	5*59	119, 176
299	13*23	116, 183
301	7*43	6, 36, 37, 44, 50, 79, 80, 85, 87, 92, 93, 122, 123, 128, 130, 135, 136, 165, 166, 171, 173, 178, 179, 208, 209, 214, 216, 221, 222, 251, 257, 264, 265, 295
303	3*101	100, 203
305	5*61	11, 62, 72, 111, 121, 123, 133, 172, 182, 184, 194, 233, 243, 294
309	3*103	104, 205
319	11*29	144, 175
321	3*107	106, 215
323	17*19	18, 305
327	3*109	110, 217
329	7*47	48, 281
335	5*67	66, 269
339	3*113	112, 227
341	11*31	2, 4, 8, 15, 16, 23, 27, 29, 30, 32, 35, 39, 46, 47, 54, 58, 60, 61, 63, 64, 70, 78, 85, 89, 91, 92, 94, 95, 97, 101, 108, 109, 116, 120, 122, 123, 125, 126, 128, 139, 140, 147, 151, 153, 156, 157, 159, 163, 170, 171, 178, 182, 184, 185, 188, 190, 194, 201, 202, 213, 215, 216, 218, 219, 221, 225, 232, 233, 240, 244, 246, 247, 249, 250, 252, 256, 263, 271, 277, 278, 280, 281, 283, 287, 294, 295, 302, 306, 309, 311, 312, 314, 318, 325, 326, 333, 337, 339
355	5*71	141, 214
365	5*73	27, 46, 72, 74, 119, 147, 173, 192, 218, 246, 291, 293, 319, 338
371	7*53	160, 211
377	13*29	12, 57, 70, 86, 99, 144, 157, 220, 233, 278, 291, 307, 320, 365
381	3*127	128, 253
391	17*23	137, 254
393	3*131	130, 263
395	5*79	159, 236
403	13*31	25, 30, 36, 56, 61, 68, 87, 88, 92, 94, 118, 129, 160, 181, 185, 191, 192, 211, 212, 218, 222, 243, 274, 285, 309, 311, 315, 316, 335, 342, 347, 367, 373, 378
407	11*37	186, 221
411	3*137	136, 275
413	7*59	176, 237
415	5*83	84, 331
417	3*139	140, 277
427	7*61	13, 47, 48, 60, 62, 74, 75, 108, 109, 121, 123, 135, 136, 169, 170, 184, 197, 230, 243, 257, 258, 291, 292, 304, 306, 318, 319, 352, 353, 365, 367, 379, 380, 414
437	19*23	208, 229
445	5*89	34, 88, 123, 144, 177, 179, 212, 233, 266, 268, 301, 322, 357, 411
447	3*149	148, 299
451	11*41	4, 10, 16, 18, 23, 25, 31, 37, 40, 42, 45, 51, 57, 59, 64, 72, 78, 81, 83, 86, 92, 98, 100, 105, 107, 113, 119, 122, 124, 127, 133, 139, 141, 146, 148, 160, 163, 168, 174, 180, 182, 189, 195, 201, 204, 206, 215, 221, 223, 228, 230, 236, 245, 247, 250, 256, 262, 269, 271, 277, 283, 288, 291, 303, 305, 310, 312, 318, 324, 327, 329, 332, 338, 344, 346, 351, 353, 359, 365, 368, 370, 373, 379, 387, 392, 394, 400, 406, 409, 411, 414, 420, 426, 428, 433, 435, 441, 447
453	3*151	152, 301
469	7*67	29, 30, 37, 38, 66, 68, 96, 97, 104, 135, 163, 164, 171, 172, 200, 202, 230, 239, 267, 269, 297, 298, 305, 306, 334, 365, 372, 373, 401, 403, 431, 432, 439, 440
471	3*157	158, 313
473	11*43	87, 386
481	13*37	6, 8, 10, 11, 14, 23, 27, 29, 31, 36, 38, 43, 45, 47, 48, 51, 60, 63, 64, 66, 68, 73, 75, 80, 82, 84, 85, 88, 97, 100, 101, 103, 105, 110, 112, 119, 121, 122, 125, 134, 137, 138, 140, 142, 147, 149, 154, 158, 159, 162, 171, 174, 175, 177, 179, 184, 186, 191, 193, 196, 199, 211, 212, 214, 216, 223, 228, 230, 232, 233, 236, 245, 248, 249, 251, 253, 258, 265, 267, 269, 270, 282, 285, 288, 290, 295, 297, 302, 304, 306, 307, 310, 319, 322, 323, 327, 332, 334, 339, 341, 343, 344, 347, 356, 359, 360, 362, 369, 371, 376, 378, 380, 381, 384, 393, 396, 397, 399, 401, 406, 408, 413, 415, 417, 418, 421, 430, 433, 434, 436, 438, 443, 445, 450, 452, 454, 458, 467, 470, 471, 473, 475
485	5*97	22, 96, 98, 119, 172, 193, 216, 269, 292, 313, 366, 387, 389, 463
489	3*163	164, 325
493	17*29	30, 86, 115, 157, 186, 191, 220, 273, 302, 307, 336, 378, 407, 463
497	7*71	141, 356
501	3*167	166, 335
505	5*101	91, 102, 111, 192, 201, 203, 212, 293, 302, 304, 313, 394, 403, 414
511	7*73	8, 9, 64, 65, 72, 74, 81, 82, 137, 138, 145, 155, 211, 218, 220, 227, 228, 283, 284, 291, 293, 300, 356, 366, 373, 374, 429, 430, 437, 439, 446, 447, 502, 503
515	5*103	104, 411
517	11*47	142, 375
519	3*173	172, 347
527	17*31	154, 373
533	13*41	40, 73, 83, 122, 155, 196, 255, 278, 337, 378, 411, 450, 460, 493
535	5*107	106, 429
537	3*179	178, 359
543	3*181	182, 361
545	5*109	33, 76, 108, 142, 217, 219, 251, 294, 326, 328, 403, 437, 469, 512
551	19*29	115, 436
553	7*79	23, 24, 55, 78, 80, 102, 103, 134, 135, 157, 159, 181, 213, 214, 236, 260, 261, 292, 293, 317, 339, 340, 372, 394, 396, 418, 419, 450, 451, 473, 475, 498, 529, 530
559	13*43	36, 42, 49, 79, 87, 92, 165, 166, 173, 178, 179, 209, 222, 251, 257, 259, 264, 295, 300, 302, 308, 337, 350, 380, 381, 386, 393, 394, 467, 472, 480, 510, 517, 523
565	5*113	98, 112, 114, 128, 211, 227, 241, 324, 338, 354, 437, 451, 453, 467
573	3*191	190, 383
579	3*193	194, 385
581	7*83	167, 414
583	11*53	54, 529
589	19*31	26, 30, 37, 56, 68, 87, 88, 94, 125, 160, 191, 216, 254, 273, 274, 278, 284, 305, 311, 315, 316, 335, 373, 398, 429, 464, 495, 501, 502, 521, 533, 552, 559, 563