to find all the carmichael numbers N $\displaystyle < 10^{6} $ , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

$\displaystyle (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N $

Printable View

- Sep 9th 2009, 12:39 PMsilversandwhy is this argument about carmichael numbers true
to find all the carmichael numbers N $\displaystyle < 10^{6} $ , we only need to test composite N with primes a from 2 to 19 , and see if they satisfy:

$\displaystyle (a,N)=1 \ \ s.t. \ \ a^{N-1}=1 \ \ mod \ \ N $ - Sep 9th 2009, 07:38 PMThePerfectHacker
If prime numbers $\displaystyle a$ satisfy $\displaystyle a^{N-1}\equiv 1(\bmod N)$ then any number $\displaystyle (n,N)=1$ would have to satisfy $\displaystyle n^{N-1}\equiv 1(\bmod N)$. This is because if $\displaystyle a,b$ satisfy this congruence then $\displaystyle (ab)^{N-1}\equiv a^{N-1}b^{N-1}\equiv 1(\bmod N)$. Therefore, there products of all these primes would satisfy the congruence. But since $\displaystyle n$ can be realized as a product of primes it would mean that it itself satisfies the congruence.

- Sep 10th 2009, 04: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 < $\displaystyle 10^6$ 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, 03: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