to find all the carmichael numbers N , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

Printable View

- Sep 9th 2009, 01:39 PMsilversandwhy is this argument about carmichael numbers true
to find all the carmichael numbers N , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

- Sep 9th 2009, 08:38 PMThePerfectHacker
If prime numbers satisfy then any number would have to satisfy . This is because if satisfy this congruence then . Therefore, there products of all these primes would satisfy the congruence. But since can be realized as a product of primes it would mean that it itself satisfies the congruence.

- Sep 10th 2009, 05:51 AMaidan
You will also find primes as pointed out by ThePerfectHacker, but

how will you distinguish these Carmichael Numbers from primes:

A few Carmichael Numbers < with smallest factor > 19

252601 = 41 * 61 * 101

294409 = 37 * 73 * 109

399001 = 31 * 61 * 211

410041 = 41 * 73 * 137

488881 = 37 * 73 * 181

512461 = 31 * 61 * 271

. - Sep 11th 2009, 04:00 AMsilversandno clear
ThePerfectHacker's answer is not clear.

i cant get why we only need to test primes a from 2 to 19 to find all Carmichael < 10^6